INNER JOIN vs. CROSS APPLY at EXPLAIN EXTENDED

Can anyone give me a good example of when CROSS APPLY makes a difference in those cases where INNER JOIN will work as well?

This is of course SQL Server.

A quick reminder on the terms.

INNER JOIN is the most used construct in SQL: it joins two tables together, selecting only those row combinations for which a JOIN condition is true.

This query:

SELECT  *
FROM    table1
JOIN    table2
ON      table2.b = table1.a

reads:

For each row from table1, select all rows from table2 where the value of field b is equal to that of field a

Note that this condition can be rewritten as this:

SELECT  *
FROM    table1, table2
WHERE   table2.b = table1.a

, in which case it reads as following:

Make a set of all possible combinations of rows from table1 and table2 and of this set select only the rows where the value of field b is equal to that of field a

These conditions are worded differently, but they yield the same result and database systems are aware of that. Usually both these queries are optimized to use the same execution plan.

The former syntax is called ANSI syntax, and it is generally considered more readable and is recommended to use.

However, it didn't make it into Oracle until recently, that's why there are many hardcore Oracle developers that are just used to the latter syntax.

Actually, it's a matter of taste.

To use JOINs (with whatever syntax), both sets you are joining must be self-sufficient, i. e. the sets should not depend on each other. You can query both sets without ever knowing the contents on another set.

But for some tasks the sets are not self-sufficient. For instance, let's consider the following query:

We have table1 and table2. table1 has a column called rowcount.

For each row from table1 we need to select first rowcount rows from table2, ordered by table2.id

We cannot come up with a join condition here. The join condition, should it exist, would involve the row number, which is not present in table2, and there is no way to calculate a row number only from the values of columns of any given row in table2.

That's where the CROSS APPLY can be used.

CROSS APPLY is a Microsoft's extension to SQL, which was originally intended to be used with table-valued functions (TVF's).

The query above would look like this:

SELECT  *
FROM    table1
CROSS APPLY
(
SELECT  TOP (table1.rowcount) *
FROM    table2
ORDER BY
id
) t2

For each from table1, select first table1.rowcount rows from table2 ordered by id

The sets here are not self-sufficient: the query uses values from table1 to define the second set, not to JOIN with it.

The exact contents of t2 are not known until the corresponding row from table1 is selected.

I previously said that there is no way to join these two sets, which is true as long as we consider the sets as is. However, we can change the second set a little so that we get an additional computed field we can later join on.

The first option to do that is just count all preceding rows in a subquery:

SELECT  *
FROM    table1 t1
JOIN    (
        SELECT  t2o.*,
                (
                SELECT  COUNT(*)
                FROM    table2 t2i
                WHERE   t2i.id <= t2o.id
                ) AS rn
        FROM    table2 t2o
        ) t2
ON      t2.rn <= t1.rowcount

The second option is to use a window function, also available in SQL Server since version 2005:

SELECT  *
FROM    table1 t1
JOIN    (
        SELECT  t2o.*, ROW_NUMBER() OVER (ORDER BY id) AS rn
        FROM    table2 t2o
        ) t2
ON      t2.rn <= t1.rowcount

This function returns the ordinal number a row would have, be the ORDER BY condition used in the function applied to the whole query.

This is essentially the same result as the subquery used in the previous query.

Now, let's create the sample tables and check all these solutions for efficiency:

SET NOCOUNT ON
GO
DROP TABLE [20090716_cross].table1
DROP TABLE [20090716_cross].table2
DROP SCHEMA [20090716_cross]
GO
CREATE SCHEMA [20090716_cross]
CREATE TABLE table1
(
id INT NOT NULL PRIMARY KEY,
row_count INT NOT NULL
)
CREATE TABLE table2
(
id INT NOT NULL PRIMARY KEY,
value VARCHAR(20) NOT NULL
)
GO
BEGIN TRANSACTION
DECLARE @cnt INT
SET @cnt = 1
WHILE @cnt <= 100000
BEGIN
        INSERT
        INTO    [20090716_cross].table2 (id, value)
        VALUES  (@cnt, 'Value ' + CAST(@cnt AS VARCHAR))
        SET @cnt = @cnt + 1
END
INSERT
INTO    [20090716_cross].table1 (id, row_count)
SELECT  TOP 5
        id, id % 2 + 1
FROM    [20090716_cross].table2
ORDER BY
        id
COMMIT
GO

table2 contains 100,000 rows with sequential ids.

table1 contains the following:

id	row_count
1	2
2	1
3	2
4	1
5	2

Now let's run the first query (with COUNT):

SELECT  *
FROM    [20090716_cross].table1 t1
JOIN    (
SELECT  t2o.*,
(
SELECT  COUNT(*)
FROM    [20090716_cross].table2 t2i
WHERE   t2i.id <= t2o.id
                ) AS rn
        FROM    [20090716_cross].table2 t2o
        ) t2
