-
Type:
Improvement
-
Resolution: Unresolved
-
Priority:
Major - P3
-
None
-
Affects Version/s: None
-
Component/s: None
-
Storage Engines - Transactions
-
21.679
-
None
-
None
Fast truncate today marks only leaf refs WT_REF_DELETED. A range truncate walks the tree, reads in every internal page in the range, and marks each on-disk leaf ref one at a time. This ticket proposes marking a fully-contained internal ref deleted instead, pruning the whole subtree in one operation.
1. Current behaviour
- _tree_walk_internal offers every on-disk ref to _wti_delete_page before descending (src/btree/bt_walk.c).
- __wti_delete_page rejects internal refs with a single check: addr.type != WT_ADDR_LEAF_NO. Everything else - visibility gates, WT_PAGE_DELETED allocation, transaction tracking, the state set - is type-agnostic.
- Consequence: cost is O(leaves) in page_del allocations, transaction operations and parent dirtying, plus reads of all internal pages under the range.
2. Design
Three properties make this work:
- The walk hook exists. The tree walk already offers internal refs to fast delete before descending, and already skips descending on success. The entry point is relaxing the leaf-only address check in __wti_delete_page.
- Range containment needs no new plumbing. The stop cursor's page is pinned in memory, every ancestor of an in-memory page is in memory, and fast delete only acts on on-disk refs. Any on-disk internal ref offered during a truncate walk is therefore wholly inside the truncate range. Assert this in diagnostic builds.
- Transactions are handled by lazy page_del propagation. Give WT_PAGE_DELETED an atomic refcount. When a deleted internal page must be read before the delete is globally visible, build the page normally, mark each child ref WT_REF_DELETED with a shared reference to the parent's page_del, and mark the page dirty and instantiated. From there down, everything reduces to the existing leaf machinery, recursively and lazily.
Transaction resolution under propagation:
- Commit is unchanged: all children observe the shared committed flag.
- Rollback before any read is unchanged: only the top ref flips back to WT_REF_DISK.
- Rollback after propagation walks the resident subtree and un-deletes children sharing the struct. The subtree is guaranteed resident because eviction returns EBUSY for pages with unresolved deleted children.
- The transaction operation tracks only the top ref; propagation never creates new operations.
3. Hard problems
3.1 Descendant block reclamation (local block manager). Freeing an internal page's block does not free the blocks below it. Fix: deferred depth-first subtree free, drained at checkpoint.
- When parent reconciliation drops a globally-visible deleted internal child, enqueue its address on a per-btree pending list instead of calling __wt_ref_block_free.
- Drain the list during each tree checkpoint, before the block manager finalizes extent lists: read raw internal page images only, walk their address cells, recurse into internal children, and free every descendant address depth-first, including overflow keys and nested deleted-address cells. Natural home is the checkpoint cleanup infrastructure.
- Crash safety: the reference drop and all descendant frees land in the same durable checkpoint. A crash before that checkpoint recovers to one that still references the subtree, so the lost in-memory queue drops nothing.
- I/O cost is small: only internal pages are read (roughly one per hundred leaves); leaf addresses come from parent cells.
- Disaggregated storage needs no reclamation work - page-log garbage collection reclaims unreferenced pages.
3.2 On-disk format. A new cell type WT_CELL_ADDR_DEL_INT is required: WT_CELL_ADDR_DEL is the only post-unpack source of a child's leaf/internal nature and is hard-mapped to leaf semantics in address copy, ref-flag setup, split and compact. The fast-truncate payload packing is already type-agnostic. The new cell must be compatibility-gated and never written unless enabled.
3.3 Interaction audit surface. RTS handles an unstable internal delete by reading the page, triggering propagation and then existing per-leaf processing. Internal fast-delete must be rejected for prepared transactions, matching the existing prepared-aggregate rejection. Verify, salvage, dump, compact, prefetch and the disaggregated delta path need support for the new cell type. Checkpoint obsolete cleanup can remain leaf-only initially.
4. Payoff
The walk already avoids reading leaf pages. The win is skipping reads of internal pages below the subtree roots, plus an O(leaves) to O(subtrees) reduction in page_del allocations, transaction operations, parent dirty bytes and downstream obsolete-cleanup work. Material for wide truncates on trees of three or more levels; no change for two-level trees.
5. Risk
Fast truncate plus instantiation plus prepared handling is historically the buggiest corner of the btree. The rollback-after-propagation walk makes the eviction-EBUSY invariant load-bearing and it must be asserted. De-risking shape: a first PR with zero behaviour change (refcount refactor, new cell type, read-side mapping, verify/dump support, statistics), feature default-off behind config.