OLAP Cardinality Injection

A research harness for measuring the performance impact of perfect cardinality information on query optimization. We patch DuckDB's C++ optimizer so it can inject true subplan cardinalities ("oracles") in place of its built-in cardinality estimator (CE), then run the Join Order Benchmark (JOB) — 113 queries over the IMDB dataset — under each injection mode.

Three injection modes isolate a different optimizer decision:

Mode	Join order uses	Build/probe side uses
ce	default CE	default CE (baseline)
join_only	oracle	default CE
build_only	default CE	oracle
oracle	oracle	oracle (full)

The oracle is built against optimizer-visible predicates only (base-table scans + pushdown filters). Execution-time filters (bloom / min-max runtime filters) are intentionally excluded — the oracle gives the optimizer exactly the information it asks for at planning time.

For how the true cardinalities are reconstructed from the optimizer's internal logs (and why it is harder than prepending SELECT COUNT(*)), see reconstruction.md.

---

Repository layout

olap_cardinalities/
├── README.md
├── reconstruction.md            # how cardinality reconstruction works
├── pyproject.toml / uv.lock     # Python environment (managed with uv)
├── notebooks/                   # the pipeline (see "Running the pipeline")
├── data/
│   ├── imdb/                    # IMDB CSVs — DOWNLOAD (not in repo)
│   ├── join-order-benchmark/    # JOB queries + schema.sql — git submodule
│   ├── imdb.duckdb              # generated by notebook 1.0 (NOT in repo, ~5 GB)
│   ├── scans/                   # raw optimizer CE logs — generated by 2.1
│   ├── scan_cardinalities/      # the ORACLES (*-oracle.tsv) — published
│   └── results/                 # experiment output + plots — published
└── duckdb-python/               # git submodule (DuckDB Python bindings)
    └── external/duckdb/         # nested submodule — DuckDB C++ source (patched)

Only the patched C++ files and the published data live in this repo. Everything else (the rest of DuckDB, the JOB queries, the IMDB CSVs) is pulled from upstream — see below.

---

What to clone and download

1. Clone this repo with submodules

git clone --recurse-submodules <this-repo-url>
cd olap_cardinalities
# if you already cloned without --recurse-submodules:
git submodule update --init --recursive

This pulls two external repositories referenced as submodules:

• Join Order Benchmark — data/join-order-benchmark/ https://github.com/gregrahn/join-order-benchmark (queries + schema.sql).
• DuckDB Python bindings — duckdb-python/ https://github.com/duckdb/duckdb-python, which in turn nests the DuckDB C++ source at duckdb-python/external/duckdb/ (https://github.com/duckdb/duckdb).

2. DuckDB version

The patched optimizer is built against a specific DuckDB commit. The published patches are only guaranteed to apply/compile against it:

• DuckDB C++ (duckdb-python/external/duckdb): commit 2e305aac80, i.e. git describe = v1.4.3-4452-g2e305aac80 (4452 commits past the v1.4.3 release tag — effectively a 1.4.4-dev build off main).
• duckdb-python (duckdb-python): commit 89ed9a1, git describe = v1.4.3-137-g89ed9a1.

git submodule update --init --recursive checks out exactly these commits.

3. IMDB data

The JOB schema uses the IMDB snapshot from May 2013. Download and extract the CSVs into data/imdb/:

mkdir -p data/imdb
curl -L http://event.cwi.nl/da/job/imdb.tgz | tar xz -C data/imdb

---

Building patched DuckDB

duckdb-python and its nested external/duckdb are git submodules pinned to the upstream commits above. The optimizer changes are not committed inside those submodules — they ship as a single diff, patches/duckdb-oracle.patch, applied on top of the pinned DuckDB commit:

git -C duckdb-python/external/duckdb apply ../../../patches/duckdb-oracle.patch
# verify it applied cleanly:
git -C duckdb-python/external/duckdb status --short

The patch touches the following files (everything else in DuckDB is upstream):

Added

• src/optimizer/oracle_manager.cpp
• src/include/duckdb/optimizer/oracle_manager.hpp

Modified

• src/optimizer/optimizer.cpp
• src/optimizer/build_probe_side_optimizer.cpp
• src/optimizer/join_order/cardinality_estimator.cpp (+ .hpp)
• src/optimizer/join_order/relation_manager.cpp
• src/optimizer/join_order/relation_statistics_helper.cpp (+ .hpp)
• src/optimizer/CMakeLists.txt (registers oracle_manager.cpp)
• src/planner/bind_context.cpp
• src/planner/table_filter.cpp

With the patch applied, build and install the bindings into the project's virtual environment (this project uses uv):

uv sync                       # create the venv from pyproject.toml / uv.lock
uv pip install -e ./duckdb-python   # builds the patched DuckDB from source (slow)

