While analyzing a performance issue with a 63-table join query (you gotta love Siebel) I came accross a little optimizer oddity. Looking at a 600MB optimizer trace was fun, though \ud83d\ude09<\/p>\n
The problem boiled down to this:<\/p>\n
\r\n------------------------------------------------------------------------------------------\r\n| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |\r\n------------------------------------------------------------------------------------------\r\n| 0 | SELECT STATEMENT | | 83 | 6225 | 10 (0)| 00:00:01 |\r\n| 1 | NESTED LOOPS OUTER | | 83 | 6225 | 10 (0)| 00:00:01 |\r\n|* 2 | TABLE ACCESS STORAGE FULL | T1 | 2 | 20 | 9 (0)| 00:00:01 |\r\n| 3 | TABLE ACCESS BY INDEX ROWID| T2 | 41 | 2665 | 1 (0)| 00:00:01 |\r\n|* 4 | INDEX UNIQUE SCAN | T2_IDX_01 | 1 | | 0 (0)| 00:00:01 |\r\n------------------------------------------------------------------------------------------\r\n<\/pre>\nWould you expect the cardinality estimate for table access on T2 (plan Id 3) to be 41?
\nI certainly wouldn’t. It’s doing an INDEX UNIQUE SCAN on index T2_IDX_01 (plan Id 4) and according to the cardinality estimate on T2 (plan Id 2) it will do that INDEX UNIQUE SCAN two times.
\nWhy does the optimizer think it will get 41 rows per given ID value in the index while obviously a UNIQUE INDEX SCAN can only return 0 or 1 ROWID?<\/p>\nFrom the large Siebel query I managed to deduce a simple test case:<\/p>\n
\r\ncreate table t1 (\r\n id number(10) not null\r\n , id2 number(10) not null\r\n , id3 number(10)\r\n , constraint t1_pk primary key (id)\r\n using index (create unique index t1_idx_01 on t1 (id))\r\n);\r\n\r\ncreate table t2 (\r\n id number(10)\r\n , text varchar2(100)\r\n , constraint t2_pk primary key (id)\r\n using index (create unique index t2_idx_01 on t2 (id))\r\n);\r\n<\/pre>\nOnly table T1 is populated with data. Column ID3 will be 50% NULL values, the other 50% will be “1”.<\/p>\n
\r\ninsert into t1 (id, id2, id3)\r\nselect\r\n rownum id\r\n , rownum id2\r\n , decode(mod(rownum, 2), 0, null, 1) id3\r\nfrom dual connect by level <= 10000\r\n;\r\ncommit;\r\n\r\n-- gather stats on T1 and related indexes without histograms\r\nexec dbms_stats.gather_table_stats(user, 'T1', cascade => true, method_opt => 'FOR ALL COLUMNS SIZE 1')\r\n<\/pre>\nAnd that’s the query which produced above execution plan:<\/p>\n
\r\nselect *\r\nfrom t1\r\n , t2\r\nwhere t1.id2 in (10, 20)\r\nand t1.id3 = t2.id(+)\r\n;\r\n<\/pre>\nPerhaps you noticed that I didn’t gather statistics for table T2, which was exactly the sitution I had in the Siebel database. Several tables involved in the 63-table join did not have statistics on them.
\nIn case you’re wondering, according to Oracle’s Siebel “best practice” you’re not supposed to have statistics on tables with less than 15 rows in them (see Oracle’s script coe_siebel_stats.sql v11.4.4.6).<\/p>\nNow, back to the orginal question: How does Oracle come up with 41?
\nFirst<\/strong>, for any table that does not have statistics Oracle seems to assume a cardinality of 82. I don’t know where that magic number comes from. Maybe it simply takes 1% of 8192, the default database block size.
\nThe extract from optimizer trace shows table T2 is not analyzed and contains 82 rows:<\/p>\n\r\nBASE STATISTICAL INFORMATION\r\n***********************\r\nTable Stats::\r\n Table: T2 Alias: T2 (NOT ANALYZED)\r\n #Rows: 82 SSZ: 0 LGR: 0 #Blks: 1 AvgRowLen: 100.00 NEB: 0 ChainCnt: 0.00 SPC: 0 RFL: 0 RNF: 0 CBK: 0 CHR: 0 KQDFLG: 0\r\n #IMCUs: 0 IMCRowCnt: 0 IMCJournalRowCnt: 0 #IMCBlocks: 0 IMCQuotient: 0.000000\r\n Column (#1): ID(NUMBER) NO STATISTICS (using defaults)\r\n AvgLen: 13 NDV: 3 Nulls: 0 Density: 0.390244\r\n\r\n...\r\nSINGLE TABLE ACCESS PATH \r\n...\r\n Table: T2 Alias: T2\r\n Card: Original: 82.000000 Rounded: 82 Computed: 82.000000 Non Adjusted: 82.000000\r\n<\/pre>\nAlso, the optimizer guesses the NDV(3) and number of nulls(0) for the ID column of table T2.<\/p>\n
… if you think it simply divides 82 by 2, read on \ud83d\ude42 …<\/p>\n
Secondly<\/strong>, after studying different data patterns I think this is what happens.
\nBecause of above outlined assumptions the adjusted selectivty for T2 will always be 1 in the join selectivity calculation.
\nAnd, since we have a low NDV on T1.ID3 we end up with a gross misestimate for the join selectivity.<\/p>\n\r\njoin-sel =\r\n ((num_rows(t1) - num_nulls(t1.id3) \/ num_rows(t1)) *\r\n ((num_rows(t2) - num_nulls(t2.id) \/ num_rows(t2)) \/\r\n greater(num_distinct(t1.id3), num_distinct(t2.id))\r\n\r\njoin-sel =\r\n ((10000 - 5000 \/ 10000) *\r\n ((82 - 0 \/ 82) \/\r\n greater(1, 3)\r\n = 0.16666666666666666666666666666667\r\n<\/pre>\nFrom the optimzer trace we see that the join selectivity of 0.500000 does not exactly match our calculation. Interestingly, the optimizer seems to ignore the guessed NDV of 3 for T2.ID and instead use the NDV from T1.ID3, which would give you 0.5.<\/p>\n
\r\nOuter Join Card: 83.000000 = max ( outer (2.000000),(outer (2.000000) * inner (82.000000) * sel (0.500000)))\r\n<\/pre>\nSo here it is, we’ve got our number 41: (82.000000) * sel (0.500000)<\/p>\n
Note, the table access cardinality (plan Id 3) is based on the join selectivity which doesn’t account for the in-list predicate on T1, as one would expect. The in-list is accounted for in the filtered table cardinality of table T1 and so is reflected in the join cardinality (plan Id 1).<\/p>\n
Lastly<\/strong>, the cardinality estimate for plan Id 3 (TABLE ACCESS BY INDEX ROWID) is independently calculated from plan Id 4 (INDEX UNIQUE SCAN). I think there should be a sanity check to adjust the estimate for the table access to T2 (plan Id 3) when the row source is fed by an INDEX UNIQUE SCAN.<\/p>\n
Here’s another example:<\/p>\n
\r\ninsert into t1 (id, id2, id3)\r\nselect\r\n rownum id\r\n , rownum id2\r\n , decode(mod(rownum, 4), 0, null, dbms_random.value(1, 6)) id3\r\nfrom dual connect by level <= 10000\r\n;\r\ncommit;\r\n\r\n-- gather stats on T1 without histograms\r\nexec dbms_stats.gather_table_stats(user, 'T1', cascade => true, method_opt => 'FOR ALL COLUMNS SIZE 1')\r\n<\/pre>\nThis time, column ID3 contains 25% NULL values, the other 75% are evenly distributed between “1” and “6”.<\/p>\n
\r\nSQL> select column_name, histogram, num_distinct, density, num_nulls from dba_tab_columns where table_name = 'T1' order by column_name;\r\n\r\nCOLUMN_NAME HISTOGRAM NUM_DISTINCT DENSITY NUM_NULLS\r\n------------------------------ --------------- ------------ ---------- ----------\r\nID NONE 10000 .0001 0\r\nID2 NONE 10000 .0001 0\r\nID3 NONE 6 .166666667 2500\r\n<\/pre>\nSo, according to above formulae & data it would go like this:<\/p>\n
\r\njoin-sel =\r\n ((10000 - 25000 \/ 10000) *\r\n ((82 - 0 \/ 82) \/\r\n greater(6, 3)\r\n = 0.125\r\n\r\ncard = round(82 * 0.125) = 10\r\n<\/pre>\nAgain, the optimizer trace confirms the calculation, this time it’s spon-on because it again uses the NDV from T1.ID3 (which is greater than 3 anyway):<\/p>\n
\r\nOuter Join Card: 21.000000 = max ( outer (2.000000),(outer (2.000000) * inner (82.000000) * sel (0.125000)))\r\n<\/pre>\n\r\n------------------------------------------------------------------------------------------\r\n| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |\r\n------------------------------------------------------------------------------------------\r\n| 0 | SELECT STATEMENT | | 21 | 1596 | 10 (0)| 00:00:01 |\r\n| 1 | NESTED LOOPS OUTER | | 21 | 1596 | 10 (0)| 00:00:01 |\r\n|* 2 | TABLE ACCESS STORAGE FULL | T1 | 2 | 22 | 9 (0)| 00:00:01 |\r\n| 3 | TABLE ACCESS BY INDEX ROWID| T2 | 10 | 650 | 1 (0)| 00:00:01 |\r\n|* 4 | INDEX UNIQUE SCAN | T2_IDX_01 | 1 | | 0 (0)| 00:00:01 |\r\n------------------------------------------------------------------------------------------\r\n<\/pre>\nThe case for the Siebel query was little more complex but ulitmately it was the magic number 82 that caused the optimizer to choose a inefficient join order.<\/p>\n","protected":false},"excerpt":{"rendered":"
While analyzing a performance issue with a 63-table join query (you gotta love Siebel) I came accross a little optimizer oddity. Looking at a 600MB optimizer trace was fun, though \ud83d\ude09 The problem boiled down to this: —————————————————————————————— | Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time | —————————————————————————————— | […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,13],"tags":[],"class_list":["post-275","post","type-post","status-publish","format-standard","hentry","category-internals","category-things-that-happen"],"_links":{"self":[{"href":"https:\/\/www.spotonoracle.com\/index.php?rest_route=\/wp\/v2\/posts\/275","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.spotonoracle.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.spotonoracle.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.spotonoracle.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.spotonoracle.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=275"}],"version-history":[{"count":8,"href":"https:\/\/www.spotonoracle.com\/index.php?rest_route=\/wp\/v2\/posts\/275\/revisions"}],"predecessor-version":[{"id":283,"href":"https:\/\/www.spotonoracle.com\/index.php?rest_route=\/wp\/v2\/posts\/275\/revisions\/283"}],"wp:attachment":[{"href":"https:\/\/www.spotonoracle.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=275"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.spotonoracle.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=275"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.spotonoracle.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=275"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}