Cardinality-aware VEO: order LTJ variables by real index sizes; investigate alternation complexity

[matiastoro]

Motivation

Make the LTJ variable elimination order (VEO) start from the variable with the smallest actual candidate set, read from the indexes, instead of coarse fixed heuristics. Also investigate whether alternation complexity gives a better ordering bound than AGM.

Current state (feasibility)

• estimate_var_weights (src/runtime/ltj/pattern_extract.rs) uses fixed heuristics, not real cardinalities:
  • NodeAttrCmp Eq → weight 1 (point lookup)
  • range op → ~10% of index size
  • NodeLabel → ~25% of index size
  • no filter → full index size
• The indexes already know exact sizes: lookup_node_eq / lookup_node_range / lookup_node_ordered return sets whose .len() is the true cardinality; the label index buckets have known lengths.

Proposal

At plan time, query the actual bound-set sizes for each variable's strongest filter and order the VEO by real cardinality (smallest first). This is directly implementable on top of the existing lookup_node_* APIs.

Research sub-item

Alternation complexity — a WCOJ measure beyond fractional edge cover (AGM). Investigate whether it yields a tighter runtime bound / a better variable ordering for our triple decompositions, and whether it is worth encoding in the VEO cost model.

Feasibility

• Cardinality-aware ordering: directly implementable (medium).
• Alternation complexity: research/investigation, then possibly a cost-model change.