Following up my “Hacking for Skew” article from a couple of days ago, Chinar Aliyev has written an article about a method for persuading the optimizer to calculate the correct cardinality estimate without using any undocumented, or otherwise dubious, mechanisms. His method essentially relies on the optimizer’s mechanism for estimating join cardinality when there are histograms at both ends of the join so I thought I’d write a short note describing the simplest possible example of the calculation – an example where the query is a single column equi-join with no nulls in either column and a perfect frequency histograms at both ends of the join. (For a detailed description of more general cases I always refer to the work done by Alberto Dell’Era a few years ago). We start with two data sets that exhibit a strong skew in their data distributions:
rem rem Script: freq_hist_join_02.sql rem Author: Jonathan Lewis rem Dated: Oct 2018 rem execute dbms_random.seed(0) create table t1 nologging as with generator as ( select rownum id from dual connect by level <= 1e4 -- > comment to avoid WordPress format issue ) select rownum id, trunc(3 * abs(dbms_random.normal)) n1 from generator v1 ; create table t2 nologging as with generator as ( select rownum id from dual connect by level <= 1e4 -- > comment to avoid WordPress format issue ) select rownum id, trunc(3 * abs(dbms_random.normal)) n1 from generator v1 ; begin dbms_stats.gather_table_stats( ownname => null, tabname => 'T1', method_opt => 'for all columns size 254' ); dbms_stats.gather_table_stats( ownname => null, tabname => 'T2', method_opt => 'for all columns size 254' ); end; /
I’ve generated two tables of 10,000 randomly generated values using the dbms_random.normal() function, but I’ve scaled the value up by a factor of three and taken the absolute value – which has given me a range of 12 distinct integer values with a nicely skewed distribution. Then I’ve gathered stats requesting histograms of up to 254 buckets. Since I’ve tested this only on versions from 11.2.0.4 onwards this means I’ll get a perfect histogram on the n1 columns on both tables.
Now I’m going run a query that reports the values and frequencies from the two tables by querying user_tab_histograms using a variant of an analytic query I published a long time ago to convert the cumulative frequencies recorded as the endpoint values into simple frequencies. If, for some reason, this query doesn’t run very efficiently in your tests you could always /*+ materialize */ the two factored subqueries (CTEs – common table expressions):
prompt ======================================================================= prompt Multiply and sum matching frequencies. An outer join is NOT needed prompt because rows that don't match won't contributed to the join cardinality prompt ======================================================================= break on report skip 1 compute sum of product on report column product format 999,999,999 with f1 as ( select endpoint_value value, endpoint_number - lag(endpoint_number,1,0) over(order by endpoint_number) frequency from user_tab_histograms where table_name = 'T1' and column_name = 'N1' order by endpoint_value ), f2 as ( select endpoint_value value, endpoint_number - lag(endpoint_number,1,0) over(order by endpoint_number) frequency from user_tab_histograms where table_name = 'T2' and column_name = 'N1' order by endpoint_value ) select f1.value, f1.frequency, f2.frequency, f1.frequency * f2.frequency product from f1, f2 where f2.value = f1.value ; VALUE FREQUENCY FREQUENCY PRODUCT ---------- ---------- ---------- ------------ 0 2658 2532 6,730,056 1 2341 2428 5,683,948 2 1828 1968 3,597,504 3 1305 1270 1,657,350 4 856 845 723,320 5 513 513 263,169 6 294 249 73,206 7 133 117 15,561 8 40 54 2,160 9 23 17 391 10 5 5 25 11 4 2 8 ------------ sum 18,746,698
As you can see, the two columns do have a highly skewed data distribution. The pattern of the two data sets is similar though the frequencies aren’t identical, of course. The total I get from this calculation is (I claim) the cardinality (rows) estimate that the optimizer will produce for doing an equi-join on these two tables – so let’s see the test:
set serveroutput off alter session set statistics_level = all; alter session set events '10053 trace name context forever'; select count(*) from t1, t2 where t1.n1 = t2.n1 ; select * from table(dbms_xplan.display_cursor(null,null,'allstats last')); alter session set statistics_level = typical; alter session set events '10053 trace name context off';
And the resulting output:
Session altered. Session altered. COUNT(*) ---------- 18746698 PLAN_TABLE_OUTPUT ------------------------------------------------------------------------------------------------------------------------------------ SQL_ID 0wxytnyqs4b5j, child number 0 ------------------------------------- select count(*) from t1, t2 where t1.n1 = t2.n1 Plan hash value: 906334482 ----------------------------------------------------------------------------------------------------------------- | Id | Operation | Name | Starts | E-Rows | A-Rows | A-Time | Buffers | OMem | 1Mem | Used-Mem | ----------------------------------------------------------------------------------------------------------------- | 0 | SELECT STATEMENT | | 1 | | 1 |00:00:03.23 | 40 | | | | | 1 | SORT AGGREGATE | | 1 | 1 | 1 |00:00:03.23 | 40 | | | | |* 2 | HASH JOIN | | 1 | 18M| 18M|00:00:02.96 | 40 | 2616K| 2616K| 2098K (0)| | 3 | TABLE ACCESS FULL| T1 | 1 | 10000 | 10000 |00:00:00.01 | 20 | | | | | 4 | TABLE ACCESS FULL| T2 | 1 | 10000 | 10000 |00:00:00.01 | 20 | | | | ----------------------------------------------------------------------------------------------------------------- Predicate Information (identified by operation id): --------------------------------------------------- 2 - access("T1"."N1"="T2"."N1")
As we can see, the estimate for the hash join is “18M” which is in the right ballpark but, in its current format, isn’t entirely helpful which is why I’ve enabled the 10053 trace to get an exact figure from the trace file, and this is what we see:
*********************** Best so far: Table#: 0 cost: 4.352468 card: 9487.000000 bytes: 28461.000000 Table#: 1 cost: 378.482370 card: 18467968.000000 bytes: 110807808.000000 ***********************
The optimizer’s estimate is exactly the sum of the products of the frequencies of matching values from the (frequency) histogram data. There is a simple rationale for this – it gets the right answer.
For each row in t1 with value ‘X’ the (frequency) histogram on t2 tells Oracle how many rows will appear in the join, so multiplying the frequency of ‘X’ in t1 by the frequency of ‘X’ in t2 tells Oracle how many rows the ‘X’s will contribute to the join. Repeat for every distinct value that appears in both (frequency) histograms and sum the results.
As a refinement on this (very simple) example, let’s delete data from the two tables so that we have rows in t1 that won’t join to anything in t2, and vice versa – then re-gather stats, query the histograms, and check the new prediction. We want to check whether a value that appears in the t1 histogram contributes to the join cardinality estimate even if there are no matching values in the t2 histogram (and vice versa):
delete from t1 where n1 = 4; delete from t2 where n1 = 6; execute dbms_stats.gather_table_stats(user,'t1',method_opt=>'for all columns size 254', no_invalidate=>false) execute dbms_stats.gather_table_stats(user,'t2',method_opt=>'for all columns size 254', no_invalidate=>false) with f1 as ( select endpoint_value value, endpoint_number - lag(endpoint_number,1,0) over(order by endpoint_number) frequency from user_tab_histograms where table_name = 'T1' and column_name = 'N1' order by endpoint_value ), f2 as ( select endpoint_value value, endpoint_number - lag(endpoint_number,1,0) over(order by endpoint_number) frequency from user_tab_histograms where table_name = 'T2' and column_name = 'N1' order by endpoint_value ) select f1.value, f1.frequency, f2.frequency, f1.frequency * f2.frequency product from f1, f2 where f2.value = f1.value ; set serveroutput off alter session set statistics_level = all; alter session set events '10053 trace name context forever'; select count(*) from t1, t2 where t1.n1 = t2.n1 ; select * from table(dbms_xplan.display_cursor(null,null,'allstats last')); alter session set statistics_level = typical; alter session set events '10053 trace name context off';
And the output – with a little cosmetic tidying:
856 rows deleted. 249 rows deleted. PL/SQL procedure successfully completed. PL/SQL procedure successfully completed. VALUE FREQUENCY FREQUENCY PRODUCT ---------- ---------- ---------- ------------ 0 2658 2532 6,730,056 1 2341 2428 5,683,948 2 1828 1968 3,597,504 3 1305 1270 1,657,350 5 513 513 263,169 7 133 117 15,561 8 40 54 2,160 9 23 17 391 10 5 5 25 11 4 2 8 ------------ sum 17,950,172 Session altered. Session altered. COUNT(*) ---------- 17950172 PLAN_TABLE_OUTPUT ------------------------------------------------------------------------------------------------------------------------------------ SQL_ID 0wxytnyqs4b5j, child number 0 ------------------------------------- select count(*) from t1, t2 where t1.n1 = t2.n1 Plan hash value: 906334482 ----------------------------------------------------------------------------------------------------------------- | Id | Operation | Name | Starts | E-Rows | A-Rows | A-Time | Buffers | OMem | 1Mem | Used-Mem | ----------------------------------------------------------------------------------------------------------------- | 0 | SELECT STATEMENT | | 1 | | 1 |00:00:02.89 | 40 | | | | | 1 | SORT AGGREGATE | | 1 | 1 | 1 |00:00:02.89 | 40 | | | | |* 2 | HASH JOIN | | 1 | 17M| 17M|00:00:02.61 | 40 | 2616K| 2616K| 2134K (0)| | 3 | TABLE ACCESS FULL| T1 | 1 | 9144 | 9144 |00:00:00.01 | 20 | | | | | 4 | TABLE ACCESS FULL| T2 | 1 | 9751 | 9751 |00:00:00.01 | 20 | | | | ----------------------------------------------------------------------------------------------------------------- Predicate Information (identified by operation id): --------------------------------------------------- 2 - access("T1"."N1"="T2"."N1") From the 10053 trace file: *********************** Best so far: Table#: 0 cost: 4.340806 card: 9144.000000 bytes: 27432.000000 Table#: 1 cost: 368.100010 card: 17950172.000000 bytes: 107701032.000000 ***********************
You can see from the frequency histogram report that we “lost” values 4 and 6 from the report; then the total from the report matches the actual number of rows returned by the query, and the cardinality estimate in the plan is again in the right ballpark – with the trace file showing an exact match.
I’ve run this test on 11.2.0.4, 12.1.0.2, 12.2.0.1 and 18.3.0.0 (which generated a different set of random values) – and there’s an anomaly that appears in 11.2.0.4 (though maybe that should be “disappeared from”): the optimizer’s estimate for the cardinality was a little larger than the value generated in the query against user_tab_histograms. [Edit: Now explained (probably), see below]
Conclusion:
For an incredibly simple class of queries with perfect frequency histograms there’s a very simple way to calculate the cardinality estimate that the optimizer will predict. Match up rows from the two frequency histograms, multiply the corresponding frequencies (making sure you don’t multiply the cumulative frequencies) and sum.
This is, of course, only a tiny step in the direction of seeing how Oracle uses histograms and covers only a type of query that is probably too simple to appear in a production system, but it’s a basis on which I may build in future notes over the next few weeks.
Update (5th Oct)
The “error” in the 11g calculation irritated me a little, and I woke up this morning with an idea about the solution. In 10.2.0.4 Oracle changed the way the optimizer calculated for a predicate that used a value that did not appear in the frequency histogram: it did the arithmetic for “half the least frequently occurring value”. So I thought I’d run up a test where for my “sum of products” query I emulated this model. I had to change my query to an “ANSI”-style full outer join, and here it is:
with f1 as ( select endpoint_value value, endpoint_number - lag(endpoint_number,1,0) over(order by endpoint_number) frequency from user_tab_histograms where table_name = 'T1' and column_name = 'N1' ), f2 as ( select endpoint_value value, endpoint_number - lag(endpoint_number,1,0) over(order by endpoint_number) frequency from user_tab_histograms where table_name = 'T2' and column_name = 'N1' ) select f1.value, f2.value, nvl(f1.frequency, 0) t1_frequency, nvl(f2.frequency, 0) t2_frequency, nvl(f1.frequency, &t1_least / 2) * nvl(f2.frequency, &t2_least / 2) product from f1 full outer join f2 on f2.value = f1.value order by coalesce(f1.value, f2.value) ;
Running this code, and noting that the lowest frequency in t1 was 4, while the lowest frequency in t2 was 2, I got the following results (with the 10053 trace file summary following the output)
VALUE VALUE T1_FREQUENCY T2_FREQUENCY PRODUCT ---------- ---------- ------------ ------------ ------------ 0 0 2658 2532 6,730,056 1 1 2341 2428 5,683,948 2 2 1828 1968 3,597,504 3 3 1305 1270 1,657,350 4 0 845 1,690 5 5 513 513 263,169 6 294 0 294 7 7 133 117 15,561 8 8 40 54 2,160 9 9 23 17 391 10 10 5 5 25 11 11 4 2 8 ------------ ------------ ------------ sum 9144 9751 17,952,156 Join Card: 17952157.000000 = outer (9751.000000) * inner (9144.000000) * sel (0.201341) Join Card - Rounded: 17952157 Computed: 17952157.00
That’s a pretty good match to the trace file result – and the difference of 1 may simply be a rounding error (despite the trace files text suggesting it is accurate to 6 d.p.). Maybe one day I’ll wake up with an inspired guess about that difference – but since it’s relevant only to 11g I’m not going to worry about it anymore.
Footnote
Following an exchange of email with Chinar Aliyev, it’s fairly clear that the “half the least frequency” can actually be derived as “table.num_rows * column.density”.
[…] the previous note I posted about Join Cardinality I described a method for calculating the figure that the optimizer would give for the special case […]
Pingback by Join Cardinality – 2 | Oracle Scratchpad — October 5, 2018 @ 3:37 pm BST Oct 5,2018 |
[…] I haven’t tested them yet, but with the code easily available in the article it won’t take long to see what the effects are when I have a few minutes. The first fix may also be why I had a final small discrepancy between 11g and 12c on the join on two columns with frequency histograms. […]
Pingback by Upgrade threat | Oracle Scratchpad — November 1, 2018 @ 9:32 am GMT Nov 1,2018 |
[…] I haven’t tested them yet, but with the code easily available in the article it won’t take long to see what the effects are when I have a few minutes. The first fix may also be why I had a final small discrepancy between 11g and 12c on the join on two columns with frequency histograms. […]
Pingback by Upgrades – again | Oracle Scratchpad — November 1, 2018 @ 9:44 am GMT Nov 1,2018 |
[…] Here’s a query (with result set) that you may recognise from an earlier post. […]
Pingback by In-table predicates | Oracle Scratchpad — April 12, 2019 @ 1:49 pm BST Apr 12,2019 |
[…] Join cardinality with histograms (Oct 2018): Perfect frequency histograms at both ends with no filter predicates. […]
Pingback by Histogram catalogue | Oracle Scratchpad — November 8, 2022 @ 12:58 pm GMT Nov 8,2022 |