Thread
-
Extended statistics improvement: multi-column MCV missing values
Enrique Sánchez <enriqueesanchz@gmail.com> — 2026-05-18T16:09:03Z
Hi, Postgres only uses multi-column MCVs when the value we are looking for is in the list. If not, it falls back into individual independent statistics to estimate selectivity. However, a miss in a multi-column MCV list still yields valuable information that it currently throws away: we know that the combination's frequency is strictly bounded by the frequency of the last (least common) item in that MCV list. Test case ========= ``` -- 1. Create a minimal table DROP TABLE IF EXISTS planner_trap; CREATE TABLE planner_trap ( col_a integer, col_b integer, col_c integer, sort_col integer ); -- 2. 1 becomes the most common value (MCV) for all three columns. INSERT INTO planner_trap (col_a, col_b, col_c, sort_col) SELECT (pow(random(), 5) * 100)::integer + 1, (pow(random(), 5) * 10)::integer + 1, (pow(random(), 5) * 50)::integer + 1, i FROM generate_series(1, 100000) AS i; -- 3. Create indexes CREATE INDEX idx_planner_trap_sort ON planner_trap(sort_col); CREATE INDEX idx_planner_trap_a_b_c ON planner_trap(col_a, col_b, col_c); -- 4. Make the exact combination (1, 1, 1) yield zero rows. This ensures it won't appear -- in the MCV list, even though the value '1' remains the most common for each individual column. UPDATE planner_trap SET col_a = 2 WHERE col_a = 1 AND col_b = 1 AND col_c = 1; -- 5. Create MCV statistics CREATE STATISTICS (mcv) on col_a, col_b, col_c FROM planner_trap; ANALYZE planner_trap; ``` The planner multiplies the individual selectivities and overestimates the row count (5909; actual=0): ``` postgres=# EXPLAIN ANALYZE SELECT * FROM planner_trap WHERE col_a = 1 AND col_b = 1 AND col_c = 1 ORDER BY sort_col DESC LIMIT 10; QUERY PLAN --------------------------------------------------------------------------------------------------------------------------------------------------------------- Limit (cost=0.29..7.72 rows=10 width=16) (actual time=14.632..14.633 rows=0.00 loops=1) Buffers: shared hit=16355 dirtied=1 -> Index Scan Backward using idx_planner_trap_sort on planner_trap (cost=0.29..4386.99 rows=5909 width=16) (actual time=14.630..14.630 rows=0.00 loops=1) Filter: ((col_a = 1) AND (col_b = 1) AND (col_c = 1)) Rows Removed by Filter: 100000 Index Searches: 1 Buffers: shared hit=16355 dirtied=1 Planning: Buffers: shared hit=33 read=1 Planning Time: 0.478 ms Execution Time: 14.651 ms ``` 1. Cap selectivity with the last MCV item's frequency ===================================================== Applying the last MCV cap here, Postgres estimates 117 rows: 0.001167 * 100000 = 117 ``` postgres=# SELECT m.* FROM pg_statistic_ext join pg_statistic_ext_data on (oid = stxoid), pg_mcv_list_items(stxdmcv) m WHERE stxname = 'planner_trap_col_a_col_b_col_c_stat' and index = 99; index | values | nulls | frequency | base_frequency -------+----------+---------+-----------------------+---------------- 99 | {1,1,31} | {f,f,f} | 0.0011666666666666668 | 0.001049409536 ``` making postgres to choose a better plan: ``` Limit (cost=300.72..300.75 rows=10 width=16) (actual time=0.045..0.046 rows=0.00 loops=1) Buffers: shared hit=3 read=2 -> Sort (cost=300.72..301.02 rows=117 width=16) (actual time=0.043..0.044 rows=0.00 loops=1) Sort Key: sort_col DESC Sort Method: quicksort Memory: 25kB Buffers: shared hit=3 read=2 -> Bitmap Heap Scan on planner_trap (cost=5.78..298.19 rows=117 width=16) (actual time=0.026..0.027 rows=0.00 loops=1) Recheck Cond: ((col_a = 1) AND (col_b = 1) AND (col_c = 1)) Buffers: shared read=2 -> Bitmap Index Scan on idx_planner_trap_a_b_c (cost=0.00..5.76 rows=117 width=0) (actual time=0.019..0.020 rows=0.00 loops=1) Index Cond: ((col_a = 1) AND (col_b = 1) AND (col_c = 1)) Index Searches: 1 Buffers: shared read=2 Planning: Buffers: shared hit=51 read=8 dirtied=4 Planning Time: 0.742 ms Execution Time: 0.094 ms ``` 2. Estimate selectivity as Postgres does for single-column values not in MCVs ============================================================================= While that significantly improves estimations, we could mirror what Postgres already does for individual MCVs. Quote from the official documentation: > The approach is to use the fact that the value is not in the list, combined with the knowledge of the frequencies for all of the MCVs: > That is, add up all the frequencies for the MCVs and subtract them from one, then divide by the number of other distinct values. To achieve this, we need to store an ndistinct estimation alongside the MCVs that can be used for partial or entire column match. P(1, 1, 1) = (1 - sum(MCVs)) / (ndistinct(col_a, col_b, col_c) - MCV_list_size) ``` postgres=# SELECT sum(m.frequency) FROM pg_statistic_ext join pg_statistic_ext_data on (oid = stxoid), pg_mcv_list_items(stxdmcv) m WHERE stxname = 'planner_trap_col_a_col_b_col_c_stat'; sum --------------------- 0.39456666666666645 postgres=# SELECT stxkeys AS k, stxdndistinct AS nd FROM pg_statistic_ext join pg_statistic_ext_data on (oid = stxoid) WHERE stxname = 'stts2'; k | nd -------+--------------------------------------------------- 1 2 3 | [...{"attributes": [1, 2, 3], "ndistinct": 8511}] ``` Then (1 - 0.39456666666666645) / (8511 - 100) = 0.000071981; 0.000071981 * 100000 = 7 rows ``` Limit (cost=30.30..30.32 rows=7 width=16) (actual time=0.035..0.036 rows=0.00 loops=1) Buffers: shared hit=2 -> Sort (cost=30.30..30.32 rows=7 width=16) (actual time=0.033..0.034 rows=0.00 loops=1) Sort Key: sort_col DESC Sort Method: quicksort Memory: 25kB Buffers: shared hit=2 -> Bitmap Heap Scan on planner_trap (cost=4.38..30.20 rows=7 width=16) (actual time=0.028..0.029 rows=0.00 loops=1) Recheck Cond: ((col_a = 1) AND (col_b = 1) AND (col_c = 1)) Buffers: shared hit=2 -> Bitmap Index Scan on idx_planner_trap_a_b_c (cost=0.00..4.38 rows=7 width=0) (actual time=0.022..0.022 rows=0.00 loops=1) Index Cond: ((col_a = 1) AND (col_b = 1) AND (col_c = 1)) Index Searches: 1 Buffers: shared hit=2 Planning Time: 0.192 ms Execution Time: 0.057 ms ``` I think this is a cheap way to prevent bad estimations. The storage overhead of adding an ndistinct field is trivial compared to the MCV list itself, and the O(1) arithmetic during planning adds no measurable overhead. I look forward to your feedback before drafting a patch. Best, Enrique. -
Re: Extended statistics improvement: multi-column MCV missing values
Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2026-05-18T22:13:39Z
Hi Enrique, On 5/18/26 19:09, Enrique Sánchez wrote: > > Postgres only uses multi-column MCVs when the value we are looking for > is in the list. If not, it falls back into individual independent > statistics to estimate selectivity. > However, a miss in a multi-column MCV list still yields valuable > information that it currently throws away: we know that the > combination's frequency is strictly bounded by the frequency of the > last (least common) item in that MCV list. LGTM. If the multicolumn MCV statistics exists and the clause combination is absent from the MCV-list, we can use the least frequent MCV item as an upper bound. BTW, this only applies to AND-clauses. > > 2. Estimate selectivity as Postgres does for single-column values not > in MCVs > ============================================================================= > While that significantly improves estimations, we could mirror what > Postgres already does for individual MCVs. Quote from the official > documentation: > > The approach is to use the fact that the value is not in the list, > combined with the knowledge of the frequencies for all of the MCVs: > > That is, add up all the frequencies for the MCVs and subtract them > from one, then divide by the number of other distinct values. > > To achieve this, we need to store an ndistinct estimation alongside > the MCVs that can be used for partial or entire column match. > > P(1, 1, 1) = (1 - sum(MCVs)) / (ndistinct(col_a, col_b, col_c) - > MCV_list_size) > > > ... > > I think this is a cheap way to prevent bad estimations. The storage > overhead of adding an ndistinct field is trivial compared to the MCV > list itself, and the O(1) arithmetic during planning adds no > measurable overhead. I look forward to your feedback before drafting a > patch. For this, the ndistinct extended statistics already exist. If both MCV and ndistinct statistics are present on the same column set, the formula is correct. There are already places in the code that compute ndistinct for columns without extended ndistinct statistics (see estimate_num_groups) - but it is worth thinking carefully about whether the added complexity is justified before going down that path. -- Best regards, Ilia Evdokimov, Tantor Labs LLC, https://tantorlabs.com/
-
Re: Extended statistics improvement: multi-column MCV missing values
Enrique Sánchez <enriqueesanchz@gmail.com> — 2026-05-24T18:34:52Z
Hi Ilia, > 1. Cap selectivity with the last MCV item's frequency I've attached a draft patch. It's split into 4 commits to make it easier to review. It adds the MCV cap for AND (equality, IN, ANY) clauses. Looking forward to your feedback. On 5/19/26 0:13, Ilia Evdokimov wrote: > Postgres only uses multi-column MCVs when the value we are looking for is > in the list. If not, it falls back into individual independent statistics > to estimate selectivity. > However, a miss in a multi-column MCV list still yields valuable > information that it currently throws away: we know that the combination's > frequency is strictly bounded by the frequency of the last (least common) > item in that MCV list. > > LGTM. If the multicolumn MCV statistics exists and the clause combination > is absent from the MCV-list, we can use the least frequent MCV item as an > upper bound. BTW, this only applies to AND-clauses. > Given that the inclusion-exclusion principle (P(A OR B) = P(A) + P(B) - P(A AND B)) is used to calculate OR paths, we could use the same cap to improve the overlap estimation (P(A AND B)). 2. Estimate selectivity as Postgres does for single-column values not in > MCVs > > ============================================================================= > While that significantly improves estimations, we could mirror what > Postgres already does for individual MCVs. Quote from the official > documentation: > > The approach is to use the fact that the value is not in the list, > combined with the knowledge of the frequencies for all of the MCVs: > > That is, add up all the frequencies for the MCVs and subtract them from > one, then divide by the number of other distinct values. > > To achieve this, we need to store an ndistinct estimation alongside the > MCVs that can be used for partial or entire column match. > > P(1, 1, 1) = (1 - sum(MCVs)) / (ndistinct(col_a, col_b, col_c) - > MCV_list_size) > ... > I think this is a cheap way to prevent bad estimations. The storage > overhead of adding an ndistinct field is trivial compared to the MCV list > itself, and the O(1) arithmetic during planning adds no measurable > overhead. I look forward to your feedback before drafting a patch. > > For this, the ndistinct extended statistics already exist. If both MCV and > ndistinct statistics are present on the same column set, the formula is > correct. There are already places in the code that compute ndistinct for > columns without extended ndistinct statistics (see estimate_num_groups) - > but it is worth thinking carefully about whether the added complexity is > justified before going down that path. > I think that the implementation would look similar to the attached patch. The only added complexity is getting the ndistinct estimation. There are 2 ways: - Rely on the extended ndistinct statistic if it exists - Calculate the ndistinct(col_a, col_b, col_c) statistic as part of the MCV. The storage cost is negligible compared to the MCV list and it keeps the MCV statistic complete, so it doesn't need to check if the ndistinct statistic exists. That would be a change on the MCV struct, meaning a change in the mcvlist->type. I can start working on a proposal for this second part. Let me know what you think. Best regards, Enrique.