cardinal

DuckDB picks a join order from estimates of how many rows each join produces. Those estimates assume columns are independent and every join key matches as many rows as any other, so on real data they can be off by orders of magnitude, and DuckDB picks slow plans.

cardinal is a DuckDB extension that learns Bayesian networks from your tables, and gives DuckDB their estimates instead. It needs no configuration: load it, and queries are planned with better numbers. Results never change, only plans. On the STATS-CEB benchmark, total runtime drops from 118 s to 70 s.

Quick start

Cardinal is a DuckDB community extension, for DuckDB v2.0.0. Install and load it from any DuckDB client:

INSTALL cardinal FROM community;
LOAD cardinal;

Then query as usual. With a database file, e.g. duckdb my.duckdb:

CREATE TABLE a AS SELECT range AS id, range % 10 AS x FROM range(1000);
CREATE TABLE b AS SELECT range % 1000 AS a_id, range % 7 AS y FROM range(10000);
SELECT count(*) FROM a, b WHERE a.id = b.a_id AND a.x = 3 AND b.y = 2;

The join's first run fits a model per table. They show up in cardinal_models():

SELECT * FROM cardinal_models();

┌─────────────┬────────────┬───────────┬──────────────────┐
│ schema_name │ table_name │ row_count │     columns      │
├─────────────┼────────────┼───────────┼──────────────────┤
│ main        │ a          │      1000 │ ['F(b.a_id)', x] │
│ main        │ b          │     10000 │ [a_id, y]        │
└─────────────┴────────────┴───────────┴──────────────────┘

Models are saved in ~/.duckdb/extension_data/cardinal/, never in your database, and refitted when a table's row count changes by more than 10%, or when it is rewritten or altered. A query that needs a model waits for its fit: milliseconds for small tables, about a second for large ones.

Example

STATS-CEB's query 107 counts the comments, votes and badges of users, with filters on each:

SELECT count(*) FROM comments AS c, votes AS v, badges AS b, users AS u
WHERE u.Id = b.UserId AND u.Id = c.UserId AND u.Id = v.UserId
  AND c.Score = 1 AND c.CreationDate >= '2010-08-27 14:12:07'::TIMESTAMP
  AND v.VoteTypeId = 5
  AND v.CreationDate BETWEEN '2010-07-19'::TIMESTAMP AND '2014-09-13'::TIMESTAMP
  AND b.Date <= '2014-08-19 10:32:13'::TIMESTAMP AND u.Reputation >= 1;

	DuckDB alone	With cardinal
Estimated result	1,865 rows	28 million rows
True result	537 million rows	537 million rows
Estimate error	288,000× too low	19× too low
Planning time	1.0 ms	1.1 ms
Total time	12.9 s	0.45 s

Cardinal's estimate is still low, but close enough for DuckDB to pick a plan 29 times faster.

To compare on your own queries, turn cardinal off and on for the connection:

SET cardinal_estimator = 'off';
SET cardinal_estimator = 'on';

How the plans differ

DuckDB runs each join as a hash join: it stores one input, the build side, in a hash table, and streams the other input through it. It builds on the side it thinks is smaller. Each join shows its estimated and true rows:

DuckDB alone                          estimated          true
⋈ u.Id = v.UserId                         1,865   537,352,263
├── users                                40,325        40,325
└── build: ⋈ v.UserId = c.UserId          1,711   537,352,263
    ├── votes                            25,236        33,690
    └── build: ⋈ b.UserId = c.UserId      2,508     3,203,614
        ├── badges                       15,970        77,535
        └── build: comments               5,811        24,733

With cardinal                         estimated          true
⋈ v.UserId = u.Id                    28,146,412   537,352,263
├── ⋈ v.UserId = c.UserId               610,081     2,087,379
│   ├── votes                            46,598        33,690
│   └── build: comments                  44,187        24,733
└── build: ⋈ b.UserId = u.Id            155,707        77,535
    ├── badges                           76,106        77,535
    └── build: users                      6,905        40,325