ON      t2.rn <= t1.row_count
ORDER BY
        t1.id, t2.id

id	row_count	id	value	rn
1	2	1	Value 1	1
1	2	2	Value 2	2
2	1	1	Value 1	1
3	2	1	Value 1	1
3	2	2	Value 2	2
4	1	1	Value 1	1
5	2	1	Value 1	1
5	2	2	Value 2	2
8 rows fetched in 0.0000s (498.4063s)

Table 'table1'. Scan count 2, logical reads 200002, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0. 
Table 'Worktable'. Scan count 100000, logical reads 8389920, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0. 
Table 'Worktable'. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0. 
Table 'table2'. Scan count 4, logical reads 1077, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0. 

SQL Server Execution Times:
   CPU time = 947655 ms,  elapsed time = 498385 ms.

This query, as was expected, is very unoptimal. It runs for more than 500 seconds.

Here's the query plan:

SELECT
  Sort
    Compute Scalar
      Parallelism (Gather Streams)
        Inner Join (Nested Loops)
          Inner Join (Nested Loops)
            Clustered Index Scan ([20090716_cross].[table2])
            Compute Scalar
              Stream Aggregate
                Eager Spool
                  Clustered Index Scan ([20090716_cross].[table2])
          Clustered Index Scan ([20090716_cross].[table1])

For each row selected from table2, it counts all previous rows again and again, never recording the intermediate result. The complexity of such an algorithm is O(n^2), that's why it takes so long.

Let's run the second query, which uses ROW_NUMBER():

SELECT  *
FROM    [20090716_cross].table1 t1
JOIN    (
SELECT  t2o.*, ROW_NUMBER() OVER (ORDER BY id) AS rn
FROM    [20090716_cross].table2 t2o
) t2
ON      t2.rn <= t1.row_count
ORDER BY
        t1.id, t2.id

id	row_count	id	value	rn
1	2	1	Value 1	1
1	2	2	Value 2	2
2	1	1	Value 1	1
3	2	1	Value 1	1
3	2	2	Value 2	2
4	1	1	Value 1	1
5	2	1	Value 1	1
5	2	2	Value 2	2
8 rows fetched in 0.0006s (0.5781s)

Table 'Worktable'. Scan count 1, logical reads 214093, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0. 
Table 'table2'. Scan count 1, logical reads 522, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0. 
Table 'table1'. Scan count 1, logical reads 2, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0. 

SQL Server Execution Times:
   CPU time = 578 ms,  elapsed time = 579 ms.

This is much faster, only 0.5 ms.

Let's look into the query plan:

SELECT
  Inner Join (Nested Loops)
    Clustered Index Scan ([20090716_cross].[table1])
  Lazy Spool
    Sequence Project (Compute Scalar)
      Compute Scalar
        Segment
          Clustered Index Scan ([20090716_cross].[table2])

This is much better, since this query plan keeps the intermediate results while calculating the ROW_NUMBER.

However, it still calculates ROW_NUMBERs for all 100,000 of rows in table2, then puts them into a temporary index over rn created by Lazy Spool, and uses this index in a nested loop to range the rns for each row from table1.

Calculating and indexing all ROW_NUMBERs is quite expensive, that's why we see 214,093 logical reads in the query statistics.

Finally, let's try a CROSS APPLY:

SELECT  *
FROM    [20090716_cross].table1 t1
CROSS APPLY
(
SELECT  TOP (t1.row_count) *
FROM    [20090716_cross].table2
ORDER BY
id
) t2
ORDER BY
t1.id, t2.id

id	row_count	id	value
1	2	1	Value 1
1	2	2	Value 2
2	1	1	Value 1
3	2	1	Value 1
3	2	2	Value 2
4	1	1	Value 1
5	2	1	Value 1
5	2	2	Value 2
8 rows fetched in 0.0004s (0.0008s)

Table 'table2'. Scan count 5, logical reads 10, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0. 
Table 'table1'. Scan count 1, logical reads 2, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0. 

SQL Server Execution Times:
   CPU time = 0 ms,  elapsed time = 1 ms.

This query is instant, as it should be.

The plan is quite simple:

SELECT
  Inner Join (Nested Loops)
    Clustered Index Scan ([20090716_cross].[table1])
    Top
      Clustered Index Scan ([20090716_cross].[table2])

For each row from table1, it just takes first row_count rows from table2. So simple and so fast.

Summary:

While most queries which employ CROSS APPLY can be rewritten using an INNER JOIN, CROSS APPLY can yield better execution plan and better performance, since it can limit the set being joined yet before the join occurs.

Written by Quassnoi

July 16th, 2009 at 11:00 pm

Posted in SQL Server

48 Responses to 'INNER JOIN vs. CROSS APPLY'

