Disjunctive subqueries are the subqueries which are applied to the or<\/em> operator, like the following one:<\/p>\n Given that the not null<\/em> constraint on the t_large.a<\/em> column is defined, an alternative way to write this query is:<\/p>\n Ideally, the optimizer should apply cost-based query transformations to rewrite the original query with the or<\/em> operator as the union all<\/em> variant when appropriate. In this blog post I’ll investigate, how successfully these algorithms work in SQL Server and Oracle.<\/p>\n Let me start with SQL Server. I’ll create two test tables, one large with a milion records and the other small, containing just two records:<\/p>\n The query to populate a large table with numbers<\/a> is used by courtesy of Aaron Bertrand.<\/p>\n First, I’ll examine the execution plan and the statistics of the original query with the or<\/em> operator:<\/p>\n At the first glance, there are two things in the execution plan above that look suspicious. One is the Table Scan<\/em> in the Nested Loop Join (NLJ)<\/em>. Usually, the Query Optimizer uses Nested Loop Join Heuristics<\/a> to pre-empt Table Scans<\/em> in NLJs. The other is, that the Concatenation<\/em> operator, which implements union all<\/em>, is not on the top of the execution plan. Instead, it is placed inside the NLJ. As a consequence, there will be repeated Table Scans<\/em> of the inner table t_small<\/em>.<\/p>\n So, let’s examine the execution plan of the equivalent query with the union all<\/em> operator:<\/p>\n As expected, the union query uses the Hash Join (HJ)<\/em>, and the Concatenation<\/em> operator is on the top of the exection plan. However, its estimated cost is significantly higher than the cost of the NLJ query, 15.3989<\/span> and 9.70106<\/span>, respectively. Curiously, despite its more expensive plan, the union all query with the HJ is by orders of magnitude more efficient than the original query with the or<\/em> operator which does NLJ. What I mean by that is, considering the high number of logical reads (999999<\/span>) on t_small<\/em>, its estimated cost (9.70106<\/span>) seems quite small when compared to the cost of the HJ (10.97784<\/span>), which performed in total only 7665<\/span> logical reads. To get an idea, by how much the cost of the NLJ was underestimated, I’ll isolate the join in a separate query forcing the join order and NLJ with hints:<\/p>\n As opposed to the original query with the or<\/em> operator, the cost of the scan of the inner table in the NLJ in the query above – 80.7032<\/span> – reflects much better the high number of logical reads performed. In conclusion, if this cost had been caculated correctly in the original query, it is not unreasonable to assume that the query would have been transformed correctly.<\/p>\n So, how can we overcome the wrong cost calculation?<\/p>\n As the wrong cost calculation applies to the Table Scan<\/em>, let’s try to eliminate it by creating the following index:<\/p>\n Indeed, the transformation is done as expected for the original query with the or clause:<\/p>\n Also, the number of logical reads is identical for both the or and union all query:<\/p>\n Therefore, we can conclude, that the transformation is now successful.<\/p>\n Now, let’s see how all of this works (or doesn’t work) in an Oracle database:<\/p>\n First, I’ll inspect the execution plan and the statistics of the original query containing or<\/em>:<\/p>\n The presence of the filter operation indicates that the subquery was not unnested, which in turn means that it was repeatidly executed for each record in t_large<\/em>. Moreover, the full table scan of t_small<\/em> was not costed properly. What I mean by this is, there were 4999K<\/span> logical reads on the table, but the cost was estimated to only 4<\/span>.<\/p>\n At this point, we might ask ourselves, whether the absence of the query unnesting is the consequence of the wrong cost calculation, or is the Oracle optimizer inherently incapable of transforming disjunctive queries.<\/p>\n We can easily answer this question by verifying whether the execution plan changes after embedding the unnest hint in the subquery:<\/p>\n Unfortunately, the execution plan hasn’t improved, which leads us to the conclusion that the Oracle optimizer just doesn’t do unnesting of disjunctive subqueries. Actually, Jonathan Lewis and Mohamed Houry have already elaborated on this topic in their blog posts Subquery with OR<\/a> and Tuning a disjunctive subquery<\/a>, repectively.<\/p>\n Finally, let’s quantify the benefit of manually rewriting the query:<\/p>\n Looking into the buffers statistics, we can see that the number of logical reads slumped from 5 million<\/span> to just 548<\/span>. Sadly, Oracle misses a huge optimizing potential by not implementing the unnesting of disjunctive subqueries.<\/p>\n In summary, the unnesting of disjunctive subqueries and merging them into the main query can boost query performance.<\/p>\n Unfortunately, the algorithm hasn’t been implemented in the Oracle optimizer yet. Therefore, developers have to put effort in assisting the optimizer in deriving a good execution plan.<\/p>\n In contrast, the SQL Server optimizer is able to do this transformation all by itself. However, beware of some edge cases where, due to a wrong cost calculation, the optimization process doesn’t yield the expected result, which in turn may result in suboptimal plans. The good news is, that such plans can be easily recognized by Table Scans<\/em> in Nested Loop Joins<\/em> and therefore avoided by a good indexing strategy.<\/p>\n The behavior hasn’t changed in 12.2: the disjunctive subquery is still not being unnested.<\/p>\n Jonathan Lewis shows us here<\/a> that ORE works with disjunctive queries in 19c. The optimizer team implemented the unnesting of disjunctive subqueries. Keep in mind that every column of the table in the main query block which is referenced in OR must have an index. This means that you have to create an index on t_large.a in the test case above.<\/p>\n The feature isn’t implemented in 18c (tested on 18.5.0.0.190115).<\/p>\n","protected":false},"excerpt":{"rendered":" Disjunctive subqueries are the subqueries which are applied to the or operator. Alternatively, these queries can be rewritten to use the union all operator which may be a more efficient way to retrieve the records from the database. This blog post compares the efficiency of SQL Server and Oracle optimizer when dealing with the transformations of disjunctive subqueries.select a from t_large l \n where id in ( select b from t_small s ) or<\/span> a = 1 <\/code><\/pre>\nselect a from t_large l where a = 1 \nunion all<\/span>\nselect a from t_large l \n where id in ( select b from t_small s ) and a != 1 <\/span><\/code><\/pre>\nSQL Server<\/h1>\n
Setting the Scene<\/h2>\n
\nSELECT TOP (1000000)\nid = CONVERT(INT, ROW_NUMBER() OVER (ORDER BY s1.[object_id])),\na = CONVERT(INT, ROW_NUMBER() OVER (ORDER BY s1.[object_id]))\nINTO t_large\nFROM sys.all_objects AS s1 CROSS JOIN sys.all_objects AS s2\nOPTION (MAXDOP 1);\n\nalter table t_large alter column a integer not null\n\ncreate table t_small (b integer,c integer) ;\ninsert into t_small values (1,1) ;\ninsert into t_small values (2,2) ;\n<\/code><\/pre>\nQuery Transformation<\/h2>\n
select a from t_large l where id in ( select b from t_small s ) or<\/span> a = 1 \nStmtText\tEstimateRows\tTotalSubtreeCost<\/span>\tEstimateExecutions\nselect a from t_large l where id in ( select b from t_small s ) or a = 1\t1000000\t9.70106<\/span>\tNULL\n |--Nested Loops<\/span>(Left Semi Join, OUTER REFERENCES:([l].[id], [l].[a]))\t1000000\t9.70106\t1\n |--Table Scan(OBJECT:([master].[dbo].[t_large] AS [l]))\t1000000\t3.94106\t1\n |--Concatenation\t1\t1.58\t1000000\n |--Filter(WHERE:(STARTUP EXPR([master].[dbo].[t_large].[a] as [l].[a]=(1))))\t1\t1.48\t1000000\n | |--Constant Scan\t1\t1\t1000000\n |--Table Scan<\/span>(OBJECT:([master].[dbo].[t_small] AS [s]), WHERE:([master].[dbo].[t_large].[id] as [l].[id]=[master].[dbo].[t_small].[b] as [s].[b]))\t1\t9.70106\t1000000\n<\/code><\/pre>\nselect a from t_large l where a = 1 \nunion all<\/span>\nselect a from t_large l where id in ( select b from t_small s ) and a != 1\nStmtText\tTotalSubtreeCost<\/span>\tEstimateExecutions\nselect a from t_large l where id in ( select b from t_small s ) and a != 1\t15.3989<\/span>\tNULL\n |--Concatenation<\/span>\t15.3989\t1\n |--Table Scan(OBJECT:([master].[dbo].[t_large] AS [l]), WHERE:([master].[dbo].[t_large].[a] as [l].[a]=(1)))\t3.94106\t1\n |--Hash Match<\/span>(Right Semi Join, HASH:([s].[b])=([l].[id]), RESIDUAL:([master].[dbo].[t_large].[id] as [l].[id]=[master].[dbo].[t_small].[b] as [s].[b]))\t10.97784<\/span>\t1\n |--Table Scan(OBJECT:([master].[dbo].[t_small] AS [s]))\t0.0032842\t1\n |--Table Scan(OBJECT:([master].[dbo].[t_large] AS [l]), WHERE:([master].[dbo].[t_large].[a] as [l].[a]<>(1)))\t3.94106\t1\n<\/code><\/pre>\n
\nFor this reason, it makes sense to cross-check the cost calculation with the IO and timing statistics for both queries:<\/p>\nNLS (or query) <\/span>:\n\nTable 't_small'. Scan count 1, logical reads 999999<\/span>, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.\nTable 't_large'. Scan count 1, logical reads 3832, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.\n\n(1 row(s) affected)\n\n SQL Server Execution Times:\n CPU time = 3766 ms, elapsed time = 5143 ms.\n \nHJ (union all query)<\/span>:\nTable 'Workfile'. 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 '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 't_large'. Scan count 2, logical reads 7664<\/span>, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.\nTable 't_small'. Scan count 1, logical reads 1<\/span>, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.\n\n(1 row(s) affected)\n\n SQL Server Execution Times:\n CPU time = 328 ms, elapsed time = 493 ms.\nSQL Server parse and compile time: \n CPU time = 0 ms, elapsed time = 0 ms.\n<\/code><\/pre>\nselect a from t_large l \n where id in ( select b from t_small s ) \n option (loop join , force order)\n\nStmtText\tTotalSubtreeCost\nselect a from t_large l \t\n where id in ( select b from t_small s ) option (loop join , force order)<\/span>\t93.60426\n |--Nested Loops(Left Semi Join, WHERE:([master].[dbo].[t_large].[id] as [l].[id]=[master].[dbo].[t_small].[b] as [s].[b]))\t93.60426\n |--Table Scan(OBJECT:([master].[dbo].[t_large] AS [l]))\t3.94106\n |--Table Scan(OBJECT:([master].[dbo].[t_small] AS [s]))\t80.7032 \n<\/span><\/code><\/pre>\nIndexing<\/h2>\n
CREATE NONCLUSTERED INDEX [idx_t_large_id]\nON [dbo].[t_large] ([id])\nINCLUDE ([a])<\/code><\/pre>\n\n |--Concatenation<\/span>\n |--Index Scan(OBJECT:([master].[dbo].[t_large].[idx_t_large_id] AS [l]), WHERE:([master].[dbo].[t_large].[a] as [l].[a]=(1)))\n |--Nested Loops(Inner Join, OUTER REFERENCES:([s].[b]))\n |--Sort(DISTINCT ORDER BY:([s].[b] ASC))\n | |--Table Scan(OBJECT:([master].[dbo].[t_small] AS [s]))\n |--Index Seek(OBJECT:([master].[dbo].[t_large].[idx_t_large_id] AS [l]), SEEK:([l].[id]=[master].[dbo].[t_small].[b] as [s].[b]), WHERE:([master].[dbo].[t_large].[a] as [l].[a]<>(1)) ORDERED FORWARD)\n<\/code><\/pre>\nTable '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 't_large'. Scan count 3, logical reads 2735<\/span>, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.\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.<\/code><\/pre>\nOracle<\/h1>\n
create user u identified by Temp_12345 ;\ngrant dba to u ;\n\nconnect u\/Temp_12345\n\ncreate table t_large ( id number , a number not null ) ;\ncreate table t_small ( b number , c number ) ;\n\ninsert into t_large\nSELECT level,level\nFROM dual\nCONNECT BY level <= 1000000;\n\ninsert into t_small values (1,1) ;\ninsert into t_small values (2,2) ;\n\ncommit ;\n\nCREATE INDEX idx_t_large_a ON t_large(id) ;\n\nexec dbms_stats.gather_schema_stats('U');<\/code><\/pre>\nselect \/*+ gather_plan_statistics *\/ a from t_large l \n where id in ( select b from t_small s ) or<\/span> a = 1 ;\n\n\n------------------------------------------------------------------------------------------------------------------------\n| Id | Operation | Name | Starts | E-Rows |E-Bytes| Cost (%CPU)| E-Time | A-Rows | A-Time | Buffers<\/span> |\n------------------------------------------------------------------------------------------------------------------------\n| 0 | SELECT STATEMENT | | 1 | | | 280 (100)| | 2 |00:00:00.01 | 5000K<\/span>|\n|* 1 | FILTER<\/span> | | 1 | | | | | 2 |00:00:00.01 | 5000K|\n| 2 | TABLE ACCESS FULL| T_LARGE | 1 | 1000K| 9765K| 280 (2)| 00:00:01 | 1000K|00:00:00.20 | 538 |\n|* 3 | TABLE ACCESS FULL| T_SMALL | 999K| 1 | 3 | 4<\/span> (0)| 00:00:01 | 1 |00:00:09.17 | 4999K<\/span>|\n------------------------------------------------------------------------------------------------------------------------\n\nPredicate Information (identified by operation id):\n---------------------------------------------------\n 1 - filter((\"A\"=1 OR IS NOT NULL))\n 3 - filter(\"B\"=:B1)<\/code><\/pre>\nselect \/*+ gather_plan_statistics *\/ a from t_large l \n where id in ( select \/*+ unnest<\/span> *\/ b from t_small s ) or<\/span> a = 1 ;\n\n------------------------------------------------------------------------------\n| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |\n------------------------------------------------------------------------------\n| 0 | SELECT STATEMENT | | | | 280 (100)| |\n|* 1 | FILTER<\/span> | | | | | |\n| 2 | TABLE ACCESS FULL| T_LARGE | 1000K| 9765K| 280 (2)| 00:00:01 |\n|* 3 | TABLE ACCESS FULL| T_SMALL | 1 | 3 | 4 (0)| 00:00:01 |\n------------------------------------------------------------------------------\n\nPredicate Information (identified by operation id):\n---------------------------------------------------\n\n 1 - filter((\"A\"=1 OR IS NOT NULL))\n 3 - filter(\"B\"=:B1)\n<\/code><\/pre>\nselect \/*+ gather_plan_statistics *\/ a from t_large l where a = 1 \nunion all<\/span>\nselect a from t_large l where id in ( select b from t_small s ) and a != 1 ;\n\n--------------------------------------------------------------------------------------------------------------------------------------------------------------------\n| Id | Operation | Name | Starts | E-Rows |E-Bytes| Cost (%CPU)| E-Time | A-Rows | A-Time | Buffers<\/span> | OMem | 1Mem | Used-Mem |\n--------------------------------------------------------------------------------------------------------------------------------------------------------------------\n| 0 | SELECT STATEMENT | | 1 | | | 286 (100)| | 2 |00:00:00.01 | 548<\/span> | | | |\n| 1 | UNION-ALL<\/span> | | 1 | | | | | 2 |00:00:00.01 | 548 | | | |\n|* 2 | TABLE ACCESS FULL | T_LARGE | 1 | 1 | 5 | 279 (2)| 00:00:01 | 1 |00:00:00.01 | 538 | | | |\n| 3 | NESTED LOOPS | | 1 | 2 | 26 | 7 (15)| 00:00:01 | 1 |00:00:00.01 | 10 | | | |\n| 4 | NESTED LOOPS | | 1 | 2 | 26 | 7 (15)| 00:00:01 | 2 |00:00:00.01 | 9 | | | |\n| 5 | SORT UNIQUE | | 1 | 2 | 6 | 4 (0)| 00:00:01 | 2 |00:00:00.01 | 5 | 2048 | 2048 | 2048 (0)|\n| 6 | TABLE ACCESS FULL | T_SMALL | 1 | 2 | 6 | 4 (0)| 00:00:01 | 2 |00:00:00.01 | 5 | | | |\n|* 7 | INDEX RANGE SCAN | IDX_T_LARGE_A | 2 | 1 | | 1 (0)| 00:00:01 | 2 |00:00:00.01 | 4 | | | |\n|* 8 | TABLE ACCESS BY INDEX ROWID| T_LARGE | 2 | 1 | 10 | 2 (0)| 00:00:01 | 1 |00:00:00.01 | 1 | | | |\n--------------------------------------------------------------------------------------------------------------------------------------------------------------------\n<\/code><\/pre>\nConclusion<\/h1>\n
Updates<\/h1>\n
March 9, 2017 – 12.2<\/h2>\n
August 24, 2020 – 19c<\/h2>\n
\n Continue Reading