Start from a faithful port of clauselist_selectivity and the literal statistics Postgres computes. Let an LLM-driven evolutionary loop (openevolve driving a local claude -p with the Haiku model) rewrite the combining logic, and judge it only on data it never optimized against. Run 1 fell into 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 before execution | 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 makes 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.