Subscribe to comments with RSS

Extremely helpful, thank-you.

Dave

1 Feb 13 at 01:36
In the first two alternative queries you post, you have:
t1.rowcount = t2.rn

I think you meant >=, otherwise the result is totally different from the output query

mas

7 Mar 13 at 01:27
@mas: thanks, corrected.

Quassnoi

7 Mar 13 at 14:02
Thanks very much for this explanation of INNER JOIN vs. CROSS APPLY. I finally get it — the key idea (for me) being “The sets here are not self-sufficient: the query uses values from table1 to define the second set, not to JOIN with it.”

Sam

12 May 13 at 22:58
“This is much faster, only 0.5 ms.”

Did you mean to write “0.5 s”? As shown in the screenshots.

theghostofc

13 Aug 13 at 12:11
You mister have just optimized my query from 1200 ms to 10 ms. THANK YOU!

I was using rowNumber over Name column but joining result over id and that was killing MSSQL. If rowNumber was also over Id everything was fine.

Milan

5 Sep 13 at 13:09
Thanks for the detailed explanation, this CROSS APPLY is becoming an interview question now but still difficult to find a good explanation, even worse when comparing with other execution plans like our beloved JOIN. THanks Again.

Pap Perlada

10 Jun 14 at 00:15
Please go through and correct your grammar. I find this to difficult to read. I’m at my fourth mistake and really these are big mistakes. No idea what you are trying to communicate.

Paul

13 Oct 14 at 19:20
@Paul: sorry, English is not my first language.

Quassnoi

13 Oct 14 at 19:34
This explanation is exactly what I was looking for.

Thank you very much!

Dmitriy

28 Oct 14 at 20:06
It might be worth mentioning that the SQL standard defines the same operator. It’s called LATERAL JOIN there.

I ran this example on Postgres (9.4) and it pretty much shows the same behavior with the exception that the first query is really, really slow on Postgres (12 minutes with just 25.000 rows instead of 100.000).

But the difference between the version with a window function and the lateral join is pretty much the same as with your example (62ms vs. 0.2ms with 25.000 rows)

Hans

8 Jan 15 at 15:01
Finally an explanation I can easily follow :) Finally I am not afraid anymore when I see a statement involving CROSS APPLY (including those pesky Xml – .nodes() operations…)

Thank you very much!

Wolfgang

3 Apr 15 at 11:41
Hello Quassnoi,

Thank you very much for so clear and simple explanation. Queries based on CROSS APPLY are more readable. You highlighted how performance boosts or, at least, response time. That crucial when you have millions of records and complex table relationships.

BTW, please do not apologize for your language. Your message is understandable.

@Paul, I guess this is not a literature forum. “correct your grammar”, you said … Please read your 4 sentences and you will find some inconsistencies. The fact that somebody allocated time to model an idea, searches, creates examples, measures performance and writes an article is admirable, furthermore if it has been published in a second language.

Regards, Alberto

Alberto Villar

2 Jul 15 at 11:15
hi , its realy good article

osman

10 Jul 15 at 02:51
@osman: thanks!

Quassnoi

10 Jul 15 at 03:19
Very well explained. Very very impressive.

Marc-Olivier

25 Aug 15 at 15:43
Hi Quassnoi,

are there scenarios where a statement can be written with either JOIN or APPLY, but selecting JOIN instead of APPLY would yield a much better execution plan, resulting in better performance?
In other words, are there scenarios where APPLY should be avoided?

Thanks,
Paul

Paul

27 Aug 15 at 00:22
@Paul: APPLY is more powerful.

You can always rewrite JOIN as APPLY:

a JOIN b ON b.x = a.x

is the same as

a CROSS APPLY (SELECT * FROM b WHERE b.x = a.x) b

SQL Server does a great job at spotting these, and those two queries will most probably yield similar plans.

If you change the query semantics, like using APPLY with TOP vs. JOIN with ROW_NUMBER() (as in the article), then either query might or might not be efficient.

So if ROW_NUMBER() proves to be the more efficient solution, then JOIN (with ROW_NUMBER) would be better than APPLY (with TOP).

But you can always use ROW_NUMBER() with APPLY, if you want. SQL Server would treat it the same as JOIN with ROW_NUMBER.

Quassnoi

27 Aug 15 at 01:26
Clearly a great article… thanks.

@Paul: try using some punctuation and check your spelling… if you want others to understand what you write.

Gabriel Badea

6 Nov 15 at 20:23
Great article Quassnoi.

Vivek

27 Nov 15 at 05:44
@GabrielBadea, @vivek: thanks!

Quassnoi

27 Nov 15 at 18:43
Just a little info.

Both syntax for join are ANSI compliant.

The INNER JOIN syntax is a newer ANSI Spec.

