Problem

PR #415 changes predicate-index deletion to use each deleted entry's metadata to locate and update only the relevant buckets.

Predicate indexes use the following nested structure:

HashMap<MetadataValue, HashSet<StoreKeyId>>

Under the proposed implementation, when a store entry is deleted, its StoreKeyId is removed from the corresponding inner set, while the MetadataValue -> empty HashSet bucket is deliberately retained. This avoids adding unsafe concurrent cleanup to the deletion hot path, but it can retain substantial memory for high-cardinality predicate indexes.

Worst-Case Impact

Consider an indexed metadata field containing 10,000 unique values, each referenced by one store entry. After deleting every entry, the index retains:

• 10,000 MetadataValue keys
• 10,000 empty papaya::HashSet<StoreKeyId> instances
• each set's backing table and sharded counter
• the outer Papaya table

On an arm64 machine with 10 logical CPUs, the estimated retained-memory lower bound is approximately 30.3 MiB:

This excludes table headers, metadata string/byte allocations, allocator bookkeeping, the outer table, and deferred reclamation state.

Papaya creates a cache-padded counter shard per logical CPU, rounded to the next power of two. Consequently, the retained memory per empty bucket increases with the machine's CPU count.

Correctness Constraint

A naive cleanup is unsafe:

store_key_ids.remove(store_key_id);

if store_key_ids.is_empty() {
    buckets.remove(metadata_value);
}

A concurrent insertion could obtain the existing set before the outer bucket is removed, insert into the now-detached set, and lose the index update.

Any cleanup implementation must coordinate insertion and deletion so that a bucket cannot be removed while another operation can still mutate it without detecting and retrying.

Investigation

Evaluate approaches such as:

1. Concurrent bucket removal with identity checks and insertion retries.
2. Periodic compaction or index rebuilding when the empty-bucket ratio exceeds a threshold.
3. Deferred cleanup under exclusive access to the predicate index.
4. A different bucket representation with cheaper empty-state overhead.

The investigation should measure:

• retained memory at increasing cardinalities
• deletion and insertion latency
• concurrent delete/insert behavior for the same metadata value
• cleanup or rebuild cost
• low-cardinality and high-cardinality workloads
• sensitivity to logical CPU count

Acceptance Criteria

• Empty predicate buckets can be reclaimed without losing concurrent index updates.
• Concurrent insertion and deletion tests cover the same metadata value.
• Memory benchmarks quantify retained and reclaimed memory at representative cardinalities.
• The selected strategy does not materially regress normal predicate ingestion, deletion, or lookup performance.
• Snapshot serialization and restoration remain behaviorally equivalent.