Seedlabs

EquiDepth-2D: Balanced Two-Column Histogram Builder for Query Optimizers

A database component that organizes data into balanced buckets to help the system predict query costs more accurately.

A statistics component for database engines that tiles the joint frequency array of two correlated columns into at most p near-equal-weight rectangles (within 2.5x of optimal, near-linear build time), giving cost-based optimizers balanced 2D buckets for far better cardinality estimates on correlated predicates.

EngineeringOptimization and Packing Problems
Hybrid Graph-Based Memory and SchedulingDatabase query optimization (cardinality estimation and statistics collection)

Concept

Cost-based query optimizers estimate how many rows a predicate will match using per-column histograms; when two columns are correlated (latitude with longitude, price with date), multiplying two independent 1D estimates can be wrong by orders of magnitude and the optimizer picks a bad join order. EquiDepth-2D is a statistics-builder component that fixes this for chosen column pairs: it builds the joint frequency array (both columns binned, tuple count per cell — the same raw material engines already collect), then applies the new rectangle-tiling algorithm to cover that array with at most p rectangles whose maximum tuple count is within 2.5x of optimal. The output is a compact 2D histogram with near-equal-depth buckets: no bucket hoards the tuples, so per-bucket density is stable, and a range query over the column pair gets its selectivity from the handful of rectangles it intersects. It ships as an ANALYZE-time extension that serializes the rectangle list plus per-rectangle counts for the optimizer to consult on two-column predicates.

Why now

Paper [0] names histogram-based estimation of query sizes as a direct motivation and pins down why 2D histograms have been stuck: the 1D balanced-bucket problem is solved by dynamic programming, but the 2D version is NP-hard to approximate within 1.25 — and the paper supplies a near-linear time algorithm with a 2.5x guarantee. That is exactly the missing piece for practical 2D equidepth histograms: a build-time method whose worst-case bucket imbalance is bounded and whose runtime fits inside routine statistics-collection windows on large tables. The algorithm is proven; integrating it (binning, serialization, optimizer hooks) is standard database engineering, making this a contained upgrade rather than a research project.

Written by GLM · 12 Oct 2026

AI assessment

Backed by 1 paper93

A highly focused, technically grounded improvement to database cardinality estimation that solves a known NP-hard bottleneck with a proven approximation algorithm.

Evidence strength
5/5
The idea maps directly to the provided research paper's core result: a near-linear time algorithm with a 2.5x approximation guarantee for the exact problem of rectangle tiling for database histograms.
Market pull
4/5
Cardinality estimation is a fundamental pain point for all major RDBMS vendors, as poor estimates lead to catastrophic query plan choices.
Novelty & moat
5/5
The idea is entirely distinct from the listed catalog items, which focus on query rewriting, UI/UX, and schema drafting rather than core engine statistics.
Feasibility
4/5
The algorithm is already proven and the integration points (ANALYZE and optimizer hooks) are standard database engineering tasks.
Wedge clarity
5/5
The wedge is a specific, high-value component (2D histogram builder) that solves one precise problem: correlated predicate estimation.
Simplicity / focus
5/5
It is a single, sharp tool—a statistics builder—rather than an over-scoped platform or a full database rewrite.

Scored by Gemma 4 · 12 Oct 2026. Rated against a fixed rubric (evidence, market, novelty, feasibility, wedge, simplicity), relative to the closest ideas already in the catalog. A prior estimate to compare ideas before real-world signal arrives.

Persona discussion

AI personas trained on real people's expertise debate this idea as it evolves.

View the discussion →

Act on this idea

Ideas only matter if someone runs with them. Your message goes straight to the founder's inbox — nothing is stored on our servers.

Who benefits

  • Microsoftcompany

    SQL Server's cardinality estimator is known to misestimate correlated predicates; a build-time 2D equidepth histogram with a 2.5x balance bound targets that failure mode directly.

  • DuckDB Labscompany

    DuckDB's ANALYZE collects per-column statistics; balanced 2D rectangle histograms over correlated column pairs would sharpen range-join estimates in the analytical workloads DuckDB targets.

  • PostgreSQL Global Development Grouporganization

    PostgreSQL's CREATE STATISTICS captures correlations via MCV lists and functional dependencies but has no balanced 2D histogram; this module fills that gap for range queries on column pairs.

  • Oraclecompany

    Oracle's cost optimizer has relied on 1D height-balanced histograms for decades; extending balance to two correlated columns is a natural, contained upgrade path for its statistics layer.

Research it builds on

  1. On approximating rectangle tiling and packing
    Sanjeev Khanna, S. Muthukrishnan, Mike Paterson · 2026 · 106 citations
    All ideas from this paper →
Leave feedback
feasibility