Constant Scan applying

Question

This question is a continuation of optimizer behavior exploration in regards to VALUES construct started here and here. I want to ask about VALUES and APPLY this time.

Using CROSS APPLY to alias an expression that needs to be referenced in various parts of a query is the common pattern. Such as, for example:

CREATE TABLE #data (N int);
INSERT INTO #data VALUES (5), (4), (3), (2), (1);

SELECT d.N, c.[Square]
FROM #data d
    CROSS APPLY (VALUES (d.N * d.N)) c([Square])
WHERE c.[Square] BETWEEN 1 AND 10
ORDER BY c.[Square];

I myself always use CROSS APPLY in such cases, but sometimes I encounter such expressions wrapped into inline-TVF and OUTER APPLY-ed. So, out of curiosity, I changed CROSS to OUTER in the exampling query

SELECT d.N, c.[Square]
FROM #data d
    OUTER APPLY (VALUES (d.N * d.N)) c([Square])
WHERE c.[Square] BETWEEN 1 AND 10
ORDER BY c.[Square];

to check if it matters.

To my understanding, semantics of CROSS APPLY and OUTER APPLY are equal in this case, since VALUES (d.N * d.N) always returns exactly one row for each row of d. My expectation was that the optimizer would produce identical execution plans for both (likewise it changes left join to inner sometimes). This is not the case however.

The OUTER modification has an execution plan resembling its written form. It has APPLY implemented as Nested Loops with expression computed in Constant Scan on the inner side. Then Filter is there to address WHERE predicate and Sort to address ORDER BY finally.

Whereas the execution plan of the CROSS modification looks as if there were no APPLY at all and the expression has been substituted instead of its alias. It has WHERE predicate pushed to Table Scan. Then there is the Compute Scalar performing expression computation, and finally Sort as well.

Why doesn't the optimizer want to get rid of APPLY in case of OUTER, like it did with CROSS? It has all the information in hands to conclude that VALUES produces exactly one row per each table row.

I understand that the answer can be short like "It could in theory, but that's what current implementation is". So, to inspire on how to construct a more thorough answer, I have additional questions (going along the way) regarding optimization paths of these two queries.

In the remaining parts of the question, shortened queries are used:

SELECT d.N, c.[Square]
FROM #data d
    CROSS APPLY (VALUES (d.N * d.N)) c([Square]);

SELECT d.N, c.[Square]
FROM #data d
    OUTER APPLY (VALUES (d.N * d.N)) c([Square]);

They lack WHERE and ORDER BY. Despite that, they have all the necessary attributes, and have different execution plans as well.

CROSS APPLY

Let's start with the Input Tree (trace flag 8606). At this point, the logical tree corresponds well to the written form of the query.

*** Input Tree: ***
LogOp_Project QCOL: [d].N COL: Expr1002 
    LogOp_Apply (x_jtInner)
        LogOp_Get TBL: #data(alias TBL: d)
        LogOp_Project
            LogOp_ConstTableGet (1) [empty]
            AncOp_PrjList 
                AncOp_PrjEl COL: Expr1002 
                    ScaOp_Arithmetic x_aopMult
                        ScaOp_Identifier QCOL: [d].N
                        ScaOp_Identifier QCOL: [d].N
    AncOp_PrjList 
*******************

Then, before entering the simplification stage, an event named projection pulling happens. Optimizer pulls scalar expression computation above Apply

*** Before Simplification Tree (not visible with TF 8606) ***
LogOp_Project QCOL: [d].N COL: Expr1002 
    LogOp_Apply (x_jtInner)
        LogOp_Get TBL: #data(alias TBL: d)
        LogOp_ConstTableGet (1) [empty]
    AncOp_PrjList 
        AncOp_PrjEl COL: Expr1002 
            ScaOp_Arithmetic x_aopMult
                ScaOp_Identifier QCOL: [d].N
                ScaOp_Identifier QCOL: [d].N
*******************

What is the aim of pulling scalar expression above Apply? What are the things that inhibit pulling naturally, and is there a way to suppress it by force?

After that simplification stage begins and among the first rules being applied (trace flag 8621) PrjApplyHandler changes Apply to Join

***** Rule applied: Prj APPLY stack -> Prj Join stack
LogOp_Project
    LogOp_Join
        LogOp_Get TBL: #data(alias TBL: d)
        LogOp_ConstTableGet (1) [empty]
        ScaOp_Const TI(bit,ML=1) XVAR(bit,Not Owned,Value=1)
    AncOp_PrjList 
        ...

If being implemented at this stage, the execution plan of the query would look as follows:

Then SimplifyJoinWithCTG rule gets into action. It removes cross join to empty single row LogOp_ConstTableGet leaving the LogOp_Get only

