Hierarchical taxonomies should match their subtree: resolve the hierarchy at write time

[MA2153]

Hierarchical taxonomies should match their subtree: resolve the hierarchy at write time

Type: Feature + migration — additive schema, one behaviour change on hierarchical taxonomies

What users expect

Picking a parent term should return everything filed under it. Selecting North America should match entries tagged USA, Mexico and Canada; selecting a top-level region in a 5-level tree should match everything beneath it. That is what a term means in a browse UI, and it is what WordPress does (category_name includes children).

EmDash matches exact slugs only. where: { region: "north-america" } returns entries tagged literally north-america and nothing else, so a parent term in a hierarchical taxonomy is usually an archive page showing zero results while hundreds of matching entries sit one level down. The hierarchy is already in the database (taxonomies.parent_id); nothing reads it at query time.

The workaround is to expand the subtree in the caller and pass every descendant slug. On a real hierarchy that does not fit: D1 caps a query at 100 bound parameters, and one slug is one parameter.

The constraint that makes this interesting

Since migration 051 a taxonomy-filtered listing seeks the denormalized pivot:

idx_content_taxonomies_pub (taxonomy_id, collection, deleted_at, published_at DESC, entry_id DESC)

taxonomy_id = ? lands on the index, walks it in sort order, and stops at LIMIT. A term archive costs ~11 rows read.

That index requires an equality on taxonomy_id. A subtree is a set of terms, so the natural implementations — expand to IN (…), or resolve descendants with a recursive CTE and feed the filter from it — turn the equality into a set match, and SQLite falls off the index onto the primary-key autoindex:

SEARCH ct USING INDEX sqlite_autoindex_content_taxonomies_1 (collection=?)
USE TEMP B-TREE FOR ORDER BY

That seeks on collection alone: it walks the collection's entire pivot partition and temp-sorts the matches. Every subtree design has to get past this, and it is why the obvious ones don't work.

Measurements

Schema-faithful repro: migration 051's pivot and indexes, taxonomies, ec_posts with its real indexes. 1,491-term region taxonomy, 5 levels (fan-out 7/4/4/3/3), 200,000 published entries filed at the leaves, page size 10 over-fetched by 1. No ANALYZE — fresh D1 has no sqlite_stat1 and the planner has to get this right without stats. All three strategies return identical result sets at every level.

subtree root	terms in subtree	entries beneath	expand to IN + GROUP BY	per-term top-N merge	ancestor rows (proposed)
L0 (top level)	213	28,656	28,656 rows / 37.5 ms	not expressible	11 rows / 0.0 ms
L1	53	7,164	7,164 rows / 22.5 ms	396 rows / 1.1 ms	11 rows / 0.0 ms
L2	13	1,791	1,791 rows / 16.3 ms	99 rows / 0.3 ms	11 rows / 0.0 ms
L3	4	597	597 rows / 13.0 ms	33 rows / 0.1 ms	11 rows / 0.0 ms
L4 (leaf)	1	199	199 rows / 8.0 ms	11 rows / 0.0 ms	11 rows / 0.0 ms

Two approaches ruled out by this:

Expanding the subtree into the filter costs rows proportional to everything beneath the term. Browsing a top-level region reads 28,656 rows to render 10. It also cannot express a top-level subtree at all — 213 terms is over D1's 100-parameter cap — so it needs chunking into several queries, each of which still scans.

A per-term top-N merge (k branches, each seeking its own term with its own LIMIT, merged and de-duplicated) keeps every branch on the index and is a big improvement lower down the tree. But it needs a bound parameter per term, so it dies at exactly the case users click most: the top-level term is not expressible as a single query. Its cost also grows linearly with subtree width, which is the wrong shape for a taxonomy that is meant to grow.

Resolving the hierarchy at write time makes a branch filter the identical single equality seek as a leaf filter: 11 rows, at every level, independent of subtree size and of how large the taxonomy gets.

The multi-term cliff already on main

Worth separating out, because it is a live regression independent of this feature. The multi-group path is taken by any filter resolving to more than one term, and the cliff is at two:

terms in filter	plan	time
1	SEARCH ct USING INDEX idx_content_taxonomies_pub (taxonomy_id=? AND collection=? AND deleted_at=?)	0.017 ms
2	SEARCH ct USING INDEX sqlite_autoindex_content_taxonomies_1 (collection=?)	3.243 ms
40	… (collection=?)	11.770 ms

where: { category: "news" }             // 11 rows walked
where: { category: ["news", "sport"] }  // whole partition walked — 190x the time

Control, to show the cost is the partition walk and not the matches: the same IN filter with 40 terms matching nothing still costs 5.045 ms against 0.010 ms for a no-match equality seek — 524×, for an empty result. Under this proposal a subtree filter is a single term and never takes that path, but an explicit ["a","b"] filter still does. The per-term merge above is the fix, and it is worth doing on its own merits.

(Every plan was re-derived with the instrumentation stripped out and diffed, so none of these are artifacts of the probe.)

Proposal

Resolve the hierarchy when content is written, not when it is read

