{"id":717,"date":"2009-10-22T00:00:00","date_gmt":"2009-10-22T00:00:00","guid":{"rendered":"https:\/\/test.simple-talk.com\/uncategorized\/query-optimizer-and-cartesian-products\/"},"modified":"2021-09-29T16:22:03","modified_gmt":"2021-09-29T16:22:03","slug":"query-optimizer-and-cartesian-products","status":"publish","type":"post","link":"https:\/\/www.red-gate.com\/simple-talk\/databases\/sql-server\/t-sql-programming-sql-server\/query-optimizer-and-cartesian-products\/","title":{"rendered":"Query Optimizer and Cartesian Products"},"content":{"rendered":"

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:<\/p>\n

USE tempdb\r\nGO\r\nDECLARE @tab1 TABLE(a INT)\r\nINSERT INTO @tab1\r\n\u00a0\u00a0SELECT TOP 1000 1\r\n\u00a0\u00a0FROM sysobjects b, sysobjects a\r\nSET STATISTICS io ON\r\nSET STATISTICS time ON\r\nSELECT * \r\n\u00a0\u00a0FROM @tab1 a\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0INNER JOIN @tab1 b\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0ON a.a = b.a\r\nSELECT * \r\n\u00a0\u00a0FROM @tab1 a\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0INNER JOIN @tab1 b\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0ON a.a = b.a\r\n\u00a0\u00a0WHERE a.a = 1\r\nSET STATISTICS io OFF\r\nSET STATISTICS time OFF <\/pre>\n
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<\/em>” must be equal to 1), and that<\/em> is the key. The QO knows<\/em> that there is a redundancy of filters – if “a.a<\/em>” is equal to 1 and “a.a<\/em>” is also<\/em> equal to “b.a<\/em>” (the JOIN condition), then obviously “b.a<\/em>” 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<\/em>” and “b<\/em>” tables.<\/p>\n
This behavior can be clearly seen when we look at the execution plan:<\/p>\n\n\n\n\n\n\n\n
\n
StmtText <\/strong><\/p>\n<\/td>\n
\n
Argument <\/strong><\/p>\n<\/td>\n<\/tr>\n
\n
select * from @tab1 a\u00a0\u00a0 inner join @tab1 b\u00a0\u00a0\u00a0\u00a0\u00a0 on a.a = b.a\u00a0\u00a0 where a.a = 1<\/p>\n<\/td>\n
\n
NULL<\/p>\n<\/td>\n<\/tr>\n
\n
\u00a0 |–Nested Loops(Inner Join)<\/p>\n<\/td>\n
\n
NULL<\/p>\n<\/td>\n<\/tr>\n
\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 |–Table Scan(OBJECT:(@tab1 AS [b]), WHERE:(@tab1.[a] as
\n \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 [b].[a]=(1)))<\/p>\n<\/td>\n
\n
OBJECT:(@tab1 AS [b]), WHERE:(@tab1.[a] as [b].[a]=(1))<\/p>\n<\/td>\n<\/tr>\n
\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 |–Table Scan(OBJECT:(@tab1 AS [a]), WHERE:(@tab1.[a] as
\n \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 [a].[a]=(1)))<\/p>\n<\/td>\n
\n
OBJECT:(@tab1 AS [a]), WHERE:(@tab1.[a] as [a].[a]=(1))<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
\u00a0 
\n 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’.<\/p>\n
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:<\/p>\n\n\n\n\n\n\n\n
\n
StmtText<\/strong><\/p>\n<\/td>\n
\n
Argument<\/strong><\/p>\n<\/td>\n<\/tr>\n
\n
select * from @tab1 a\u00a0\u00a0 inner join @tab1 b\u00a0\u00a0\u00a0\u00a0\u00a0 on a.a = b.a<\/p>\n<\/td>\n
\n
NULL<\/p>\n<\/td>\n<\/tr>\n
\n
\u00a0 |–Hash Match(Inner Join, HASH:([b].[a])=([a].[a]),
\n \u00a0 RESIDUAL:(@tab1.[a] as [b].[a]=@tab1.[a] as [a].[a]))<\/p>\n<\/td>\n
\n
HASH:([b].[a])=([a].[a]), RESIDUAL:(@tab1.[a] as
\n [b].[a]=@tab1.[a] as [a].[a])<\/p>\n<\/td>\n<\/tr>\n
\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 |–Table Scan(OBJECT:(@tab1 AS [b]))<\/p>\n<\/td>\n
\n
OBJECT:(@tab1 AS [b])<\/p>\n<\/td>\n<\/tr>\n
\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 |–Table Scan(OBJECT:(@tab1 AS [a]))<\/p>\n<\/td>\n
\n
OBJECT:(@tab1 AS [a])<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
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:<\/p>\n
First query (Hash Join):<\/strong> 
\n 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. 
\nTable '#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. 
\n\u00a0 
\nSQL Server Execution Times: 
\n\u00a0\u00a0 CPU time = 328 ms,\u00a0 elapsed time = 19976 ms. <\/code>
\n \u00a0\u00a0 
\n Second query (Loop Join):<\/strong> 
\n 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. 
\n\u00a0 
\nSQL Server Execution Times: 
\n\u00a0\u00a0 CPU time = 407 ms,\u00a0 elapsed time = 20377 ms.<\/code><\/p>\n
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?<\/em>” Wrong (at least at this stage…). If you try this, you will receive the follow error message:<\/p>\n
SELECT * \r\n\u00a0\u00a0FROM @tab1 a\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0INNER JOIN @tab1 b\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0ON a.a = b.a\r\n\u00a0\u00a0WHERE a.a = 1\r\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0OPTION(hash JOIN)\r\n\r\nMsg 8622, Level 16, State 1, Line 20 \r\nQuery processor could not produce a query plan because of the hints defined in this query. Resubmit the query without specifying any hints and without using SET FORCEPLAN.<\/pre>\n
When SQL removes the join condition, it needs<\/em> 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.<\/p>\n
What you can do to fix that? Wait.<\/p>\n
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<\/a> to learn more about. There is<\/em> a Connect<\/a> item talking about the problem, so we should keep watching this space.<\/p>\n
That’s all folks.<\/p>\n","protected":false},"excerpt":{"rendered":"
In his continuing quest to bring a deeper understanding of Query Optimizer to the world at large, Fabiano takes a moment to point out a potential pitfall you may encounter. A light read, but one worth perusing.…<\/p>\n","protected":false},"author":65554,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[143531],"tags":[4178,5076,4150,4252],"coauthors":[6809],"class_list":["post-717","post","type-post","status-publish","format-standard","hentry","category-t-sql-programming-sql-server","tag-bi","tag-query-optimizer","tag-sql","tag-t-sql-programming"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/717","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/users\/65554"}],"replies":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/comments?post=717"}],"version-history":[{"count":5,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/717\/revisions"}],"predecessor-version":[{"id":75328,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/717\/revisions\/75328"}],"wp:attachment":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/media?parent=717"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/categories?post=717"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/tags?post=717"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/coauthors?post=717"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}