The patch must be applied before this build step, so the compiled extension includes the oracle logic.

Verify the patched extension is active by running notebook 2.1 on one query and confirming a data/scans/{qid}-scan.tsv file is produced.

---

Runtime control: environment flags

All oracle behavior is driven by environment variables read by the patched C++ (OracleManager). The notebooks set these via os.environ before each query; the authoritative semantics are:

Variable	Effect
USE_ORACLE=true	Full injection: oracle for both join order and build/probe side.
ORACLE_JOIN=true	Oracle for join-order selection only.
ORACLE_BUILD=true	Oracle for build/probe-side selection only. Implied by USE_ORACLE.
USE_SCAN_ORACLE=true	Inject oracle scan cardinalities (also satisfies "oracle enabled").
USE_LOGGER=true	Emit the CE log (scan/join subplan reconstruction). Used by 2.1.
ORACLE_DIR=<path>	Directory of per-query {qid}-oracle.tsv oracle files.
CURRENT_QUERY_ID=<qid>	The query being run (e.g. 18c). Selects which oracle file to load; oracle maps reload when this changes.
CE_LOG_PATH=<path>	Where the CE log is written when USE_LOGGER=true.

Notes:

• USE_ORACLE implicitly enables both ORACLE_JOIN and ORACLE_BUILD; the narrow flags exist to isolate a single optimizer stage (join_only / build_only conditions).
• Filter pushdown for logging/injection is enabled whenever either oracle or logging is on.

The DuckDB-side knobs used in the experiment notebook:

con.execute("PRAGMA threads=N")               # vary parallelism (1,2,4,6,8)
con.execute("PRAGMA enable_profiling='json'")  # per-query EXPLAIN ANALYZE profiles
con.execute("PRAGMA profile_output='...'")

The legacy single-file join-oracle loader (LoadJoinOracleOnce in oracle_manager.cpp) is only consulted when ORACLE_PATH is explicitly set, and is superseded by the per-query ORACLE_DIR mechanism. The current pipeline does not use it.

---

Running the pipeline

All steps are notebooks under notebooks/, loosely numbered by stage (1.x build · 2.x oracle generation · 3.x experiment · 4.x analysis). Run them in this order:

Step	Notebook	Produces
1	1.0-generate-duckdb-file.ipynb	Builds data/imdb.duckdb from the IMDB CSVs + JOB schema.sql. Run all cells.
2	2.1-scan-all-queries.ipynb	Runs every JOB query with the logger on → data/scans/{qid}-scan.tsv.
3	2.2-reconstruct-cardinalities.ipynb	Reconstructs join-order true cardinalities → data/scan_cardinalities/{qid}-oracle.tsv.
4	2.4-recover_bp_cards.ipynb	Adds build/probe-side cardinalities to the same oracle files.
5	3.1-experiment.ipynb	Runs all four conditions across thread counts → data/results/. Settings (threads, which conditions, run counts) are at the top of the notebook.
6	4.2-analyze-results.ipynb	Plots speedups / summary tables from data/results/. Template analysis.

The oracle files (data/scan_cardinalities/) and the experiment results (data/results/) are published in this repo, so to reproduce the analysis only you can skip straight to step 6. To re-run the experiment without regenerating oracles, start at step 5.

3.1 only runs queries that have a matching {qid}-oracle.tsv, so a partial oracle set still produces a valid (smaller) experiment.

---

Published data

Path	Contents
data/scan_cardinalities/*-oracle.tsv	The reconstructed oracles (true cardinalities per subplan). The expensive artifact — included so you need not regenerate.
data/results/raw_times*.csv, summary.csv, t{N}/raw_times.csv	Per-run and per-thread-count execution timings for all four conditions.
data/results/t{N}/explain-analyze-*/	Per-query EXPLAIN ANALYZE JSON profiles for each condition and thread count.
data/results/**/*.pdf	Speedup and time-difference plots produced by 4.2.

To keep the repo lean, only the bulkiest regenerable artifact is excluded (see .gitignore): the per-condition scan logs (logs_default/, t{N}/logs/, ~1.2 GB). The timing and profile analyses in 4.2 run from the published CSVs and EXPLAIN ANALYZE profiles; only the CE-estimation-quality cells need those logs regenerated via notebooks 2.1 / 3.1.

Oracle and result file formats are documented in reconstruction.md.

---

Reproducing from scratch

To rebuild everything without any published data, run the full pipeline (1.0 → 2.1 → 2.2 → 2.4 → 3.1 → 4.2) after downloading the IMDB CSVs and applying the patch. The published data/scan_cardinalities/ and data/results/*.csv let you skip ahead: start at 3.1 to re-run the experiment, or at 4.2 to reproduce the timing analysis only.