CROSS APPLY produces outer join

In answer to SQL counting distinct over partition Erik Darling posted this code to work around for the lack of COUNT(DISTINCT) OVER ():

SELECT      *
FROM        #MyTable AS mt
CROSS APPLY (   SELECT COUNT(DISTINCT mt2.Col_B) AS dc
                FROM   #MyTable AS mt2
                WHERE  mt2.Col_A = mt.Col_A
                -- GROUP BY mt2.Col_A 
            ) AS ca;

The query uses CROSS APPLY (not OUTER APPLY) so why is there an outer join in the execution plan instead of an inner join?

Also why does uncommenting the group by clause result in an inner join?

I don't think the data is important but copying from that given by kevinwhat on the other question:

create table #MyTable (
Col_A varchar(5),
Col_B int
)

insert into #MyTable values ('A',1)
insert into #MyTable values ('A',1)
insert into #MyTable values ('A',2)
insert into #MyTable values ('A',2)
insert into #MyTable values ('A',2)
insert into #MyTable values ('A',3)

insert into #MyTable values ('B',4)
insert into #MyTable values ('B',4)
insert into #MyTable values ('B',5)

Summary

SQL Server uses the correct join (inner or outer) and adds projections where necessary to honour all the semantics of the original query when performing internal translations between apply and join.

The differences in the plans can all be explained by the different semantics of aggregates with and without a group by clause in SQL Server.

Details

Join vs Apply

We will need to be able to distinguish between an apply and a join:

-
Apply

The inner (lower) input of the apply is run for each row of the outer (upper) input, with one or more inner side parameter values provided by the current outer row. The overall result of the apply is the combination (union all) of all the rows produced by the parameterized inner side executions. The presence of parameters means apply is sometimes referred to as a correlated join.

An apply is always implemented in execution plans by the Nested Loops operator. The operator will have an Outer References property rather than join predicates. The outer references are the parameters passed from the outer side to the inner side on each iteration of the loop.

-
Join

A join evaluates its join predicate at the join operator. The join may generally be implemented by Hash Match, Merge, or Nested Loops operators in SQL Server.

When Nested Loops is chosen, it can be distinguished from an apply by the lack of Outer References (and usually the presence of a join predicate). The inner input of a join never references values from the outer input - the inner side is still executed once for each outer row, but inner side executions do not depend on any values from the current outer row.

For more details see my post Apply versus Nested Loops Join.


...why is there an outer join in the execution plan instead of an inner join?

The outer join arises when the optimizer transforms an apply to a join (using a rule called ApplyHandler) to see if it can find a cheaper join-based plan. The join is required to be an outer join for correctness when the apply contains a scalar aggregate. An inner join would not be guaranteed to produce the same results as the original apply as we will see.

Scalar and Vector Aggregates

• An aggregate without a corresponding GROUP BY clause is a scalar aggregate.

• An aggregate with a corresponding GROUP BY clause is a vector aggregate.

In SQL Server, a scalar aggregate will always produce a row, even if it is given no rows to aggregate. For example, the scalar COUNT aggregate of no rows is zero. A vector COUNT aggregate of no rows is the empty set (no rows at all).

The following toy queries illustrate the difference. You can also read more about scalar and vector aggregates in my article Fun with Scalar and Vector Aggregates.

-- Produces a single zero value
SELECT COUNT_BIG(*) FROM #MyTable AS MT WHERE 0 = 1;

-- Produces no rows
SELECT COUNT_BIG(*) FROM #MyTable AS MT WHERE 0 = 1 GROUP BY ();

db<>fiddle demo

Transforming apply to join

I mentioned before that the join is required to be an outer join for correctness when the original apply contains a scalar aggregate. To show why this is the case in detail, I will use a simplified example of the question query:

DECLARE @A table (A integer NULL, B integer NULL);
DECLARE @B table (A integer NULL, B integer NULL);

INSERT @A (A, B) VALUES (1, 1);
INSERT @B (A, B) VALUES (2, 2);

SELECT * FROM @A AS A
CROSS APPLY (SELECT c = COUNT_BIG(*) FROM @B AS B WHERE B.A = A.A) AS CA;

The correct result for column c is zero, because the COUNT_BIG is a scalar aggregate. When translating this apply query to join form, SQL Server generates an internal alternative that would look similar to the following if it were expressed in T-SQL:

SELECT A.*, c = COALESCE(J1.c, 0)
FROM @A AS A
LEFT JOIN
(
    SELECT B.A, c = COUNT_BIG(*) 
    FROM @B AS B
    GROUP BY B.A
) AS J1
    ON J1.A = A.A;

To rewrite the apply as an uncorrelated join, we have to introduce a GROUP BY in the derived table (otherwise there could be no A column to join on). The join has to be an outer join so each row from table @A continues to produce a row in the output. The left join will produce a NULL for column c when the join predicate does not evaluate to true. That NULL needs to be translated to zero by COALESCE to complete a correct transformation from apply.

The demo below shows how both outer join and COALESCE are required to produce the same results using join as the original apply query:

db<>fiddle demo

With the GROUP BY


...why does uncommenting the group by clause result in an inner join?

Continuing the simplified example, but adding a GROUP BY:

DECLARE @A table (A integer NULL, B integer NULL);
DECLARE @B table (A integer NULL, B integer NULL);

INSERT @A (A, B) VALUES (1, 1);
INSERT @B (A, B) VALUES (2, 2);

-- Original
SELECT * FROM @A AS A
CROSS APPLY 
(SELECT c = COUNT_BIG(*) FROM @B AS B WHERE B.A = A.A GROUP BY B.A) AS CA;

The COUNT_BIG is now a vecto

StackExchange Database Administrators Q#239865, answer score: 24