In this blog post, I’ll be analyzing how Oracle 18c and SQL Server 2017 optimize queries with a correlated subquery in the SELECT clause, such as the following:<\/p>\n
select<\/span> \/*+ qb_name(QB_MAIN) *\/ \n case when exists<\/span> ( \n select \/*+ qb_name(QB_EXISTS) *\/ 1 \n\t from t_1k \n\t where t_1k.n1 = t_100k.n1 \n ) then 1 else 0 end\n from t_100k ;<\/code><\/pre>\nFirst, we’re going to explore the limitations of the Oracle optimizer.<\/p>\n
Oracle<\/h1>\nTables<\/h2>\n
The tables t_1k and t_100k are created as follows:<\/p>\n
create table t_1k ( n1 integer ) ;\n\ncreate table t_100k ( n1 integer ) ;\n\ninsert into t_1k\n select level\n from dual\n connect by level <= 1000;\n\ninsert into t_100k\n select level \n from dual\n connect by level <= 100000;\n \ncommit ;\n\nbegin\n dbms_stats.gather_table_stats ( null, 'T_1K') ;\n dbms_stats.gather_table_stats ( null, 'T_100K') ;\nend ;\n\/<\/code><\/pre>\nThe larger table t_100k is used in the main query block, the smaller t_1k in the subquery.<\/p>\n
Missing Join<\/h2>\n
What first strikes out is that there isn’t any join operation performed.<\/p>\n
-----------------------------------------------------------------------------\n| Id | Operation | Name | E-Rows |E-Bytes| Cost (%CPU)| E-Time |\n-----------------------------------------------------------------------------\n| 0 | SELECT STATEMENT | | | | 356K<\/span>(100)| |\n|* 1 | TABLE ACCESS FULL| T_1K | 1 | 4 | 4 (0)| 00:00:01 |\n| 2 | TABLE ACCESS FULL| T_100K | 100K| 488K| 33 (0)| 00:00:01 |\n-----------------------------------------------------------------------------<\/code><\/pre>\nTherefore, it comes to no surprise that both query blocks are optimized independently (they’re marked as OUTLINE_LEAF in the outline section):<\/p>\n
Query Block Name \/ Object Alias (identified by operation id):\n-------------------------------------------------------------\n \n 1 - QB_EXISTS \/ T_1K@QB_EXISTS\n 2 - QB_MAIN \/ T_100K@QB_MAIN\n \nOutline Data\n-------------\n \n \/*+\n BEGIN_OUTLINE_DATA\n IGNORE_OPTIM_EMBEDDED_HINTS\n OPTIMIZER_FEATURES_ENABLE('18.1.0')\n DB_VERSION('18.1.0')\n ALL_ROWS\n OUTLINE_LEAF(@\"QB_EXISTS\")\n OUTLINE_LEAF(@\"QB_MAIN\")<\/span>\n FULL(@\"QB_MAIN\" \"T_100K\"@\"QB_MAIN\")\n FULL(@\"QB_EXISTS\" \"T_1K\"@\"QB_EXISTS\")\n END_OUTLINE_DATA\n *\/<\/code><\/pre>\nFinally, the predicate and column projection sections tell us that the driving table is T_100K.<\/p>\n
Predicate Information (identified by operation id):\n---------------------------------------------------\n \n 1 - filter(\"T_1K\".\"N1\"=:B1)\n \nColumn Projection Information (identified by operation id):\n-----------------------------------------------------------\n \n 2 - \"T_100K\".\"N1\"[NUMBER,22]<\/code><\/pre>\nSo, T_1K.N1 is matched for every single retrieved row from T_100K. That’s the reason why the number of rows in the driving row source will be the main contributor to the total cost, specially for large driving row sources:
\ntotal_cost ~ driving_row_source_cost + k * driving_rows * single_subquery_access_cost
\n356000<\/span> ~ 33 + k * 100000<\/span> * 4<\/p>\nBy the way, k is around 0.5 for smaller tables and then it grows toward 1 with the table size. That’s presumably to factor in the caching effect.<\/p>\n
Anyway, the query will perform poorly for large driving row sources – the query indeed executed 500323<\/span> logical reads.<\/p>\nFurther, it can be easily seen that our example query isn’t an exception, but rather other correlated subqueries suffer from the same problem too, like, for example:<\/p>\n
select \/*+ qb_name(QB_MAIN) *\/ \n (\n select \/*+ qb_name(QB_EXISTS) *\/ n1 \n\t from t_1k \n\t where t_1k.n1 = t_100k.n1 \n ) \n from t_100k ;\n \n----------------------------------------------------------------------------\n| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |\n----------------------------------------------------------------------------\n| 0 | SELECT STATEMENT | | 100K| 488K| 371K<\/span> (1)| 00:00:59 |\n|* 1 | TABLE ACCESS FULL| T_1K | 1 | 4 | 4 (0)| 00:00:01 |\n| 2 | TABLE ACCESS FULL| T_100K | 100K| 488K| 33 (0)| 00:00:01 |\n----------------------------------------------------------------------------\n\nPredicate Information (identified by operation id):\n---------------------------------------------------\n \n 1 - filter(\"T_1K\".\"N1\"=:B1)<\/code><\/pre>\nNotice that the first executed operation in the execution plan isn’t the first child, as per usual, but the second one.<\/p>\n
In conclusion, problematic correlated subqueries have a specific shape with the following characteristics:<\/p>\n
\n- two children of the SELECT operation without a join,<\/li>\n
- filter predicate on the first child,<\/li>\n
- high cost of the parent SELECT related to a high cardinality of the second child.<\/li>\n<\/ul>\n
I recommend memorizing this pattern, because it can help you immediately identify a problematic correlated subquery even in larger execution plans where the subquery is buried under many layers of cascaded views.<\/p>\n
But, is there a better way to execute the same query?<\/p>\n
Outer Join<\/h2>\n
The answer is yes, but we have to manually rewrite it to use a join. For instance, the query<\/p>\n
select \/*+ qb_name(QB_MAIN) *\/ \n case when exists ( \n select \/*+ qb_name(QB_EXISTS) *\/ 1 \n\t from t_1k \n\t where t_1k.n1 = t_100k.n1 \n ) then 1 else 0 end\n from t_100k ;<\/code><\/pre>\ncan be rewritten as:<\/p>\n
select \n case when v.n1 is not null then 1 else 0 end\n from t_100k, ( select distinct n1 from t_1k ) v\n where t_100k.n1 = v.n1(+) ;\n\n--------------------------------------------------------------------------------\n| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |\n--------------------------------------------------------------------------------\n| 0 | SELECT STATEMENT | | 100K| 1757K| 39<\/span> (6)| 00:00:01 |\n|* 1 | HASH JOIN RIGHT OUTER| | 100K| 1757K| 39 (6)| 00:00:01 |\n| 2 | VIEW | | 1000 | 13000 | 5 (20)| 00:00:01 |\n| 3 | HASH UNIQUE | | 1000 | 4000 | 5 (20)| 00:00:01 |\n| 4 | TABLE ACCESS FULL | T_1K | 1000 | 4000 | 4 (0)| 00:00:01 |\n| 5 | TABLE ACCESS FULL | T_100K | 100K| 488K| 33 (0)| 00:00:01 |\n--------------------------------------------------------------------------------\n \nPredicate Information (identified by operation id):\n---------------------------------------------------\n \n 1 - access(\"T_100K\".\"N1\"=\"V\".\"N1\"(+))<\/code><\/pre>\nAs you can see, the plan has a significantly lower cost than the original, 39<\/span> and 371000<\/span>, respectively. The total cost entails retrieving both row sources and combining them together with a hash join.<\/p>\nThe modified query performed 161<\/span> logical reads, which is orders of magnitude less than carried out by the original query (500323<\/span>).<\/p>\nWe’ve seen so far how the query can be rewritten to execute more efficiently. Now it’s time to check how SQL Server optimizes the same original query.<\/p>\n
SQL Server<\/h1>\n
Below is the equivalent test case for SQL Server:<\/p>\n
drop table t_1k ;\n\ndrop table t_100k ;\n\ncreate table t_1k (n1 integer) ;\n\ncreate table t_100k (n1 integer) ;\n\ninsert into t_1k \nSELECT TOP (1000) \n n1 = CONVERT(INT, ROW_NUMBER() OVER (ORDER BY s1.[object_id]))\nFROM sys.all_objects AS s1 CROSS JOIN sys.all_objects AS s2\nOPTION (MAXDOP 1);\n\ninsert into t_100k\nSELECT TOP (100000) \n n1 = CONVERT(INT, ROW_NUMBER() OVER (ORDER BY s1.[object_id]))\nFROM sys.all_objects AS s1 CROSS JOIN sys.all_objects AS s2\nOPTION (MAXDOP 1);\n\nset statistics io on \n\nselect \n case when exists ( \n select 1 \n\t from t_1k \n\t where t_1k.n1 = t_100k.n1 \n ) then 1 else 0 end\n from t_100k ; <\/code><\/pre>\nThat’s terrific! Unlike Oracle, SQL Server transformed the query to use merge semi join out of the box:<\/p>\n
StmtText\tStmtId\tNodeId\tParent\tEstimateRows\tTotalSubtreeCost\tEstimateExecutions\n |--Compute Scalar(DEFINE:([Expr1007]=CASE WHEN [Expr1008] THEN (1) ELSE (0) END))\t1\t2\t1\t90000\t8.64109<\/span>\t1\n |--Merge Join<\/span>(Left Semi Join, MANY-TO-MANY MERGE:([DERITRADE].[dbo].[t_100k].[n1])=([DERITRADE].[dbo].[t_1k].[n1]), RESIDUAL:([DERITRADE].[dbo].[t_1k].[n1]=[DERITRADE].[dbo].[t_100k].[n1]))\t1\t3\t2\t90000\t8.632091\t1\n |--Sort(ORDER BY:([DERITRADE].[dbo].[t_100k].[n1] ASC))\t1\t4\t3\t100000\t7.995876\t1\n | |--Table Scan(OBJECT:([DERITRADE].[dbo].[t_100k]))\t1\t5\t4\t100000\t0.3606894\t1\n |--Sort(ORDER BY:([DERITRADE].[dbo].[t_1k].[n1] ASC))\t1\t6\t3\t1000\t0.03351212\t1\n |--Table Scan(OBJECT:([DERITRADE].[dbo].[t_1k]))\t1\t7\t6\t1000\t0.006604222\t1\n<\/code><\/pre>\nThe execution resulted in only 339<\/span> logical reads without having to manually rewrite the query:<\/p>\n(100000 rows affected)\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_1k'. Scan count 1, logical reads 4<\/span>, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.\nTable 't_100k'. Scan count 1, logical reads 335<\/span>, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.<\/code><\/pre>\nSummary<\/h1>\n\n- Unfortunately, Oracle doesn’t optimally handle queries with correlated subqueries in the select clause.<\/li>\n
- Such queries can be manually rewritten to use join instead.<\/li>\n
- Suboptimal correlated subqueries have a specific shape that can be easily spotted in a larger execution plan.<\/li>\n
- Unlike Oracle, SQL Server automatically transforms such queries to use more efficient joins.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"
How Oracle and SQL Server optimize correlated subqueries in the SELECT clause with an example how to manually optimize such queries for Oracle. Continue Reading