SQLite's join Bloom filter waits for ANALYZE
Since version 3.38, SQLite can put a Bloom filter in front of the inner table of a join. If a fact table's row points at a dimension row that the WHERE clause throws away, the filter skips the B-tree lookup. I timed a plain star join with the filter on and off. On a fresh database it was never used: the plan was the same either way, at every size I tried. After one ANALYZE, every query got it, and the join ran 4.7 to 27 times faster when the filter kept 1% or less of the dimension table. ANALYZE on just one of the two tables didn't trigger it, and neither did PRAGMA optimize.
The setup
Two tables: fact with 2 million rows, and dim with 1,000 to 1,000,000 rows. Both are keyed on INTEGER PRIMARY KEY, and there are no other indexes. Each fact row points at a random dimension row. The query:
SELECT count(*), sum(f.v)
FROM fact f JOIN dim d ON f.d = d.id
WHERE d.cat < ?Here cat is uniform over 0 to 9,999, so the cutoff sets the share of dimension rows that survive: 0.1%, 1%, 10%, 50% or 90%. The planner scans fact and looks up dim by rowid for each row. With the filter, the plan gets an extra line, BLOOM FILTER ON d (id=?), between the two.
To get a baseline I turned the optimization off without rebuilding SQLite. sqlite3_test_control(SQLITE_TESTCTRL_OPTIMIZATIONS, db, mask) masks the planner's BloomFilter and BloomPulldown bits on one connection. I called it through ctypes on the system library, SQLite 3.46.1. Each case ran from the page cache: one warm-up, then seven timed runs. Both settings returned the same row counts in every case.
Results
Seconds per query after ANALYZE, filter on and off, as the third-fastest of seven runs:
| dim rows | kept | filter on | filter off | speedup |
|---|---|---|---|---|
| 1,000 | 0.1% | 0.039 | 0.190 | 4.9× |
| 1,000 | 10% | 0.060 | 0.196 | 3.3× |
| 1,000 | 90% | 0.213 | 0.226 | 1.1× |
| 10,000 | 0.1% | 0.038 | 0.279 | 7.4× |
| 10,000 | 10% | 0.072 | 0.290 | 4.0× |
| 10,000 | 50% | 0.199 | 0.312 | 1.6× |
| 100,000 | 0.1% | 0.046 | 0.646 | 14× |
| 100,000 | 1% | 0.056 | 0.637 | 11× |
| 100,000 | 10% | 0.118 | 0.661 | 5.6× |
| 1,000,000 | 0.1% | 0.059 | 1.569 | 27× |
| 1,000,000 | 1% | 0.072 | 1.563 | 22× |
| 1,000,000 | 10% | 0.226 | 1.669 | 7.4× |
| 1,000,000 | 50% | 0.942 | 1.514 | 1.6× |
| 1,000,000 | 90% | 1.430 | 1.206 | 0.8× |
The bigger the dimension table, the more a skipped lookup is worth. Without the filter, a probe into a 1,000-row table hits pages that are already hot, and the whole join takes 0.19 s. A probe into a million-row table walks a deeper tree over pages scattered across memory, and the join takes 1.5 s. With the filter and a selective WHERE, both run in about 0.04 to 0.06 s, because almost no probe reaches the tree. What's left is the scan of fact.
When most rows survive, it is close to a wash. At 90% kept, the filter cost or saved about 10% at most sizes. At a million dimension rows it came out between 0.8× and 1.1× across three separate sweeps, so I'd call that break-even, not a measured slowdown. The planner can't know in advance how much its filter will reject, and here it never chose to drop it.
Which statistics it needs
I ran each database through a few ways of getting statistics, checked the plan, and timed it again:
| before the query | Bloom filter in plan? |
|---|---|
| nothing | no |
ANALYZE | yes, every case |
ANALYZE dim | no |
ANALYZE fact | no |
run the query, then PRAGMA optimize | no |
PRAGMA optimize=0x10002 | no |
That held for every size and cutoff I tried in this round (10,000 and 1,000,000 dimension rows, 1%, 50% and 90% kept). With no statistics, or only half of them, the plan was a plain scan and probe, and the timings with the filter on and off matched to within noise. PRAGMA optimize is the call the SQLite docs suggest running on a schedule. On these tables it didn't add whatever the planner wanted. My guess is that's because the only index is the rowid, so it saw nothing worth analyzing, but I didn't dig into its rules.
What I'd do
If you have a reporting-style SQLite database, with a big table joined to smaller ones that you filter, run a full ANALYZE once it has data and again after big loads. Then check EXPLAIN QUERY PLAN for the BLOOM FILTER ON line. Here that one statement turned a 1.6 s query into 0.07 s. If the plan doesn't show the filter, the optimization isn't happening, however new your SQLite is.
Method: SQLite 3.46.1 (Debian build) driven from Python 3.14 via ctypes, in a Linux aarch64 container with 10 cores, three cases at a time. Each case built its own fresh database file with journaling off. The table shows the last of three sweeps. The first sweep ran nine cases at a time and was visibly noisier at a million rows, which is where my early "0.65×" came from before I reran it. This is one synthetic schema with uniform keys and a single join. Skewed keys, joins over several dimension tables, or a database bigger than memory could all come out differently.