***** Rule applied: Join/LSJ(ConstTableGet(1),x0,True) --> x0
    LogOp_Get TBL: #data(alias TBL: d)

So, after all simplifications, the logical tree becomes

*** Simplified Tree: ***
LogOp_Project
    LogOp_Get TBL: #data(alias TBL: d)
    AncOp_PrjList 
        AncOp_PrjEl COL: Expr1002 
            ScaOp_Arithmetic x_aopMult
                ScaOp_Identifier QCOL: [d].N
                ScaOp_Identifier QCOL: [d].N
*******************

And then it flows, unchanged, up until being implemented trivially as

Disabling the SimplifyJoinWithCTG rule leads to the execution plan with scalar expression computation pushed below the join, but to its outer side

(this plan has JoinCommute disabled also).

What is the aim of pushing the scalar expression below the join after it has been pulled above before?

OUTER APPLY

The Input Tree for OUTER APPLY modification is almost identical to that of the CROSS APPLY. The only difference is that LogOp_Apply has x_jtLeftOuter type

*** Input Tree: ***
LogOp_Project QCOL: [d].N COL: Expr1002 
    LogOp_Apply (x_jtLeftOuter)
        LogOp_Get TBL: #data(alias TBL: d)
        LogOp_Project
            LogOp_ConstTableGet (1) [empty]
            AncOp_PrjList 
                AncOp_PrjEl COL: Expr1002 
                    ScaOp_Arithmetic x_aopMult
                        ScaOp_Identifier QCOL: [d].N
                        ScaOp_Identifier QCOL: [d].N
    AncOp_PrjList 
*******************

Starting from this point, things are very different for OUTER APPLY. The first difference is that projection pulling does not happen for scalar expression in this case. Why doesn't the optimizer pull the scalar expression for OUTER APPLY?

The second difference is that the optimizer does not change Apply to Join at simplification stage. Actually, even in the Output Tree (trace flag 8607), it is presented as PhyOp_Apply, and join appears as post-optimization only.

Despite that, RedundantApplyOJ and ApplyHandler simplification rules are applied

there are no signs of it in the Simplified Tree

*** Simplified Tree: ***
LogOp_Apply (x_jtLeftOuter)
    LogOp_Get TBL: #data(alias TBL: d)
    LogOp_ConstTableGet (1) COL: Expr1002 
        ScaOp_Arithmetic x_aopMult
            ScaOp_Identifier QCOL: [d].N
            ScaOp_Identifier QCOL: [d].N
*******************

Also, SimplifyJoinWithCTG rule is not even considered for OUTER APPLY (meaning that it has no chance to match or not match).

Then, after all simplifications are done, the logical tree flows, unchanged, up until being implemented at Quick Plan stage as

Why didn't the optimizer try to change Apply to Join at simplification stage for OUTER APPLY like it did it for CROSS APPLY? What RedundantApplyOJ and ApplyHandler rules do during simplification in this case? Are they something like A*1=A (meaning that nothing is changed effectively), or are they just change some properties of the logical tree nodes without affecting tree shape?

Answer 1

The Optimiser doesn’t know what the data is until the query is running. So it has to prepare for anything.

If you make the queries simpler and put 10 rows in the #data table, it becomes clearer that the FILTER guesstimates for the OUTER APPLY query are 50% of the #data table row-count.

The results of the OUTER APPLY c.[Square] result-set appears Non-deterministic.

APPLY will always use a Nested Loop unless it is safe to do something else. In this case it isn’t safe because the content is unknown and an OUTER APPLY can potentially produce NULL results for c.[Square].

Even if you set #data to (N int NOT NULL) the Nested Loop is still used and the Estimates are wrong because it’s the OUTER APPLY that is invisible to the Optimiser.

Note: Any filters on c.[Square] may not be NULL sensitive: “NULL <> 5” can produce unwanted results.

Here’s an example with #data containing 10 integers.

The Optimiser Estimates 5 rows will be returned from the OUTER APPLY

IF OBJECT_ID('tempdb..#data') IS NOT NULL DROP TABLE #data
CREATE TABLE #data (N int);

INSERT INTO #data
SELECT TOP 10 ROW_NUMBER() OVER (PARTITION BY NULL ORDER BY Object_id) FROM sys.columns

SELECT d.N, c.[Square]
FROM #data d
    CROSS APPLY (VALUES (d.N)) c([Square])
WHERE c.[Square] <> 5;

SELECT d.N, c.[Square]
FROM #data d
    OUTER APPLY (VALUES (d.N)) c([Square])
WHERE c.[Square] <> 5;

Hopefully there's someone who knows more about OUTER APPLY internals that can explain why the Optimiser is making blind guesses.....