Query Optimizer and Cartesian Products

Comments 12

Share to social media

If you use the Query Optimizer (QO) enough, you will eventually run into this interesting observation: There are some situations where the QO just decides to remove a join instruction from a query, and that behavior, in turn, creates a Cartesian product (in other words, the same thing as a join but without the structured relationship – essentially a Cross Join). For instance, take the following example:

Both of the queries above return the same rows from the @tab1 table, but there is obviously a difference between the first instruction and the second. As we can easily see, the difference is the WHERE condition present in the second query (“a.a” must be equal to 1), and that is the key. The QO knows that there is a redundancy of filters – if “a.a” is equal to 1 and “a.a” is also equal to “b.a” (the JOIN condition), then obviously “b.a” will also be equal to 1. In that case, the QO removes the join condition and applies just the one “a = 1” filter to both “a” and “b” tables.

This behavior can be clearly seen when we look at the execution plan:

StmtText

Argument

select * from @tab1 a   inner join @tab1 b      on a.a = b.a   where a.a = 1

NULL

  |–Nested Loops(Inner Join)

NULL

       |–Table Scan(OBJECT:(@tab1 AS [b]), WHERE:(@tab1.[a] as
       [b].[a]=(1)))

OBJECT:(@tab1 AS [b]), WHERE:(@tab1.[a] as [b].[a]=(1))

       |–Table Scan(OBJECT:(@tab1 AS [a]), WHERE:(@tab1.[a] as
       [a].[a]=(1)))

OBJECT:(@tab1 AS [a]), WHERE:(@tab1.[a] as [a].[a]=(1))

 
Take notice of the argument column; the QO has generated just one argument to read both tables, and there is no join condition in the Nested Loops. That characterizes a Cartesian product, in that for each row of the table ‘a’, the SQL will link with all rows of the table ‘b’.

Ok, but is that a bad thing? In this case, yes. To have that particular query use a hash algorithm to make the join will certainly be better than a Loop Join. If you’re not sure about that, just look at the first query, remembering that they are both semantically equivalent. If you then look at the plan for that first query (below), you can see the QO has generated a Hash Join to link the table:

StmtText

Argument

select * from @tab1 a   inner join @tab1 b      on a.a = b.a

NULL

  |–Hash Match(Inner Join, HASH:([b].[a])=([a].[a]),
  RESIDUAL:(@tab1.[a] as [b].[a]=@tab1.[a] as [a].[a]))

HASH:([b].[a])=([a].[a]), RESIDUAL:(@tab1.[a] as
[b].[a]=@tab1.[a] as [a].[a])

       |–Table Scan(OBJECT:(@tab1 AS [b]))

OBJECT:(@tab1 AS [b])

       |–Table Scan(OBJECT:(@tab1 AS [a]))

OBJECT:(@tab1 AS [a])

If we then analyze the results of the IO and time statistics, we will see that the first query used less time and read fewer pages to return the data:

First query (Hash Join):
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 '#2E75B1C0'. Scan count 2, logical reads 4, 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 = 328 ms,  elapsed time = 19976 ms.

  
Second query (Loop Join):
Table '#2E75B1C0'. Scan count 2, logical reads 2002, 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 = 407 ms,  elapsed time = 20377 ms.

Now, if you’re clever, you’re probably thinking, “Hmmm, in that case we could just put a Hint in to force a Hash Join, yes?” Wrong (at least at this stage…). If you try this, you will receive the follow error message:

When SQL removes the join condition, it needs to make a Cartesian product, and the QO can’t do this with a Hash or Merge Join, only with a Loop join. So in this case, the logic of the QO clashes with the hint.

What you can do to fix that? Wait.

Yes, that’s all you can do. Wait for the next version or point release of SQL Server, and trust the development team to imitate Oracle. To ‘fix’ this problem, Oracle has a handy parameter, which you can look here to learn more about. There is a Connect item talking about the problem, so we should keep watching this space.

That’s all folks.

About the author

Fabiano Amorim

See Profile

Fabiano Amorim is a Data Platform MVP since 2011 that loves to conquer complex, challenging problems—especially ones that others aren’t able to solve. He first became interested in technology when his older brother would bring him to his work meetings at the age of 14. With over a decade of experience, Fabiano is well known in the database community for his performance tuning abilities. When he isn’t working, he loves to read and spend time with his family.

Fabiano Amorim's contributions