I used to say the same thing that joining in the where clause was not ANSI standard, until someone shared with me.

Nicely done. Write more, you’re good at it.

Ben

Ben

24 Feb 16 at 06:22
@Paul, too difficult*

Qualcuno

23 Mar 16 at 15:46
Very well done. I’ve had only a fuzzy understanding of CROSS APPLY before reading your article – now I’m going in the right direction. I also applaud the painstaking job with formatting and practical consideration of code with “sourceprint”. A lot of SE bloggers don’t go to this trouble.

Only a slight typo above:

“Let’s run he second query, which uses ROW_NUMBER():”

should read:

“Let’s run the second query, which uses ROW_NUMBER():”

JCampbell

1 Apr 16 at 16:07
Apply or Lateral Join should be used when injecting a function into a Join (in the same way that its used when “joining” to a table valued function).

Using it in other circumstances will lead to confused code and increased maintenance costs

edward green

18 Jul 16 at 11:21
Sorry I am new to T-SQL. Can I ask what means by table2. table1? I thought only database name can be put in front of a table, but not a table in front of another table…Can you please help me to understand this? Thank you!

May

19 Dec 16 at 22:39
@may: We have table1 and table2. Period. table1 has a column called rowcount.

Quassnoi

20 Dec 16 at 11:52
@Quassnoi: Thank you very much for the clarification!

May

20 Dec 16 at 17:08
SELECT TOP (t1.row_count) * ….

I think that before “*” is needed a “,”

ice72

8 Jan 17 at 12:35
@ice72: TOP is a clause, not a function. This is older SQL Server‘s version of FETCH NEXT / OFFSET. This basically means “give me all fields of the first t1.rowcount rows”, so no comma is needed.

Quassnoi

8 Jan 17 at 12:49
I’m here in 2017 taking a look at this great post while trying to undersand 2nd course of Microsoft’s Data Science Certification. It did help a lot.

adolfo

25 Jun 17 at 22:07
Excelente artículo.

Boris Ivancho

5 Sep 17 at 23:41
Flawless article,thanks

erhan

18 Jan 18 at 17:16
I’ve struggled for a while really understanding the difference between apply and join. This article finally helped me get it. Thank you for taking the time to write this up.

Joe

14 Mar 18 at 18:36
Thanks!
Hasagi!

Yasuo

28 May 18 at 06:55
This is really helpful. Thanks.
Can you please point me to any execution plan related article that you have written?

Pradip Biswas

10 Sep 18 at 07:58
Very Well Explained. Thank you

Raja

28 Sep 18 at 10:00
I am not afraid of APPLY anymore. Thank you very much for this clear and simple explanation. While I am writing this, my JOIN is still executing lol.

Sanya

5 May 19 at 14:24
Thank you for this helpful knowledge-sharing.

Bogdan

23 Aug 19 at 12:40
nice one,got a clear idea,thanks for your efforts @Quassnoi.

vinothini

27 Jul 20 at 19:57
I am pretty sure you mean <= rather than <=. In SQL, &lt is not an operator and the semicolon ends a SQL statement, thus never reaching the comparison.

NotTelling

25 Feb 21 at 00:19
@NotTelling: a botched code plugin upgrade messed up code on my pages some time ago. Thanks for the heads up!

Quassnoi

25 Feb 21 at 00:57
This is an excellent article. Do you have other topics related to optimizations? Thank you!

Adriana

20 Oct 21 at 12:13
Great Explanation

yomf

17 Mar 22 at 11:43
This is great, it helped me understand the difference, many thanks! What program have you used to test the performance?

Tomsk

12 Apr 22 at 13:20
Thanks for good explanation.

One small doubt.
Is there any performance difference in the following two formats of CROSS APPLY?

1) CROSS APPLY (SELECT * FROM b WHERE b.x = a.x) b

2) CROSS APPLY (SELECT col1, col2 FROM b WHERE b.x = a.x) b

Because in most of the cases we don’t all fields from CROSS APPLY (SELECT * FROM …..)

Ashish

25 Aug 22 at 15:57
@Ashish: in this particular aspect the SQL Server optimizer is quite smart. If you don’t end up using all fields from CROSS APPLY in your outermost query, the optimizer will optimize the query as if you had never requested them. In other words, these two queries: SELECT b.field1, b.field2 FROM a CROSS APPLY (SELECT * FROM b) b and SELECT b.field1, b.field2 FROM a CROSS APPLY (SELECT field1, field2 FROM b) b will yield the same plan.

Quassnoi

25 Aug 22 at 19:59
Considering the performance.

…. should I replace all INNER JOIN with CROSS APPLY and all LEFT JOIN with OUTER APPLY everywhere straightforward?

…. then question remains, when to use INNER JOIN and LEFT JOIN?

Ashish

12 Oct 22 at 11:17

EXPLAIN EXTENDED