Start from a faithful port of clauselist_selectivity and the literal statistics Postgres computes. Let an LLM-driven evolutionary loop (openevolve × local claude -p, haiku) rewrite the combining logic — and judge it only on data it never optimized against. Run 1 sprang the trap this harness was built to catch; run 2 re-runs the same search with the objective hardened against the diagnosed exploit.
Before a database runs your SQL it picks a strategy — which index, which join order, which algorithm. It can't try them all, so it predicts how many rows each step will match and takes the cheapest-looking plan. That prediction is cardinality estimation, and it decides everything downstream: a plan that's perfect for 10 rows is catastrophic for 100,000 — milliseconds versus minutes. The standard finding in the field (Leis et al.): estimation error, not the plan search, is the main reason databases pick bad plans.
Estimates come from small per-column statistics — most-common values with frequencies, plus histograms. One condition is easy: the stats say directly that ~1.5% of rows have city = 'BUFFALO'.
The hard part is combining conditions. Postgres mostly multiplies the fractions — which silently assumes the conditions are independent. Real values aren't: they co-occur (a city pins down its county) or they contradict (a city paired with the wrong county). Multiplication is wrong in opposite directions on those two — and, as the live example shows, per-column statistics cannot tell them apart. Postgres ships hand-written fixes for a few declared column pairs (extended statistics); everything else falls back to multiplication. This project evolves that combining logic.
--- seed +++ champion @@ -20,7 +20,64 @@ remaining = remove_clauses_on(remaining, a, b) - # Step 3: independence fallback for everything left. + # Step 3: independence fallback with contradiction detection for remaining clauses. + # For equality clause pairs sharing extended stats, check if combination exists in MCV. + # If absent but independence predicts non-zero, dampen by unobserved mass ratio. + processed = set() + eq_clauses = {c.col: c for c in remaining if c.op == "="} + for c in remaining: - sel *= marginal_selectivity(c, S) + if c.col in processed: + continue + s_c = marginal_selectivity(c, S) + sel *= s_c + processed.add(c.col) + + # For equality clauses, look for correlated columns in extended stats. + if c.op == "=" and s_c > 0.0: + for other in remaining: + if other.col in processed or other.col == c.col: + continue + for g in S.groups(): + if c.col in g.cols and other.col in g.cols and g.mcv: + s_other = marginal_selectivity(other, S) + if s_other <= 0.0: + continue + + litmap = {c.col: c.lit} + if other.op == "=": + litmap[other.col] = other.lit + + mcv_sel = 0.0 + base_matched = 0.0 + total_freq = 0.0 + for item in g.mcv: + total_freq += item["frequency"] + vals = dict(zip(g.cols, item["values"])) + # For equality: exact match; for range: check bounds. + if other.op == "=": + if all(vals.get(col) == lit and vals.get(col) is not None + for col, lit in litmap.items()): + mcv_sel += item["frequency"] + base_matched += item["base_frequency"] + else: + # Range clause: check if c's literal matches and other's value + # falls in the range. This is a coarse check; we use MCV to + # detect if the pair co-occurs at all. + if vals.get(c.col) == c.lit and vals.get(c.col) is not None: + mcv_sel += item["frequency"] + base_matched += item["base_frequency"] + + # If combination completely absent from MCV but independence predicts it, + # apply dampening based on unobserved mass ratio. + if total_freq > 0.0 and mcv_sel == 0.0 and base_matched > 0.0: + # Combination never observed in training; dampen by unobserved ratio. + unobs_ratio = 1.0 - (base_matched / total_freq) + sel *= s_other * max(0.01, unobs_ratio) + else: + sel *= s_other + + if other.op == "=": + processed.add(other.col) + break return clamp(sel, 1.0 / S.row_count, 1.0)
| run 1 | run 2 | ||
|---|---|---|---|
| G1 | marginal fidelity vs EXPLAIN dmv 61/61 · census 61/61 · covertype 59/60 within 1.5x | PASS | |
| G2 | seed fidelity vs EXPLAIN, multi-clause 40/40 · 40/40 · 39/40 within 2x (after importing mcv.c's leftover-mass cap) | PASS | |
| G3 | planted cheats rejected by lint hardcoded row counts, column-name dispatch, banned imports — all caught pre-exec | PASS | |
| G4 | loop smoke (mock + live claude) 40/40 live iterations; invalid children zeroed by guards | PASS | |
| G5 | champion beats seed on unseen queries {held-out} run 1: 11.34→41.29 · run 2: 11.34→7.85 | FAIL | PASS |
| G6 | improvement holds on never-seen tables {held-out} | PASS | PASS |
| G7 | no phantom win on the shuffled control run 1: 61% swing · run 2: 24301% | FAIL | FAIL |
For some column pairs, Postgres keeps a list of the ~500 most common value combinations it saw while sampling the table. The champion added exactly one rule on top of Postgres:
That single rule changed the answers on 190 of 300 trap queries and 103 of 526 correlated-pair queries on the vehicle table (plus a small accidental side-effect on 21 census queries). Every other query — including everything involving ranges — gets the exact same answer as stock Postgres.
Does it make sense? Mostly, yes. For pairs with only a few dozen possible combinations, a 500-item list effectively contains every combination that exists — so "not in the list" really does mean "doesn't exist." Postgres never dares to make that leap (it lowers its guess, but never near zero); the champion does, and that one leap is where all its gains come from. The flaw: for pairs with thousands of combinations (city × county), "not in the list" usually just means "uncommon," and the champion wrongly flattens those to 1 row. On the unseen test data the wins outweighed the losses (−31% and −33%). But on the shuffled control table — where nothing is correlated, so "not in the list" means nothing at all — the same rule collapsed, and that is exactly why the control gate stamped run 2 FAIL.