While testing the optimizer transformations on disjunctive subqueries, I created by chance boundary conditions where I observed that the optimizer had not chosen\u00a0the plan with the lowest cost. More precisely, the optimizer discarded the cheaper Nested Loop join and opted for the Hash Join which had a higher cost. In particular, the phenomena happens when the index on the join column of the inner table is missing, and the inner table contains only 1 or 0 records. Although these conditions are less likely on a live system and would have only a minor impact on the query response time, I decided to find out the reason for such behaviour. In fact, elaborating the conditions under which the optimizer starts to change its behavioral patterns almost always provides interesting insights into its internal functioning. I tested the behaviour on SQL Server and Oracle.<\/p>\n
First, I’ll create one big and one small table :<\/p>\n
SELECT TOP (1000000) \r\n id = CONVERT(INT, ROW_NUMBER() OVER (ORDER BY s1.[object_id])),\r\n a = CONVERT(INT, ROW_NUMBER() OVER (ORDER BY s1.[object_id]))\r\nINTO t_large\r\nFROM sys.all_objects AS s1 CROSS JOIN sys.all_objects AS s2\r\nOPTION (MAXDOP 1);\r\n\r\ncreate table t_small (b integer,c integer) ;\r\n\r\ninsert into t_mall values (1,1) ;<\/code><\/pre>\nThe query to populate the large table with numbers<\/a> is used by courtesy of Aaron Bertrand.
\nNext, I’ll execute the\u00a0 query which joins both of the tables and observe the execution plan. The following output is produced by running the queries with set showplan_all on<\/em>. For the sake of\u00a0simplicity, I removed the irrelevant information leaving only the operation and its cost.<\/p>\nselect a from t_large l join t_small s on l.id = s.b ;\r\n\r\nselect a from t_large l join t_small s on l.id = s.b \t10.49783<\/span>\t\r\n |--Hash Match<\/span>(Inner Join, HASH:([s].[b])=([l].[id]), RESIDUAL:([master].[dbo].[t_small].[b] as [s].[b]=[master].[dbo].[t_large].[id] as [l].[id]))\t10.49783\t\r\n |--Table Scan(OBJECT:([master].[dbo].[t_small] AS [s]))\t0.0032831\t\r\n |--Table Scan(OBJECT:([master].[dbo].[t_large] AS [l]))\t3.94106\t<\/code><\/pre>\nThe optimizer has chosen Hash Join and estimated the total cost to 10.49783<\/span>:<\/p>\nLet’s take a look at the plan cost for Nested Loop Join which can be enforced by hint:<\/p>\n
select a from t_large l join t_small s on l.id = s.b option (loop join<\/span>);\r\n\r\nselect a from t_large l join t_small s on l.id = s.b option (loop join);\t8.424343<\/span>\r\n |--Nested Loops<\/span>(Inner Join, WHERE:([master].[dbo].[t_small].[b] as [s].[b]=[master].[dbo].[t_large].[id] as [l].[id]))\t8.424343\t\r\n |--Table Scan(OBJECT:([master].[dbo].[t_small] AS [s]))\t0.0032831\t\r\n |--Table Scan(OBJECT:([master].[dbo].[t_large] AS [l]))\t3.94106\t<\/code><\/pre>\nIn this case, as expected, the cost of the Nested Loop is slightly lower than the one of the Hash Join; the Hash Join namely has an overhead of preparing the hash table. This can be confirmed by the runtime statistics, which were switched on by the following directives:<\/p>\n
SET STATISTICS IO ON\r\nSET STATISTICS TIME ON<\/code><\/pre>\nNested Loop:<\/p>\n
Table 't_large'. Scan count 1, logical reads 3832<\/span>, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.\r\nTable 't_small'. Scan count 1, logical reads 1, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.\r\n\r\n SQL Server Execution Times:\r\n CPU time = 125 ms<\/span>, elapsed time = 119 ms.\r\n<\/code><\/pre>\nHash Join:<\/p>\n
Table 't_large'. Scan count 1, logical reads 3832<\/span>, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.\r\nTable 't_small'. Scan count 1, logical reads 1, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.\r\n\r\n SQL Server Execution Times:\r\n CPU time = 172 ms<\/span>, elapsed time = 159 ms.\r\n<\/code><\/pre>\nWe can make two observations. One is, that the inner table t_large<\/em> was scanned only once in both cases. The other is, that the Hash Join spent slightly more time on CPU for, as already mentioned, building the hash table. In conclusion, the calculated costs correspond well to the reality, but at the end, the Nested Loop was not considered, unless it was enforced by the hint.<\/p>\nSo, the question is, why did the optimizer ignore the nested loop?<\/p>\n
Heuristics<\/h1>\n
To answer this question, we’ll trace the transformation rules which were applied by the optimizer during the query optimization. This can be done by comparing the content of the dm_exec_query_transformation_stats<\/em> DMV just before and immediately after the query compilation. The query transformations for which the succeeded<\/em> column increased, have been considered as alternatives. The exact technique for getting this information for a particular query is described in the book Inside the SQL Server Query Optimizer<\/a> by Benjamin Nevarez. I publish the queries by courtesy of the author:<\/p>\nGO\r\nSELECT *\r\nINTO before_query_transformation_stats\r\nFROM sys.dm_exec_query_transformation_stats\r\nGO\r\nSELECT *\r\nINTO after_query_transformation_stats\r\nFROM sys.dm_exec_query_transformation_stats\r\nGO\r\nDROP TABLE after_query_transformation_stats\r\nDROP TABLE before_query_transformation_stats\r\nGO\r\nSELECT *\r\nINTO before_query_transformation_stats\r\nFROM sys.dm_exec_query_transformation_stats\r\nGO\r\nselect a from t_large l join t_small s on l.id = s.b \r\nOPTION (RECOMPILE)\r\nGO\r\nSELECT *\r\nINTO after_query_transformation_stats\r\nFROM sys.dm_exec_query_transformation_stats\r\nGO\r\nSELECT a.name, (a.promised - b.promised) as promised\r\nFROM before_query_transformation_stats b\r\nJOIN after_query_transformation_stats a\r\nON b.name = a.name\r\nWHERE b.succeeded <> a.succeeded\r\nDROP TABLE before_query_transformation_stats\r\nDROP TABLE after_query_transformation_stats\r\n<\/code><\/pre>\nHere are the joins that are considered when we don’t specify the hint:<\/p>\n
name\tpromised\r\n...\r\nJNtoHS\t2\r\nJNtoSM\t2\r\n...\r\n<\/code><\/pre>\nIt can be seen, that only JNtoSM<\/em> (Join to Sort Merge Join) and JNtoHS<\/em> (Join to Hash) have been considered. In contrast, JNtoNL<\/em> (Join to Nested Loop) was discarded. Thus, we can deduce, that some heuristics kicked in. I couldn’t find any explanation for it, but we can guess that the heuristics is there to pre-empt a disastrous scenario, where we can end up with lot of table scans when there are more than one record in the small outer table. To demonstrate this point, I’ll add just one more record into the small table and collect the IO statistics:<\/p>\ninsert into t_small values (2,2) ;<\/code><\/pre>\nPrior to rerunning the query I’ll disable the Table Spool (Lazy Spool)<\/em> operations, which would otherwise be introduced and change the execution plan:<\/p>\nDBCC RULEOFF('BuildSpool')\r\nSET STATISTICS IO ON<\/code><\/pre>\nNested Loop:<\/p>\n
Table 't_large'. Scan count 1, logical reads 7664<\/span>, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.\r\nTable 't_small'. Scan count 1, logical reads 1, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.\r\n<\/code><\/pre>\nHash Join:<\/p>\n
Table 't_large'. Scan count 1, logical reads 3832<\/span>, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.\r\nTable 't_small'. Scan count 1, logical reads 1, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.\r\n<\/code><\/pre>\nAs expected, the large\u00a0inner table in the Nested Loop has to be scanned once again for an additional row in the outer table, while the number of logical reads remained the same for Hash Join. In conclusion, the number of logical reads in the Nested Loop join grows proportionally to the number of records in the inner table. Therefore, there is indeed a compelling reason for the heuristic rule for avoiding nested loops when the index on the join predicate column in the inner table is missing.<\/p>\n
Oracle<\/h1>\n
I also checked how the Oracle optimizer behaves under the same conditions. Here’s the test case:<\/p>\n
create user u identified by Temp_1234 ;\r\n\r\ngrant dba to u ;\r\n\r\nconnect u\/Temp_1234\r\n\r\ncreate table t_large ( id number , a number ) ;\r\ncreate table t_small ( b number , c number ) ;\r\n\r\ninsert into t_large\r\nSELECT level,level\r\nFROM dual\r\nCONNECT BY level <= 1000000;\r\n\r\ninsert into t_small values (1,1) ;\r\n\r\ncommit ;\r\n\r\nexec dbms_stats.gather_schema_stats('U');\r\n\r\nalter session set tracefile_identifier = 'NL' ;\r\nALTER SESSION SET EVENTS='10053 trace name context forever, level 1' ;\r\nexplain plan for select a from t_large l join t_small s on l.id = s.b ;<\/code><\/pre>\nUnlike in SQL Server, in Oracle, we don’t need to run the queries with hints to obtain the costing information for different join methods. We can rather extract all the information we need from the optimizer 10053 trace.
\nLikewise, Oracle opted for Hash Join, although\u00a0Nested Loop was cheaper.<\/p>\n
--------------------------------------+-----------------------------------+\r\n| Id | Operation | Name | Rows | Bytes | Cost | Time |\r\n--------------------------------------+-----------------------------------+\r\n| 0 | SELECT STATEMENT | | | | 284 | |\r\n| 1 | HASH JOIN <\/span> | | 1 | 13 | 284 | 00:00:06 |\r\n| 2 | TABLE ACCESS FULL | T_SMALL | 1 | 3 | 4 | 00:00:01 |\r\n| 3 | TABLE ACCESS FULL | T_LARGE | 977K | 9766K | 278 | 00:00:06 |\r\n--------------------------------------+-----------------------------------+\r\n\r\nBest NL cost: 282.775582<\/span>\r\n...\r\nHA Join\r\n HA cost: 283.618402<\/span>\r\n...\r\nBest:: JoinMethod: Hash\r\n<\/code><\/pre>\nIf you run the test case on a 12c database, you’ll find a hint that there is indeed some Nested Loop Join heuristics involved in the optimization process:<\/p>\n
DP: skipping adaptive plan due to NLJ heuristics<\/code><\/pre>\nConclusion<\/h1>\n
Both of the observed database optimizers employ heuristics to pre-empt expensive full table scans of the inner table, because the disadvantage of full table scan – when there are multiple records in the outer table – far outweighs the overhead of Hash Join compared to Nested Loop, when we have just 0 or 1 records in the outer table.<\/p>\n","protected":false},"excerpt":{"rendered":"
Not always the cheapest execution plan gets chosen. This blog post describes such an edge case in SQL Server and Oracle. Continue Reading