{"id":3472,"date":"2020-08-30T13:34:32","date_gmt":"2020-08-30T13:34:32","guid":{"rendered":"https:\/\/nenadnoveljic.com\/blog\/?p=3472"},"modified":"2020-08-30T13:38:12","modified_gmt":"2020-08-30T13:38:12","slug":"or-expansion-of-subqueries-limitations","status":"publish","type":"post","link":"https:\/\/nenadnoveljic.com\/blog\/or-expansion-of-subqueries-limitations\/","title":{"rendered":"OR-Expansion of Subqueries – Limitations"},"content":{"rendered":"

Oracle introduced cost based OR-expansion (ORE) in 12.2, and then significantly enhanced it in 19c to include subqueries [1]<\/a>. But this improvement doesn’t work for my old test case <\/a>. As it turned out, undocumented heuristics and a bug prevent the transformation.<\/p>\n

Here’s what I learned.<\/p>\n

Data<\/h1>\n
drop table t_large ;\ndrop table t_small ;\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\nexec dbms_stats.gather_table_stats(null, 'T_LARGE');\nexec dbms_stats.gather_table_stats(null, 'T_SMALL');<\/code><\/pre>\n
Unnesting without ORE<\/h1>\n
I’ll start this demo with subquery unnesting (SU), which is a prerequisite for ORE:<\/p>\n
Query A<\/b><\/p>\n
select \/*+ qb_name(main) *\/ a from t_large l \n  where id in ( select \/*+ qb_name(sbq) *\/ b from t_small s );<\/code><\/pre>\n
---------------------------------------------------------------------------------\n| Id  | Operation            | Name     | Rows  | Bytes | Cost (%CPU)| Time     |\n---------------------------------------------------------------------------------\n|   0 | SELECT STATEMENT     |          |       |       |   576<\/span> (100)|          |\n|*  1 |  HASH JOIN RIGHT SEMI|          |     2 |    46 |   576   (3)| 00:00:01 |\n|   2 |   VIEW               | VW_NSO_1 |     2 |    26 |     2   (0)| 00:00:01 |\n|   3 |    TABLE ACCESS FULL | T_SMALL  |     2 |     6 |     2   (0)| 00:00:01 |\n|   4 |   TABLE ACCESS FULL  | T_LARGE  |  1000K|  9765K|   569   (2)| 00:00:01 |\n---------------------------------------------------------------------------------\n\nPredicate Information (identified by operation id):\n---------------------------------------------------\n\n   1 - access(\"ID\"=\"B\")<\/code><\/pre>\n
SU is, expectedly, a cost based decision:<\/p>\n
SU:   Passed validity checks, but requires costing.<\/code><\/pre>\n
SU opens up new possibilities for the optimizer when searching for an optimal plan.<\/p>\n
FILTER without ORE<\/h1>\n
Without SU, the optimizer generates an inferior plan with FILTER:<\/p>\n
Query B (no_unnest hint added to the Query A)<\/b><\/p>\n
select  \/*+ qb_name(main) *\/ a from t_large l \n  where id in ( select \/*+ no_unnest<\/span> qb_name(sbq) *\/ b from t_small s );<\/code><\/pre>\n
------------------------------------------------------------------------------\n| Id  | Operation          | Name    | Rows  | Bytes | Cost (%CPU)| Time     |\n------------------------------------------------------------------------------\n|   0 | SELECT STATEMENT   |         |       |       |  1979K<\/span>(100)|          |\n|*  1 |  FILTER            |         |       |       |            |          |\n|   2 |   TABLE ACCESS FULL| T_LARGE |  1000K|  9765K|   570   (2)| 00:00:01 |\n|*  3 |   TABLE ACCESS FULL| T_SMALL |     1 |     3 |     2   (0)| 00:00:01 |\n------------------------------------------------------------------------------\n\nPredicate Information (identified by operation id):\n---------------------------------------------------\n\n   1 - filter( IS NOT NULL)\n   3 - filter(\"B\"=:B1)<\/code><\/pre>\n
The subquery runs for every row returned by the main query [2]<\/a>. The total cost, therefore, can be calculated as follows :<\/p>\n
Cost of acquiring data in the main query + Cardinality of result from the main query * Cost of single subquery execution = 570 + 10^6 * 2 = 2 * 10^6 [3]<\/a><\/p>\n
The subquery execution is performance killer.<\/p>\n
FILTER with ORE<\/h1>\n
After adding an OR operand to the query A, optimizer, surprisingly, doesn’t unnest anymore, and generates a plan with FILTER.<\/p>\n
Query C (OR added to the query A)<\/b><\/p>\n
select \/*+ qb_name(main) *\/ a from t_large l where id in \n  ( select \/*+ qb_name(sbq) *\/ b from t_small s ) \n  or a = 1<\/span> ;<\/code><\/pre>\n
\n------------------------------------------------------------------------------\n| Id  | Operation          | Name    | Rows  | Bytes | Cost (%CPU)| Time     |\n------------------------------------------------------------------------------\n|   0 | SELECT STATEMENT   |         |       |       |   572<\/span> (100)|          |\n|*  1 |  FILTER            |         |       |       |            |          |\n|   2 |   TABLE ACCESS FULL| T_LARGE |  1000K|  9765K|   572   (3)| 00:00:01 |\n|*  3 |   TABLE ACCESS FULL| T_SMALL |     1 |     3 |     2   (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)<\/code><\/pre>\n
The cost wrongly slumped from 1979K to 572, because the subquery execution isn’t factored in in the total cost anymore. Consequently, that cost is severely underestimated.<\/p>\n
Indexing driving table<\/h1>\n
ORE was bypassed due to missing indexes on the driving table:<\/p>\n
ORE: Bypassed for disjunct chain: No Index or Partition driver found<\/code><\/pre>\n
(“Disjunct chain” is a synonym for OR operands.)<\/p>\n
As we can see, the ORE decision isn’t entirely cost based – the optimizer rejects the transformation if the OR operands aren’t indexed.<\/p>\n
The “ORE: Bypassed…” message disappeared after creating the following index on t_large.a:<\/p>\n
create index i_t_large_1 on t_large(a);<\/code><\/pre>\n
Yet the plan didn’t change. The index above is necessary but not sufficient.<\/p>\n
Reducing ORE cost<\/h1>\n
Now I’m enforcing ORE with the hint.<\/p>\n
Query D (or_expand hint added to the Query C)<\/b><\/p>\n
select \/*+ qb_name(main) or_expand<\/span>(@main) *\/ a from t_large l \n  where id in ( select \/*+ qb_name(sbq) *\/ b from t_small s ) \n  or a = 1 ;<\/code><\/pre>\n
------------------------------------------------------------------------------------------\n| Id  | Operation              | Name            | Rows  | Bytes | Cost (%CPU)| Time     |\n------------------------------------------------------------------------------------------\n|   0 | SELECT STATEMENT       |                 |       |       |   581 (100)|          |\n|   1 |  VIEW                  | VW_ORE_48C33071 |     3 |    39 |   581<\/span>   (3)| 00:00:01 |\n|   2 |   UNION-ALL            |                 |       |       |            |          |\n|*  3 |    INDEX RANGE SCAN    | I_T_LARGE_1     |     1 |     5 |     3   (0)| 00:00:01 |\n|*  4 |    HASH JOIN RIGHT SEMI|                 |     2 |    46 |   578   (3)| 00:00:01 |\n|   5 |     VIEW               | VW_NSO_1        |     2 |    26 |     2   (0)| 00:00:01 |\n|   6 |      TABLE ACCESS FULL | T_SMALL         |     2 |     6 |     2   (0)| 00:00:01 |\n|*  7 |     TABLE ACCESS FULL  | T_LARGE         |   999K|  9765K|   571   (2)| 00:00:01 |\n------------------------------------------------------------------------------------------\n\nPredicate Information (identified by operation id):\n---------------------------------------------------\n\n   3 - access(\"A\"=1)\n   4 - access(\"ID\"=\"B\")\n   7 - filter(LNNVL(\"A\"=1))<\/code><\/pre>\n
The ORE cost is slightly higher than the miscalculated FILTER cost, so we have to reduce it. The following index eliminates the expensive full table scan on t_large:<\/p>\n
create index i_t_large_2 on t_large(id)<\/code><\/pre>\n
The plan for the query D (with or_expand hint) indeed became much more efficient:<\/p>\n
--------------------------------------------------------------------------------------------------\n| Id  | Operation                      | Name            | Rows  | Bytes | Cost (%CPU)| Time     |\n--------------------------------------------------------------------------------------------------\n|   0 | SELECT STATEMENT               |                 |       |       |    12 (100)|          |\n|   1 |  VIEW                          | VW_ORE_48C33071 |     3 |    39 |    12<\/span>   (9)| 00:00:01 |\n|   2 |   UNION-ALL                    |                 |       |       |            |          |\n|*  3 |    INDEX RANGE SCAN            | I_T_LARGE_1     |     1 |     5 |     3   (0)| 00:00:01 |\n|   4 |    NESTED LOOPS                |                 |     2 |    46 |     9  (12)| 00:00:01 |\n|   5 |     NESTED LOOPS               |                 |     2 |    46 |     9  (12)| 00:00:01 |\n|   6 |      VIEW                      | VW_NSO_1        |     2 |    26 |     2   (0)| 00:00:01 |\n|   7 |       HASH UNIQUE              |                 |     2 |     6 |            |          |\n|   8 |        TABLE ACCESS FULL       | T_SMALL         |     2 |     6 |     2   (0)| 00:00:01 |\n|*  9 |      INDEX RANGE SCAN          | I_T_LARGE_2     |     1 |       |     2   (0)| 00:00:01 |\n|* 10 |     TABLE ACCESS BY INDEX ROWID| T_LARGE         |     1 |    10 |     3   (0)| 00:00:01 |\n--------------------------------------------------------------------------------------------------\n\nPredicate Information (identified by operation id):\n---------------------------------------------------\n\n3 - access(\"A\"=1)\n9 - access(\"ID\"=\"B\")\n10 - filter(LNNVL(\"A\"=1))<\/code><\/pre>\n
That’s clearly a better plan, but optimizer rejects it. But, why?<\/p>\n
Unique constraint on the table in the subquery<\/h1>\n
The reason is recorded in the trace file:<\/p>\n
ORE: Checking validity of OR Expansion for query block SBQ (#2)\nORE: Predicate chain before QB validity check - SBQ\n:B1=\"S\".\"B\"\nORE: Predicate chain after QB validity check - SBQ\n:B1=\"S\".\"B\"\nORE: bypassed - No valid predicate for OR expansion.<\/code><\/pre>\n
“No valid predicate for OR expansion”, wrote optimizer. “Which predicate isn’t valid; and why?”, I wondered.<\/p>\n
Just couple of lines above…<\/p>\n
ORE: applying simple unnesting on interleaved qb.\nSU:   Transform an ANY subquery to semi-join<\/span> or distinct.\nRegistered qb: SEL$397D8923 0x8485cfb0 (SUBQ INTO VIEW FOR COMPLEX UNNEST SEL$7DA70B07)<\/code><\/pre>\n
The subquery was converted to semi-join (as opposed to join), because the correlated column in the subquery isn’t unique.<\/p>\n
Will ORE work with a unique constraint?<\/p>\n
create unique index i_t_small_1 on t_small(b);<\/code><\/pre>\n
It will!<\/p>\n
--------------------------------------------------------------------------------------------------\n| Id  | Operation                      | Name            | Rows  | Bytes | Cost (%CPU)| Time     |\n--------------------------------------------------------------------------------------------------\n|   0 | SELECT STATEMENT               |                 |       |       |     9 (100)|          |\n|   1 |  VIEW                          | VW_ORE_48C33071 |     3 |    39 |     9<\/span>   (0)| 00:00:01 |\n|   2 |   UNION-ALL                    |                 |       |       |            |          |\n|*  3 |    INDEX RANGE SCAN            | I_T_LARGE_1     |     1 |     5 |     3   (0)| 00:00:01 |\n|   4 |    NESTED LOOPS                |                 |     2 |    26 |     6   (0)| 00:00:01 |\n|   5 |     NESTED LOOPS               |                 |     2 |    26 |     6   (0)| 00:00:01 |\n|   6 |      INDEX FULL SCAN           | I_T_SMALL_1     |     2 |     6 |     1   (0)| 00:00:01 |\n|*  7 |      INDEX RANGE SCAN          | I_T_LARGE_2     |     1 |       |     2   (0)| 00:00:01 |\n|*  8 |     TABLE ACCESS BY INDEX ROWID| T_LARGE         |     1 |    10 |     3   (0)| 00:00:01 |\n--------------------------------------------------------------------------------------------------\n\nPredicate Information (identified by operation id):\n---------------------------------------------------\n\n   3 - access(\"A\"=1)\n   7 - access(\"ID\"=\"B\")\n   8 - filter(LNNVL(\"A\"=1))<\/code><\/pre>\n
Summary<\/h1>\n
Cost based ORE of disjunctive subqueries is a huge improvement in 19c. But the decision isn’t entirely cost based. The optimizer has heuristics which can unnecessarily rule out a good plan.<\/p>\n
I discovered the following requirements:<\/p>\n