6

I have table with tree structure (defined by hierarchyid column) and I want to select all descendants of particular record. For that, I am using hiearchyid.IsDescendantOf() method.

I expected, that since I am not doing simple comparisons, but I am performing operations (in this case I am calling the IsDescendantOf() method) then I will get some terrible execution plan with index scans and whatnot.

Yet SQL Server optimized it away to nice little index seek.

Execution Plan

I am puzzled why and how.

Does calling methods on CLR types usually get optimized away? I assumed, that the SQL Server sees the CLR types as opaque black box and therefore cannot work it's magic on it. (Since it is not able to do so on native SQL functions either.)

Or is that only for the this particular method? (Since the hieararchyid values are ordered depth-first, I could get the similar result just by doing comparisons.)

Demo:

CREATE TABLE dbo.HierarchyExample (
    Id INT PRIMARY KEY,
    Hieararchy HIERARCHYID NOT NULL
);

INSERT INTO dbo.HierarchyExample(Id, Hieararchy)
VALUES
(1,  hierarchyid::Parse('/1/')),
(2,  hierarchyid::Parse('/1/1/')),
(3,  hierarchyid::Parse('/1/2/')),
(4,  hierarchyid::Parse('/1/3/')),
(5,  hierarchyid::Parse('/1/3/1/')),
(6,  hierarchyid::Parse('/1/3/2/')),
(7,  hierarchyid::Parse('/1/3/3/')),
(8,  hierarchyid::Parse('/1/4/')),
(9,  hierarchyid::Parse('/1/4/1/')),
(10, hierarchyid::Parse('/1/4/2/'));

CREATE INDEX IX_HierarchyExample_Hierarchy 
ON dbo.HierarchyExample (Hieararchy);

SELECT descendant.*
FROM HierarchyExample ancestor
    INNER JOIN HierarchyExample descendant
        ON descendant.Hieararchy.IsDescendantOf(ancestor.Hieararchy) = 1
WHERE ancestor.Id = 1

DROP TABLE IF EXISTS dbo.HierarchyExample;

The execution plan

The fiddle

1 Answer 1

5

descendant.Hieararchy.IsDescendantOf(ancestor.Hieararchy) = 1 certainly doesn't look like it should be sargable but it seems to do some shenanigans very early on in the process for this specific case.

If I try

declare @x hierarchyid;     

SELECT *
FROM HierarchyExample descendant
WHERE descendant.Hieararchy.IsDescendantOf(@x) = 1
OPTION (querytraceon 3604, querytraceon 8605, querytraceon 8606);

The resultant execution plan shows a seek on

Seek Keys[1]: Start: [tempdb].[dbo].[HierarchyExample].Hieararchy >= Scalar Operator([@x]), 
               End:  [tempdb].[dbo].[HierarchyExample].Hieararchy <= Scalar Operator([@x].DescendantLimit())

The range expression is already present in the converted tree.

The converted tree is the parse tree from the parser, imported and transformed ('converted') into a tree structure that the early compilation stages find convenient to work with.

*** Converted Tree: ***
    LogOp_Project QCOL: [descendant].Id QCOL: [descendant].Hieararchy

        LogOp_Select

            LogOp_Get TBL: HierarchyExample(alias TBL: descendant) HierarchyExample TableID=1093578934 TableReferenceID=0 IsRow: COL: IsBaseRow1000 

            ScaOp_Logical x_lopAnd

                ScaOp_Comp x_cmpLe

                    ScaOp_Identifier COL: @x 

                    ScaOp_Identifier QCOL: [descendant].Hieararchy

                ScaOp_Comp x_cmpLe

                    ScaOp_Identifier QCOL: [descendant].Hieararchy

                    ScaOp_UdtFunction EClrFunctionType_UdtMethodDescendantLimit IsDet NoDataAccess  TI(hierarchyid,Null,Var,ML=892) 

                        ScaOp_Identifier COL: @x 

        AncOp_PrjList 

So I conclude that during parsing this gets converted to a potentially seekable range predicate.

This transformation is mentioned in passing in the paper Relational support for flexible schema scenarios though it does not go into huge details.

To support the considered scenarios, we defined a specific operation that is internally rewritten before relational processing takes place. The fact that a column H1 is a descendant of H2 is expressed by H1.IsDescendant(H2) and after translation becomes the range predicate: H2 >= H1 and H2 <= H1.DescendantLimit().

Thereafter optimisation just happens as normal. The query transformation rules used after that are just SelIdxToRng and SelToTrivialFilter - nothing specific to HierarchyId.

The converted tree for your more complicated join example is below showing much the same

*** Converted Tree: ***
    LogOp_Project QCOL: [descendant].Id QCOL: [descendant].Hieararchy

        LogOp_Select

            LogOp_Join

                LogOp_Get TBL: HierarchyExample(alias TBL: ancestor) HierarchyExample TableID=1093578934 TableReferenceID=0 IsRow: COL: IsBaseRow1000 

                LogOp_Get TBL: HierarchyExample(alias TBL: descendant) HierarchyExample TableID=1093578934 TableReferenceID=0 IsRow: COL: IsBaseRow1001 

                ScaOp_Logical x_lopAnd

                    ScaOp_Comp x_cmpLe

                        ScaOp_Identifier QCOL: [ancestor].Hieararchy

                        ScaOp_Identifier QCOL: [descendant].Hieararchy

                    ScaOp_Comp x_cmpLe

                        ScaOp_Identifier QCOL: [descendant].Hieararchy

                        ScaOp_UdtFunction EClrFunctionType_UdtMethodDescendantLimit IsDet NoDataAccess  TI(hierarchyid,Null,Var,ML=892) 

                            ScaOp_Identifier QCOL: [ancestor].Hieararchy

            ScaOp_Comp x_cmpEq

                ScaOp_Identifier QCOL: [ancestor].Id

                ScaOp_Const TI(int,ML=4) XVAR(int,Not Owned,Value=1)

        AncOp_PrjList 

*******************
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.