When an entry is assigned a term in a hierarchical taxonomy, write a pivot row for that term and one for each of its ancestors, carrying a depth (0 = directly assigned). Rows are keyed (collection, entry_id, taxonomy_id), so an entry tagged at two points in the same branch collapses to one row per ancestor.

The read path then does not change at all. where: { region: "north-america" } resolves one term to one translation_group and runs the existing pivot query unmodified — same builder, same index, same early LIMIT, same non-atomic re-check against the ec_* row that #1962 established. There is no recursive CTE at read time, no expansion, no new query shape, and no new bound parameters.

Semantics, and the syntax that falls out of it

Because the closure is what the index sees, subtree matching becomes the default for hierarchical: true taxonomies, and the clean syntax gets the behaviour users expect:

// every entry in the subtree — the common case, no ceremony
where: { region: "north-america" }

// only entries tagged exactly this term — the rare case
where: { region: { exact: "north-america" } }

{ exact: … } takes the same string | string[] shapes as the current value and compiles to the existing filter plus depth = 0.

Flat taxonomies are completely unaffected — no ancestors, so the closure is depth-0 only and results are byte-identical. The behaviour change is scoped to taxonomies explicitly marked hierarchical, where today's exact-only matching is arguably the bug.

Counts come out exact, and free

A facet badge reading North America (0) next to a filter returning hundreds is the visible half of this. Because closure rows are de-duplicated per (entry, ancestor), a plain COUNT(*) GROUP BY taxonomy_id over the pivot is already the exact distinct-entry subtree count — verified against a true COUNT(DISTINCT entry_id) over the expanded subtree at 7,164 for an L1 term. fetchVisibleTermCounts needs no new query and no rollup pass; summing children in memory (which would double-count an entry tagged at two levels) is not needed.

What it costs

Stated plainly, because these are the reasons to argue with it:

• Storage. 5× pivot rows at depth 5 in the benchmark (200k → 1M), exactly the average ancestor-chain length. Only hierarchical taxonomies pay it: on a typical site categories are hierarchical and few per entry, tags are flat and many per entry, so the blended factor is well under 5×.
• Write amplification on publish. fix(loader): seek taxonomy-filtered listings via a denormalized pivot #1962's denormalized status/published_at columns must be re-stamped across an entry's closure rows, not just its direct ones — ~5× the re-stamp work on the publish path. (updated_at is deliberately not denormalized, so ordinary edits are unaffected.)
• Re-parenting a term rewrites the closure for every entry beneath it: moving an L2 term in the benchmark touched 1,791 assignments ≈ 5,373 rows, non-atomically on D1. It is a rare admin action, but it is a batched background rewrite, not an instant one, and results are transiently mixed while it runs.
• Backfill. A migration walking existing assignments up parent_id. 200k assignments → 1M rows in ~2s locally; on D1 it is chunked and forward-only.

Containing the blast radius

Two ways to store the closure, and I would take the second:

1. depth column on content_taxonomies. Cheapest storage. But every existing read of the pivot then needs depth = 0 or inherited terms leak into "the terms on this entry" — that is ~15 source files across handlers, repositories, term counts, folded hydration, seed and import, and anything missed fails open, showing wrong data.
2. A separate closure table holding all edges (depth 0..n) with the same denormalized columns and sort indexes. content_taxonomies is untouched, so every existing read is correct by construction and the only consumer of the new table is the subtree filter. Costs one extra copy of the direct rows; buys a zero-risk migration and a rollback that is DROP TABLE.

The write path maintains it the same way either way, and it stays advisory in exactly the sense #1962 established — the outer query re-checks the real predicates on the joined ec_* row, so a stale closure can under-fill a page but can never leak a deleted or wrong-status row.

Suggested split

1. Per-term merge for multi-term filters. Pure performance fix, no new API, no schema. Fixes where: { category: ["a","b"] } and stands alone.
2. Closure table + write-path maintenance + backfill migration. No behaviour change yet; the table is built and kept correct.
3. Read semantics: subtree by default on hierarchical taxonomies, { exact: … } opt-out, plus counts.
4. Admin: content-list term filter and facet counts follow the same rule.

Open questions

1. Is default-on the right call? It silently changes results for existing hierarchical archives, including every where: { category: term.slug } in this repo's templates and demos. I think that is the fix rather than the break, and flat taxonomies are untouched — but it wants an explicit decision and a changeset that calls it out. The alternative is a per-taxonomy opt-in flag, which I would rather avoid.
2. Closure table or depth column? I lean separate table for the risk containment; the column is strictly cheaper if you would rather audit the read sites once.
3. Re-parenting: acceptable as a chunked background rewrite, or does it need to block the admin action until consistent?
4. Depth cap. Parent chains are already validated to 100 ancestors. Worth lowering for closure sanity, or leave it?

Prior discussion

#1647 proposed a { subtree: … } operator resolved by a recursive CTE at read time, with #1648 as a draft PR. That predates #1962 by two weeks; measured against the pivot it now lands on the partition-scan plan above, and it cannot express a top-level subtree within D1's parameter cap. Happy to close both in favour of this if the direction is agreed.