{"id":94938,"date":"2022-10-26T05:30:52","date_gmt":"2022-10-26T05:30:52","guid":{"rendered":"https:\/\/www.red-gate.com\/simple-talk\/?p=94938"},"modified":"2022-11-10T02:17:00","modified_gmt":"2022-11-10T02:17:00","slug":"oracle-optimizer-or-expansion-transformations","status":"publish","type":"post","link":"https:\/\/www.red-gate.com\/simple-talk\/databases\/oracle-databases\/oracle-optimizer-or-expansion-transformations\/","title":{"rendered":"Oracle optimizer Or Expansion Transformations"},"content":{"rendered":"

Jonathan Lewis' continuing series on the Oracle optimizer and how it transforms queries into execution plans:<\/strong><\/p>\n

    \n
  1. Transformations by the Oracle Optimizer<\/a><\/li>\n
  2. The effects of NULL with NOT IN on Oracle transformations<\/a><\/li>\n
  3. Oracle subquery caching and subquery pushing<\/a><\/li>\n
  4. Oracle optimizer removing or coalescing subqueries<\/a><\/li>\n
  5. Oracle optimizer Or Expansion Transformations<\/a><\/li>\n<\/ol>\n\n

    There are two versions of this transformation, the \u201clegacy\u201d Or-Expansion \u2013 formerly known as \u201cConcatenation\u201d \u2013 and the new (12.2) implementation that allows Oracle greater scope and flexibility in its use. The basic mechanism is essentially the same in both versions though the shape of the execution plan does change. The key feature is that the optimizer can take a single query block and transform it into a UNION ALL<\/code> of 2 or more query blocks which can then be optimized and run separately.<\/p>\n

    Here\u2019s some code to create a table that I will use to demonstrate the principle:<\/p>\n

    create table t1\r\nas\r\nwith generator as (\r\n        select \r\n                rownum id\r\n        from dual \r\n        connect by \r\n                level <= 1e4    -- > comment to avoid \r\n                                -- WordPress format issue\r\n)\r\nselect\r\n        cast(rownum as number(8,0))                     id,\r\n        cast(mod(rownum,1949) as number(8,0))           n1949,\r\n        cast(mod(rownum,1951) as number(8,0))           n1951,\r\n        cast(lpad(rownum,10,'0') as varchar2(10))       v1,\r\n        cast(lpad('x',100,'x') as varchar2(100))        padding\r\nfrom\r\n        generator\r\norder by\r\n        dbms_random.value\r\n;\r\ncreate index t1_i1949 on t1(n1949);\r\ncreate index t1_i1951 on t1(n1951);<\/pre>\n
    The table t1<\/code> holds 10,000 rows. In case you\u2019re wondering, 1949<\/code> and 1951<\/code> are prime numbers and since they are both slightly less than 2,000 most values in the two columns will appear 5 times each, but a few will appear six times. It\u2019s worth doing a couple of quick queries to get a better intuitive feel for the data:<\/p>\n
    select  v1, n1949, n1951 from t1 where n1949 = 3;\r\n\r\nselect  v1, n1949, n1951 from t1 where n1951 = 3;\r\n\r\nselect  v1, n1949, n1951 from t1 where n1949 = 3 or n1951 = 3;<\/pre>\n
    And here are the three sets of results from my test (in the absence of an \u201corder by\u201d clause your results may appear in a different order):<\/p>\n
    V1              N1949      N1951\r\n---------- ---------- ----------\r\n0000007799          3       1946\r\n0000009748          3       1944\r\n0000001952          3          1\r\n0000005850          3       1948\r\n0000000003          3          3\r\n0000003901          3       1950\r\n\r\n6 rows selected.\r\n\r\nV1              N1949      N1951\r\n---------- ---------- ----------\r\n0000009758         13          3\r\n0000005856          9          3\r\n0000001954          5          3\r\n0000007807         11          3\r\n0000003905          7          3\r\n0000000003          3          3\r\n\r\n6 rows selected.\r\n\r\nV1              N1949      N1951\r\n---------- ---------- ----------\r\n0000009758         13          3\r\n0000005856          9          3\r\n0000007799          3       1946\r\n0000001954          5          3\r\n0000007807         11          3\r\n0000003905          7          3\r\n0000009748          3       1944\r\n0000001952          3          1\r\n0000005850          3       1948\r\n0000000003          3          3\r\n0000003901          3       1950\r\n\r\n11 rows selected.<\/pre>\n
    You\u2019ll notice, of course, that the two simple queries returned 6 rows, but the disjunct (\u201cOR<\/code>\u201d) of the two separate predicates returned only 11 rows. A little visual inspection shows that the row where v1 = '0000000003'<\/code> appears in both of the first two result sets when it\u2019s only going to appear once in the final query.<\/p>\n
    This example is so simple that the final plan doesn\u2019t show OR expansion it has used a completely different option to access the data using a method that the optimizer thinks is cheaper (partly because of a limitation \u2013 not a bug \u2013 in the optimizer\u2019s model). Here\u2019s the plan (pulled from memory after checking the SQL_ID of the query<\/a>):<\/p>\n
    select * from table(dbms_xplan.display_cursor('7ykzsaf3r0umb',null));<\/code><\/pre>\n
    This returns:<\/p>\n
    <\/p>\n
    The optimizer has decided to use btree\/bitmap conversion<\/em><\/strong>. The plan does an index range scan of the two indexes, one for each predicate, then converts the two lists of rowids into two bit-strings, does a Bitmap-OR of the two strings then converts the resulting string back into a list of rowids. It\u2019s an unfortunate feature of execution plans that bitmap strategies don\u2019t include estimates of how many bits are \u201cset\u201d (i.e. 1) and how many rowids will be produced before showing the final estimate of rows returned after the table has been accessed by rowid and filtered.<\/p>\n
    Side note:<\/strong> Since the optimizer has no idea how the pattern of bits in a bitmap is related to the scattering of data (and the clustering_factor<\/strong> of a bitmap index is simply a count of the number of bitmap chunks in that index) the optimizer simply makes a guess about the data scatter. Roughly speaking it assumes that 80% of the rows identified through a bitmap predicate will be very well clustered, and that the remaining 20% will be widely scattered. Inevitably the resulting cost estimate of using the bitmap approach will be far too high in some cases and far too low in others.<\/p>\n
    Or-Expansion plans<\/h2>\n
    Since the example allows the optimizer to use btree\/bitmap conversion, the query will need a hint to disable that choice. Unfortunately, there\u2019s no explicit hint to switch the mechanism off (you can force it to appear with the \/*+ index_combine(alias) *\/<\/em><\/strong> hint but there\u2019s no \u201cno_index_combine()\u201d<\/em> hint), so it\u2019s necessary to fall back on the opt_param()<\/em><\/strong> hint to modify one of the optimizer parameters for the duration of the query.<\/p>\n
    Since I\u2019m running 19.11.0.0 I\u2019m going to run two more versions of the sample query \u2013 the first simply disables the btree\/bitmap feature, the second also takes the optimizer back to the 12.1.0.2 optimizer feature level:<\/p>\n
    select  \/*+ opt_param('_b_tree_bitmap_plans','false') *\/  \r\n        v1, n1949, n1951 \r\nfrom    t1 \r\nwhere   n1949 = 3 or n1951 = 3;\r\n\r\nselect  \/*+ \r\n                opt_param('_b_tree_bitmap_plans','false') \r\n                optimizer_features_enable('12.1.0.2') \r\n        *\/ \r\n        v1, n1949, n1951 \r\nfrom    t1 \r\nwhere   n1949 = 3 or n1951 = 3;<\/pre>\n
    Here are the resulting plans \u2013 first the baseline 19.11.0.0 plan showing the newer Or-Expansion:<\/p>\n
    <\/p>\n
    And here\u2019s the 12.1.0.2 plan showing \u201cLegacy\u201d Or-Expansion (i.e. Concatenation<\/em><\/strong>):<\/p>\n
    \u00a0<\/p>\n
    The plans are clearly similar \u2013 both show two index range scans and the access predicate associated with each range scan uses the obvious index.<\/p>\n
    Both plans report an unusual filter <\/strong>predicate of the form lnnvl(column = constant)<\/code> \u2013 and if you check the plan body and Predicate Information you\u2019ll notice that this lnnvl()<\/strong> predicate is used during access to the second child of the Concatenation\/Union All, but the \u201cpredicate within a predicate\u201d<\/em> echoes the predicate used during access to the first child of the plan. This is Oracle making sure that rows that were reported in the first part of the Concatenation\/Union All do not get repeated by the second part.<\/p>\n
    The lnnvl()<\/strong> function takes a predicate<\/strong> as its single parameter, returning FALSE<\/code> if the input predicate evaluates to TRUE<\/code>, and TRUE<\/code> if the predicate evaluates to FALSE<\/code> or NULL<\/code>. Effectively it is the \u201cis not true()\u201d<\/em> function, engineered to work around some of the difficulties caused by SQL\u2019s \u201cthree-value logic\u201d.<\/em><\/p>\n
    There are several cosmetic differences between the plans \u2013 the view VW_ORE_xxxxxxxx<\/code> makes it very clear that the plan includes Or-Expansion, and there\u2019s an explicit UNION ALL<\/code> operation that shows very clearly how Oracle is operating. One curious difference is the reversal of the order in which the original predicates become the separate branches of the transformed query \u2013 there doesn\u2019t appear to be any clever arithmetic involved, it just seems to be a switch from bottom-up to top-down.<\/p>\n
    As a side note \u2013 this does mean that when you upgrade from a \u201cConcatenation version\u201d of Oracle\u201d to Or-Expansion a query that you\u2019ve written to \u201cselect first N rows\u201d without including an \u201corder by\u201d<\/em> clause may now return a different set of rows.<\/p>\n
    In effect, Or-Expansion has taken the original text and transformed it into a select from a UNION ALL<\/code> view (text extracted from the CBO trace file and edited for readability \u2013 \u201ctest_user\u201d was the name of the schema running the demo):<\/p>\n
    SELECT \r\n        VW_ORE_BA8ECEFB.ITEM_1 V1,\r\n        VW_ORE_BA8ECEFB.ITEM_2 N1949,\r\n        VW_ORE_BA8ECEFB.ITEM_3 N1951 \r\nFROM    (\r\n           (\r\n           SELECT T1.V1 ITEM_1, T1.N1949 ITEM_2, T1.N1951 ITEM_3\r\n           FROM TEST_USER.T1 T1 \r\n           WHERE T1.N1949=3\r\n           )\r\n           UNION ALL\r\n           (\r\n           SELECT T1.V1 ITEM_1, T1.N1949 ITEM_2, T1.N1951 ITEM_3 \r\n           FROM TEST_USER.T1 T1 \r\n           WHERE T1.N1951=3 AND LNNVL(T1.N1949=3)\r\n                )\r\n        )       VW_ORE_BA8ECEFB\r\n; <\/pre>\n
    In more complex queries, of course, once this transformation has been done the optimizer may find ways other parts of the query can be transformed with the different query blocks embedded in this UNION ALL<\/code> view. Again, this may cause some surprises when an upgrade takes you from Concatenation to Or-Expansion: plans may change because there are more cases where the optimizer can apply the basic expansion then carry on doing further transformations to individual branches of the UNION ALL<\/code>.<\/p>\n
    Or-Expansion threats<\/h2>\n
    A critical difference between Concatenation and Or-Expansion is that the OR\u2019ed access predicates for the driving table must all be indexed before Concatenation can be used. The same restriction is not required for Or-Expansion and this means the optimizer will spend more time considering more execution plans while optimizing the query. Consider a query joining table tA<\/code> and table tB<\/code> with the following where clause:<\/p>\n
    SELECT  {list of columns}\r\nFROM\r\n        tA, tB\r\nWHERE\r\n        (tA.indexed_column = 'Y' or tA.unindexed_column = 'N')\r\nAND     tB.join_column = tA.join_column\r\nAND     tB.another_indexed_column = 'X'\r\n;<\/pre>\n
    This could be expanded to:<\/p>\n
    WHERE\r\n         tA.indexed_column = 'Y'\r\nAND      tB.join_column = tA.join_column\r\nAND      tB.another_indexed_column = 'X'\r\n...\r\nUNION ALL\r\n...\r\nWHERE\r\n         tA.unindexed_column = 'N'\r\nAND      tB.join_column = tA.join_column\r\nAND      tB.another_indexed_column = 'X'\r\nAND      lnnvl(tA.indexed_column = 'Y')<\/pre>\n
    This expansion would not be legal for Concatenation because (as indicated by the choice of column names) there is no indexed access path for the predicate tA.unindexed_column = ‘N’<\/em>, but Or-Expansion would allow the transformation. At first sight that might seem like a silly choice \u2013 but now that the optimizer has two separate query blocks to examine, one of the options open to it is to produce a plan where the first query block uses an index into tA<\/code> followed by a nested loop into tB<\/code> while the second query block uses an index into tB<\/code> followed by a nested loop into tA<\/code>.<\/p>\n
    Generally we would expect the improved performance of the final plan to more than offset the extra time the optimizer spends investigating the extra execution plans but there are patterns where the optimizer tries too hard and things can go badly wrong; here\u2019s an example from a few years ago that modelled a production performance problem:<\/p>\n
    drop table t1 purge;\r\n\r\nCREATE TABLE t1\r\nAS\r\nWITH GENERATOR AS (\r\n        SELECT  --+ materialize\r\n                rownum id \r\n        FROM   dual \r\n        CONNECT BY \r\n                level <= 1e4\r\n)\r\nSELECT\r\n        rownum          id1,\r\n        rownum          id2,\r\n        rownum          id,\r\n        lpad(rownum,10) v1,\r\n        rpad('x',100)   padding\r\nFROM\r\n        generator       v1,\r\n        generator       v2\r\nWHERE\r\n        rownum <= 1e5   -- > comment to avoid \r\n                        -- wordpress format issue\r\n;\r\n\r\nCREATE INDEX t1_i1 ON t1(id1, id2);\r\n\r\nSELECT * FROM t1 WHERE\r\n   ( id1 =  1001 AND id2 in (1,2))\r\nOR ( id1 =  1002 AND id2 in (2,3))\r\n...\r\nOR ( id1 =  1249 AND id2 in (249,250))\r\nOR ( id1 =  1250 AND id2 in (250,251))\r\n;<\/pre>\n
    I\u2019ve removed 246 lines from the query but you can probably see the pattern from the remaining 4 predicates. I didn\u2019t write this query by hand, of course, I wrote a query to generate it. If you want to see the entire script (with some variations) you can find it at https:\/\/jonathanlewis.wordpress.com\/2013\/05\/13\/parse-time\/<\/a><\/p>\n
    Running version 19.11 on my sandbox this query took 21.2 seconds to parse (optimize) out of a total run time of 22.1 seconds. The session also demanded 453 MB of PGA (Program Global Area<\/a>) memory while optimizing the query. The execution plan was a full tablescan \u2013 but the optimizer spent most of its time costing Or-Expansion before discarding that option and picking a simple tablescan path.<\/p>\n
    After a little trial and error I reduced the number of predicates to 206 at which point the plan switched from a full tablescan to using Or-Expansion (the cost was 618 for Or-Expansion and 619 for a hinted full tablescan, at 207 predicates the costs were 221 and 220 respectively). The counter-intuitive side effect of this change was to increase<\/em><\/strong> the optimization time to 27 seconds and the memory demand to 575MB. The reason for this was that having discovered that the initial OR-Expansion produced a lower cost than the tablescan the optimizer then evaluated a number of further transformations of the resulting UNION ALL<\/code> view to see if it could produce an even lower cost.<\/p>\n
    Apart from the increase in the workload associated with the Or-Expansion another threat comes from an error in the estimate of CPU usage at actual run-time. Here are a few lines from the body of the execution plan with 206 predicates, and a few lines from the Predicate Information for just the last operation in the plan:<\/p>\n
    <\/p>\n
    The plan includes 206 separate query blocks that do a basic index range scan with table access (I\u2019ve shown just two of them) and as you work down the list the filter() predicate for each index range scan gets one more set of lnnvl()<\/em><\/strong> predicates than the previous one. In fact, by time the optimizer got to operation 128 \u2013 which is from the 63rd<\/sup> query block in the Union All \u2013 the number of bytes allowed in v$sql_plan<\/em><\/strong> for reporting the filter predicate was too few to hold the entire predicate and, as you can see at the end of the sample above, the filter predicate has stopped at references to the values 61 and 62, and is nowhere near the values 206 and 207 which would have appeared in the last line of the original SQL statement. There\u2019s a lot of lnnvl() checking that has to go on as the number of branches in the expansion increases \u2013 and that\u2019s going to be burning up CPU at run-time.<\/p>\n
    To block the transformation and cut down the optimization time, all that was needed was the addition of the hint \/*+ no_or_expand(@sel$1) *\/<\/em><\/strong> to the query (sel$1 because I hadn\u2019t used the qb_name()<\/em><\/strong> hint to give the query a programmer-friendly name) and this reduced the parse time from 27 seconds to 0.4 seconds and the memory demand to 7 MB.<\/p>\n
    Side note:<\/strong> It\u2019s worth pointing out that when you run<\/strong> a query the memory used for optimization is in your PGA, and the memory you\u2019re using will reduce the \u201caggregate PGA auto target\u201d which affects the limit for every other user. On the other hand if you call \u201cexplain plan\u201d<\/strong> to generate an execution plan without executing the query the memory used comes from the SGA (i.e. the shared pool), which means that when the optimizer goes a little mad with Or-Expansion your session may flush lots of useful information from the library cache, with far greater impact on the entire system. This is just one more reason for not<\/strong> depending on \u201cexplain plan\u201d to give you execution plans.<\/p>\n
    If you\u2019re responsible for the performance of a system, there are some clues about the overheads of optimization in extreme cases. One point to check is the active session history (ASH \u2013 v$active_session_history<\/code> or dba_hist_active_sess_history<\/code>) where you could aggregate SQLexecutions<\/code> to check for statements that record more than one sample in a hard parse, e.g:<\/p>\n
    break on sql_id skip 1\r\nselect \r\n        sql_id, sql_exec_id, in_hard_parse, count(*) \r\nfrom \r\n        v$active_session_history \r\ngroup by \r\n        sql_id, sql_exec_id, in_hard_parse\r\nhaving \r\n        count(*) > 1\r\norder by \r\n        1,2,3<\/pre>\n
    This returns<\/p>\n
    SQL_ID        SQL_EXEC_ID I   COUNT(*)\r\n------------- ----------- - ----------\r\n1v1mm1224up26             Y         18\r\n2kt6gcu4ns3kq             N          2\r\n                          Y         64\r\n7zc0gjc4uamz6             Y         21\r\nd47kdkn618bu4    16777216 Y          2\r\ng1rvj7fumzxda    16777216 N          4\r\n<\/pre>\n
    This isn\u2019t a perfect search, unfortunately \u2013 if a statement is parsing, then it\u2019s not yet executing so it doesn\u2019t have an execution id (sql_exec_id<\/em><\/strong>), so when you see that sql_id<\/em><\/strong>\u201c2kt6gcu4ns3kq\u201d<\/em> has recorded 64 samples \u201cin hard parse\u201d that might mean there have been lots of short hard parses (though that\u2019s a little suspicious anyway) or a few long hard parses. You\u2019d have to drill into sample times to get a better idea of what the larger numbers are telling you (64 consecutive sample times would be a fairly strong indication the statement was a threat).<\/p>\n
    Another thing you can check retrospectively is the alert log,<\/em><\/strong> as this may tell you about the memory aspect of extreme optimization problems. Here\u2019s a short extract from my alert log following one of my nasty parse calls:<\/p>\n
    This isn\u2019t saying anything about the hundreds of megabytes of PGA memory I\u2019ve been using, it\u2019s saying that someone pushed a \u201clarge object\u201d<\/em> into the SGA \u2013 but there\u2019s a chance that an object that large is interesting and you\u2019ll want to find out what it was, and the last few lines in the extract show that this one was an SQL statement that looks familiar. (The 51200K mentioned as the \u201cnotification threshold\u201d<\/em> is set by the hidden parameter _kgl_large_heap_warning_threshold<\/em><\/strong>.)<\/p>\n
    <\/p>\n
    Summary<\/h2>\n
    The Concatenation operation from earlier versions of Oracle has been superseded by the Or-Expansion operation, which is more flexible and can allow further transformations to be applied after the initial transformation in more ways than were available following the Concatenation operator. Or-Expansion is easily visible in execution plans, reporting a VIEW<\/code> operation with a name like VW_ORE_xxxxxxxx<\/code> followed by a UNION ALL<\/code> operation.<\/p>\n
    On the plus side, some queries will be able to execute much more efficiently because the optimizer can find better plans for the different branches of the expansion; on the minus side the time spent in optimization can increase significantly and there will be cases where the cost of optimisation far outweighs the benefit of the faster execution. Although the CPU and elapsed time are the obvious costs of the optimization stage of Or-Expansion it is important to keep an eye on the demands for PGA that can also appear, so queries which have a large number of \u201cOR\u2019ed\u201d predicates should be viewed with caution \u2013 and this includes queries with long \u201cIN\u201d lists, though the simplest type of IN-lists are likely to be transformed into \u201cINLIST ITERATORS\u201d rather than UNION ALL<\/code> operations.<\/p>\n
    If you find cases where the optimizer persistently tries to use Or-Expansion when it\u2019s a bad idea you can use the hint \/*+ no_or_expand(@qbname) *\/<\/code> to block the expansion. The hint \/*+ or_expand() *\/ <\/code>is also available to force Or-Expansion (but it\u2019s not a hint to use casually). If you aren\u2019t allowed to block Or-Expansion through a hint or SQL patch then you could consider disabling the feature entirely by setting the hidden parameter _no_or_expansion<\/strong> to true at the system or session level.<\/p>\n","protected":false},"excerpt":{"rendered":"
    The previous installment of this series examined aggregate subquery removal and subquery coalescing, describing the latter as similar in some ways to an inverse for \u201cOr Expansion\u201d and \u201cJoin Factorization\u201d. In this instalment, it\u2019s time to take a closer look at Or Expansion and we\u2019ll move on to Join Factorization in the next instalment.…<\/p>\n","protected":false},"author":101205,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[53,143533],"tags":[5380,4459],"coauthors":[39048],"class_list":["post-94938","post","type-post","status-publish","format-standard","hentry","category-featured","category-oracle-databases","tag-optimization","tag-oracle"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/94938","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\/101205"}],"replies":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/comments?post=94938"}],"version-history":[{"count":10,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/94938\/revisions"}],"predecessor-version":[{"id":95037,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/94938\/revisions\/95037"}],"wp:attachment":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/media?parent=94938"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/categories?post=94938"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/tags?post=94938"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/coauthors?post=94938"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}