Port the metatrie tier (cltj_index_metatrie.hpp): share the root level across ordering pairs #102

Motivation

#66 item 1 landed the cltj_index_spo_basic tier: six full LOUDS tries, 47.6 MiB against the array index's 136.6 MiB at LDBC SF0.1 (2.87× smaller). The reference's more compact variant, cltj_index_metatrie, is still unported and is the remaining checkbox on that item.

Splitting it out of #66 because it is a self-contained structural change with its own build side, iterator and measurement, while #66's other two items (a no-fallback pure-CLTJ execution path, and the RDF/BGP benchmark) are unrelated work.

What the metatrie is

The six orderings come in pairs that agree on their first symbol: SPO/SOP both start with the subject, POS/PSO with the predicate, OSP/OPS with the object. The basic tier stores that first level twice per pair. The metatrie stores it once:

• The even trie of each pair keeps its full root level; the odd one stores only levels 1–2 (end_level = 3 - (i & 0x1) in the constructor).
• The shared roots become bitvectors with rank + succ support: m_subjects for the SPO/SOP pair, m_objects for OSP/OPS.
• Predicates need neither: the constructor asserts their root symbols are contiguous (syms_root[j] == j+1) and hard-errors otherwise, so POS/PSO index arithmetically.
• m_gaps[3] records each pair's root width, which is what the navigation offsets by.

Reference: cltj/include/index/cltj_index_metatrie.hpp (240 lines) plus its iterator cltj/include/query/ltj_iterator_metatrie.hpp. A dynamic variant exists too (cltj_index_metatrie_dyn.hpp) and is out of scope here.

Scope

1. TripleRepr::Metatrie alongside the existing array and compact representations, behind FROGQL_LTJ_COMPACT=metatrie (or its own flag) — the enum-dispatched LtjIterator already makes a third representation a matter of one more variant, which is what the basic tier's port established.
2. The two shared-root bitvectors with rank + succ. compact.rs already carries a topology bitvector with sampled select-0, so the primitives exist; rank-1 and succ-1 over a sparse root vector is the new piece.
3. A metatrie iterator: the odd trie of a pair has to resolve its first level through the shared bitvector rather than its own topology.
4. Check the predicate-contiguity assumption against our data. The reference exits on violation. Our label ids are assigned in edge order by TripleIndex, so they may well be contiguous — but that has to be verified rather than assumed, and if it does not hold the port needs a fallback rather than an abort.

The property-graph divergence carries over

compact.rs documents it: RDF triples have no edge identity, ours do, and parallel edges collapse into one trie leaf. The basic tier keeps an SPO-ordered eid side table (leaf_offsets / leaf_eids) consulted at the base case so ISO bag multiplicity (#71) survives. The metatrie needs the same table, and the differential suite has to cover parallel edges explicitly.

What to expect, honestly

The saving is one root level out of three, on three of the six tries. That is a fraction of 47.6 MiB, not another 2.87×. And the basic tier already costs 1.4–2.1× on IC latency against the arrays (IC11 excepted, where it is 1.5× faster); a metatrie adds an indirection to the first level of half the tries, so it will not be faster. The question this answers is how much further the space goes and what that costs — so report both and do not bury the latency.

Verification

• Differential suite in the shape of tests/compact_ltj_test.rs (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 the new flag.
• Size and build stats through the existing ltj_index_stats bin, extended with the third representation.
• LDBC IC medians per representation on bench/data/ldbc-sf0.1.gdb.

Part of #66 (its remaining item 1 checkbox). Related: #101 (adaptive VEO).