perf(query): accelerate joins, existence checks, and counts - #1959

fluree-db-query/src/property_join.rs:1407 — optional, but the one I'd most like a number on. This swaps FlushSchedule::budgeted(budget, BATCHED_JOIN_SIZE) for ramped_from(budget, …), and the two differ in exactly the place that matters: budgeted is budget.clamp(MIN_FLUSH.min(cap), cap), so the first window was never below 1024, while ramped_from is initial.max(1).min(cap), so it is now the raw budget.

What makes this different from the rest of the PR is that PropertyJoinOperator::row_budget is fed by the pre-existing set_row_budget LIMIT pushdown, not by the new planning.row_goal — so unlike every other change here, this one fires on queries that have no row goal at all, and it changes behavior for budgeted property joins that exist on main today.

For a LIMIT 10 star whose matches come early, that is the "0.799 → 0.509 ms" win in the table and it's a good one. For a LIMIT 10 star that has to drain because matches are sparse, the window sequence becomes 10, 80, 640, 5120, 40960, cap where it used to be 1024, 8192, 65536, cap — roughly three extra flushes, each paying the per-flush setup that MIN_FLUSH was introduced to amortize (your own rewritten doc at operator/flush.rs:11-13 is what names that tension). The body says "dense and sparse star results match full-drain prefixes," which I read as a correctness check; I don't see a sparse timing anywhere.

Could we get the sparse-star wall time alongside the dense one? If it's flat, this is just a clean win and I'd say so in the body. If it isn't, a floor — ramped_from(budget.max(SOME_MIN), cap) — would keep the LIMIT 10 win without giving up the amortization on a drain.

• PR body, the DISTINCT-guard tradeoff paragraph — optional, needs one sentence rather than a code change. "The shorter chain changes from 19.4 ms to 24.8 ms when it returns to the ordinary throughput plan" is genuinely ambiguous about its baseline, and given how this repo treats speed I think it's worth disambiguating explicitly in the body.

Read as parallel to the sentence before it ("the longer chain improves from 128–131 ms to 104–107 ms"), it says the short chain is ~28% slower than before, which would be a blocking regression. Read as "with the startup hint it was 19.4; the guard sends it back to the throughput plan at 24.8," it's a forgone win and neutral against main.

I'm fairly confident it's the second, because when the guard fires row_goal is None and with None every new path is inert — hash_join.rs:474 requires row_goal.is_some_and(…), and the if let Some(goal) at execute/where_plan.rs:3355 isn't taken — so the plan should be byte-identical to main. The one thing that keeps me from asserting it is the property_join.rs change above, which fires independently of row_goal. One sentence ("24.8 ms matches main; the 19.4 ms was the hint we're deliberately giving up here") would close it.

Measured both on a c7i.8xlarge (50k fixture, 20 runs per query, alternating main and the branch on one machine).

Sparse star: you were right, it was a regression. star_sparse_limit (1 match in 1,000, LIMIT 10) went from 8.1 ms on main to 40–45 ms. The per-flush setup wasn't the cost; the overshoot was. Windows of 10, 80, 640, 5,120 and then 40,960 read 46,810 subjects, where main's 1,024 start read 9,216. A floor didn't fix it: 64 gave 32 ms and 256 gave 16 ms, and both gave back part of the dense win.

Fixed in ce18257 instead. Once a window has matched rows, the next is sized from the observed yield: twice the subjects the remaining rows need, capped at the ×8 step. That star now reads 7,150 subjects in 6.6 ms, and the dense LIMIT 10 star stays at 1.17 ms (main: 1.77 ms). One shape is still slightly slower than main: 1 match in 10,000 with LIMIT 3, 9.4 ms against 8.3 ms, because a rate estimated from the first match or two is rough. A new test in it_limit_stops_work checks that a 1-in-100 star with LIMIT 30 stops before reading half of its 12,000 subjects; without the fix it read all of them.

19.4 → 24.8 ms: confirmed a forgone win. The plan is identical to main's and the timing ratio is 0.97–1.02 across runs; the longer chain is neutral against main too. The PR body now says so, and has a table measured against main.

fluree-db-query/src/semijoin.rs:145 — optional. This is more of a question than a suggestion, and it's about the miss case rather than the hit case. The first outer row that arrives with an unbound key var builds the whole projection: for (i, key) in self.key_set.iter().enumerate() with a CompositeGroupKey clone per entry, so O(|key_set|) work and allocation before that one row gets its answer. The path it replaces was a single seeded any_solution, which for an indexed inner is a cheap lookup.

So the shape that loses is "very large inner key set, very few partially-bound outer rows" — e.g. a NOT EXISTS over a high-cardinality predicate sitting above an OPTIONAL that almost always matches, where maybe one row in a batch has the key unbound. We pay a second full pass over a set we already materialized in open(), to serve one row. I don't think this is common, and the memory is properly charged (record_alloc + checkpoint every 1024, which is nicely done), but it is a new cliff that didn't exist before.

Would it be worth deferring the build until some small number of rows have actually needed the same mask — a counter per positions key, build on the second or fourth hit — so a one-off unbound row keeps the old cheap path? It's minor and non-blocking, but if you agree it's right I'd rather see it folded in here than lost in the backlog.

• fluree-db-api/examples/query_operator_probe.rs (commenting here because the real subject is the absence of a bench, which has no line in this diff) — optional. The probe harness is a genuinely good artifact and I'm glad it exists. My worry is that it's the only thing standing behind six performance claims, and nothing will run it again.

