Implement compact CLTJ (no try-switching), benchmark vs the array LTJ, add the paper's RDF benchmark

[matiastoro]

Motivation

The current join engine is described as LTJ but is a simplified array implementation, not the compact CLTJ from the paper (Arroyuelo et al., VLDBJ 2025; C++ reference in cltj/). Implement the real compact structure, benchmark it head-to-head against the array version, and reproduce the paper's RDF benchmark.

Current state (feasibility)

• TripleIndex (src/runtime/ltj/triple_index.rs) stores orderings: [Vec<IndexEntry>; 6] — six fully-materialized sorted arrays of (u32, u32, u32, u32) tuples (~172 MiB at SF0.1).
• CLTJ in the paper is not a wavelet tree: cltj/include/trie/cltj_compact_trie.hpp is a LOUDS-style compact trie — a topology bit_vector (unary child-count encoding, one 0 per node) with succ0/select0 support, plus a bit-compressed int_vector of symbols. Navigation is child(it, n) = select0(it + gap + n), children(i) = succ0(i+1) − i; the leapfrog seek is a binary search over the symbol sequence within a node's child block (binary_search_seek).
• The paper's index still keeps six orderings (SPO/SOP/POS/PSO/OSP/OPS), as compact tries, in two variants:
  • cltj_index_spo_basic — six full compact tries;
  • cltj_index_metatrie — the more compact variant: each ordering pair shares its root level (subject/object bitvectors with rank/succ; predicates are contiguous), so odd tries store only levels 1–2.
• So the compaction win over our arrays is "6 sorted tuple-arrays → 6 LOUDS tries (or root-shared metatries) with bit-packed symbols", not "6 arrays → 1 wavelet tree".
• Try-switching: run_join / run_concat_pattern (src/runtime/engine.rs) attempt LTJ and fall back to pairwise hash-join for non-decomposable patterns (undirected edges, unions, repetitions). This item asks for a pure CLTJ path (no fallback) to measure CLTJ in isolation.

Scope

1. Compact CLTJ index: LOUDS compact tries (Rust rank/select bitvector + bit-packed symbol sequence). Two tiers: port cltj_index_spo_basic first (six full tries, direct analog of the array index, easiest to differential-test), then optionally the metatrie root-sharing.
2. A no-fallback CLTJ execution path for measurement.
3. Add the CLTJ paper's RDF / BGP benchmark (e.g. Wikidata triple-pattern queries, files in cltj/Queries/) — a different workload from the current LDBC property-graph harness (bench/cross-system/). Compare against the cltj/ C++ reference and the array LTJ.

Large. The succinct data structure is a substantial implementation effort; the RDF benchmark is a new bench workload.

[matiastoro]

Scope item 1 landed in 3b7ce66: compact CLTJ index (cltj_index_spo_basic tier) behind GQLITE_LTJ_COMPACT=1.

What it is. A port of the reference's LOUDS compact trie (cltj_compact_trie.hpp): per ordering, a topology bitvector (unary child counts, sampled select-0 + succ-0) plus a bit-packed symbol sequence; navigation via children(it) = succ0(it+1) − it, nodeselect(p) = select0(p+2), leapfrog seek = binary search inside a child block. The iterator (CompactLtjIterator) is a stateful handle-stack port of ltj_iterator_basic.hpp; both representations drive the unchanged LtjAlgorithm through an LtjIterator enum, so the whole optimizer/runtime stack (pins, filters, anydir mirror, VEO) works identically on either.

Property-graph divergence (documented in src/runtime/ltj/compact.rs): RDF triples have no edge identity; ours do, and parallel edges collapse into one trie leaf. The index carries an SPO-ordered eid side table (leaf_offsets/leaf_eids) consulted at the base case, so ISO bag multiplicity (#71) is preserved exactly.

Numbers on LDBC SF0.1 (1.49 M triples, lazy backend, 15 params × 3 iters):

	array	compact	ratio
index heap	136.6 MiB	47.6 MiB	2.87× smaller
build	0.92 s	1.13 s	1.2× slower
IC2 median	18.7 ms	26.1 ms	1.4×
IC5	191.4 ms	372.5 ms	1.9×
IC6	171.2 ms	360.4 ms	2.1×
IC8	45.5 ms	72.0 ms	1.6×
IC9	1829 ms	2570 ms	1.4×
IC11	1.70 ms	1.13 ms	0.66× — compact faster

Reproduce with cargo run --release --bin ltj_index_stats bench/data/ldbc-sf0.1.gdb and GQLITE_LTJ_COMPACT=1 ldbc_bench ….

Correctness: tests/compact_ltj_test.rs differential suite (20 tests: chains, comma-joins, reverse/undirected/any-direction, parallel-edge multiplicity, self-loops, value pins, label disjunction, fallback shapes) plus the full cargo test sweep under GQLITE_LTJ_COMPACT=1 — all green.

Remaining in this issue:

• metatrie tier (cltj_index_metatrie: root-sharing across ordering pairs → odd tries store only levels 1–2)
• no-fallback pure-CLTJ execution path for isolation measurements (item 2)
• RDF/BGP Wikidata benchmark vs the cltj/ C++ reference (item 3; query files already in cltj/Queries/)