Alone, DuckDB thinks joining comments, badges and votes gives 1,711 rows, fewer than the 40,325 users. So it builds the last hash table on that join, which stores 537 million rows. With cardinal, DuckDB sees that this join explodes. It joins votes with comments (2 million rows) and badges with users (78,000 rows), and builds on the smaller one. The last join then streams its 537 million rows into count(*) and stores none of them.

Why DuckDB's estimate is off

DuckDB estimates with almost no statistics:

• x = 'a' keeps the rows divided by the distinct values of x.
• Any other filter keeps 20% of the rows.
• A join gives the product of its inputs, divided by the distinct join keys.

The join rule assumes every key matches as many rows as any other. Here, an average user has 0.6 matching comments, 0.8 votes and 1.9 badges, so the 40,325 users would give about 40,000 rows. But active users comment, vote and earn badges at once, and their counts multiply. User 805 alone gives 1,845 × 482 × 294 = 261 million rows. Ten users give 97% of the result.

Why cardinal's estimate is closer

Cardinal fits a Bayesian network per table. It learns how the columns that queries filter on correlate, instead of treating each filter alone. Following BayesCard, each table also gets fanout columns: for each user, the count of its comments, votes and badges. The network learns these counts together, so it knows that a user with many comments also has many votes. A join's size is then the sum, over the users that pass the filters, of comments × votes × badges.

Benchmarks

The same queries, with DuckDB v2.0.0 alone and with cardinal, on five standard benchmarks:

Benchmark	Queries	Total time	Faster / same / slower queries	Median estimate error
STATS-CEB	146	118 s → 70 s	38 / 107 / 1	23× → 1.8×
JOB	113	4.0 s → 3.5 s	32 / 64 / 17	19× → 2.2×
JOB-light	70	5.3 s → 5.1 s	11 / 57 / 2	5.3× → 1.5×
DSB, scale factor 10	219	2.8 s → 3.2 s	0 / 196 / 23	4.1× → 2.0×
TPC-H, scale factor 10	22	1.4 s → 1.4 s	1 / 20 / 1	1.3× → 1.0×

• Total time: the whole workload, each query's median over several runs. Planning time included.
• Faster / same / slower: a query is faster or slower when its time changes by more than 10% and 10 ms, the same otherwise.
• Median estimate error: how far off the row counts DuckDB plans with are from the true ones, as a ratio, over every join DuckDB considers. Half the estimates are closer than this.

Estimates improve everywhere. Time follows where join order matters: STATS-CEB's slowest queries count billions of rows, and run twice as fast. DSB's queries take 10 ms each at this scale: its better plans make no difference, and small physical changes cost a few milliseconds. TPC-H, uniform data DuckDB already estimates well, is a check that cardinal does no harm.

Measured on an Apple M5 Pro. How, and more: research/.

Limits

• Only DuckDB tables: queries that read Parquet or CSV files, or attached PostgreSQL tables, are planned by DuckDB alone.
• Joins in a cycle, joins on several columns at once, and conditions such as a.x < b.y are left to DuckDB's own estimates.
• Cardinal relies on DuckDB internals, so each DuckDB release needs a new build of it.

How it works, settings, opting in per connection, and fitting ahead of time: docs/extension.md.

Development

Building needs what DuckDB's build needs: Git, CMake and a C++ compiler. It compiles DuckDB v2.0.0 itself: about 15 minutes on an Apple M5 Pro.

git clone https://github.com/MaxHalford/cardinal
cd cardinal
git submodule update --init duckdb extension-ci-tools
make release
./build/release/test/unittest "test/*"

build/release/duckdb is a DuckDB CLI with cardinal built in.

Porting to a new DuckDB release: docs/upgrading.md. The evaluation (benchmarks, accuracy, plan quality, runtime) lives in research/.

License

MIT.