Concretely: it's an examples/ binary, so it isn't a [[bench]] in fluree-db-api/Cargo.toml, it has no entry in regression-budget.json, and it isn't referenced by ci.yml or bench.yml. Meanwhile there's no bench anywhere for the shapes this PR accelerates — I grepped both bench directories for MINUS, NOT EXISTS/NotExists, CountAll and COUNT(*); the only COUNT(*) hit is query_hot_whole_graph_agg.rs, which is the whole-graph aggregate lane rather than the join-count lane you added, and query_hot_optional.rs's four lanes are all OPTIONAL, none a negation. And since db#1802 moved comparison to nightly, ci.yml on this branch has no bench job at all.

Net: every number in the table is true today and unguarded tomorrow, and so is the disclosed tradeoff. Even one bench — a query_hot_negation_count.rs with a MINUS lane, a NOT EXISTS lane and a grouped-COUNT(*)-over-join lane, plus its regression-budget.json entry — would turn six one-time measurements into something nightly can defend. I recognize that's the largest ask here; I'd still rather see it in this PR than filed, because after merge the shapes are fast and nobody has a reason to come back.

Projection build: leaving it as is. The cost is real, but bounded: open() has already paid one pass over the key set to build it, and each projection is one more pass, at most once per mask and for at most MAX_PARTIAL_KEY_SETS (4) masks. So the worst case, a huge key set with a single partially-bound row, pays one extra pass, charged to the memory budget as you noted. Deferring until a mask repeats would keep the per-row path alive for the first rows of every mask, which is the path the 5x NOT EXISTS win replaces, to save at most that one pass.

Bench: added in 8649fb2.

• query_hot_negation_count covers MINUS, NOT EXISTS after OPTIONAL, and filtered and grouped COUNT(*) over a join.
• query_hot_limit_startup covers the chain LIMIT 1 cases, the DISTINCT drain the guard protects, and a dense and a selective star.
• The selective star would have caught the property_join.rs overshoot. At small scale, built with and without that fix, it runs 4.40–4.54 ms before and 2.41–2.43 ms after.

Both benches have budgets and pass the reconcile check and the tiny --test smoke run.

Registering a bench only gets it smoke-run, though. The nightly compare runs a named subset, so e7d54ec adds both to that subset and to the CI-class capture. They gate once a baseline that includes them is captured (capture_baseline) and committed. Until then, compare lists them as new scenarios; the rest of the subset is already advisory because of the host-class mismatch.

fluree-db-query/src/execute/operator_tree.rs:3598 — nit. The DISTINCT elision is the one commit with no row in the perf table, and it adds a trait method (Operator::take_distinct_input) whose contract lives entirely in a doc comment: "The caller must prove that its consumer cannot observe input duplicates." I convinced myself it's sound — COUNT(DISTINCT ?x) dedups ?x regardless of input multiplicity, and the use_streaming && !select_needs_grouped_vars gate above is what protects grouped-list output, which distinct_count_with_grouped_list_keeps_terminal_distinct pins nicely. But with no measured win attached, I'm curious what it bought. If the answer is "not much yet, it's groundwork," a line in the body saying so would help the next reader decide whether the trait surface is earning its keep.

• fluree-db-query/src/property_path.rs:18-35 — nit, and not something this PR introduced. The doc rewrite is honest and I'd rather have it than the old text. But it's worth registering what it retracts: the previous comment claimed the both-unbound case was "intentionally an error to prevent accidental full-closure enumeration which can be extremely expensive," and the new text says it "materializes the whole closure and is not optimized." So a stated safety property turns out never to have been enforced. Given OPTIONAL with a left-bound variable in object position: quadratic CPU and ~170 KB of memory per required row (OOM) #1973 landed this morning with a 43 GB OOM on an adjacent unoptimized shape, I think that's worth more than a doc edit — even just a tracing::warn! or a record_alloc on the closure path so it shows up in a budget rather than in the kernel's OOM killer. Genuinely separable from this PR; flagging it so it doesn't disappear with the old comment.

fluree-db-query/src/planner.rs:139 — estimate_projected_distinct_rows multiplies per-variable NDVs, which is an upper bound on the projection, and operator_tree.rs:2308 uses it for "even the upper bound can't reach LIMIT + OFFSET, so drop the hint." Using an upper bound for a can't-possibly-reach test is the correct direction — the failure mode is keeping a hint you should have dropped, never dropping one you needed. The doc comment saying so ("use this only for costing, never to cap results") is exactly right, and projected_distinct_estimate_keeps_unknown_and_computed_domains_unknown pins all five None cases.

fluree-db-query/src/minus.rs:157 — I went looking for a semantic change in the single-shared-variable fast path, specifically the early return that skips unbound right rows. It matches the pre-existing rule: input_row_eliminated_all_unbound_no_match already asserted that a right row with no bound shared domain eliminates nothing, so this is a faster encoding of the same semantics rather than a behavior change. single_key_index_matches_compatibility_for_ids_and_other_terms cross-checking the compact index against rows_match for every binding kind — including EncodedSid with a t/op, a Long(7) literal, and an EncodedPid with the same numeric value — is the right instrument for that, and it's what let me stop worrying about the s_id-only key.

fluree-db-query/src/semijoin.rs:87 — the partial_keys_safe gate is the part that makes the projection sound, and it's drawn in the right place. Tracing key_vars back through choose_exists_strategy, key_vars is exactly outer_schema ∩ inner_produced_vars and outer_only_consumed already rejects any inner referencing an outer var it doesn't produce — so for a conjunction of triples every key var is bound in every inner solution, an unbound outer key really is free, and projection is equivalent to substitution. Routing Poisoned to Ok(None) rather than treating it as free is the detail that would have been easy to get wrong.