Repository navigation
perf(query): cut per-row overhead in type scans, stars, grouping, and MINUS - #1933
Conversation
… MINUS - Scans with a constant IRI object compare the row's encoded (o_type, o_key) instead of decoding the object to an IRI to compare it with the constant the cursor already matched. Every `?s rdf:type <C>` scan paid an IRI format per row. - PropertyJoinOperator keeps one insertion-ordered subject map, filtered in place, and emits by position. It no longer rebuilds a second map, clones every key, or hashes per subject on emission. Rows come out in driver-scan order rather than hash order. - GROUP BY and COUNT(DISTINCT) hash with Fx, probe with a reused key buffer, and clone key bindings only when a group is created. - MINUS builds its subtree with only the shared variables required, indexes batches as they arrive, hashes with Fx, and probes with reused scratch buffers. - Comparison and arithmetic evaluation no longer format the operator name for every row. - Shared helpers for the filtering operators: Batch::filter_rows, exists::any_solution, CompositeGroupKey::normalized.
bplatz
added
the
performance
aaj3f
left a comment
aaj3f
left a comment
There was a problem hiding this comment.
@bplatz how can I pushback against the numbers here? 🙃 In reality though, given the baseline of "these shapes are slow and the plans are right", everything in the PR holds up and the work is tidy. Full review below (I think most of the nits Claude has are more descriptive than anything in the code itself)
The MINUS rewrite is my favourite part of this — building the subtree with only the shared variables is exactly the kind of thing that looks like it should change MINUS semantics and doesn't, and lining it up with what the EXISTS semijoin already did is the right instinct. I spent a while trying to break it and couldn't: index_minus_batch only reads shared_vars, where_dedup_safe is hardcoded false on this path so the existence-only demotion can't fire, and the MINUS side ends up in a hash set where multiplicity is meaningless anyway. Batch::filter_rows is the other quiet win — four operators had each re-derived the #1439 zero-column trap on their own, and now one place knows about it. Everything else is straight per-row overhead removal with the planner left alone, which is the right altitude for a PR with these numbers on it. My notes below are all small; the only one I'd actually like to see land here is the ArithmeticOp::symbol() symmetry, since compare.rs in this same diff already shows the better shape.
One thing worth saying out loud for whoever reads the release notes: the "Result order" section is the user-visible part of this PR. A LIMIT n with no ORDER BY now returns a different — and, for the first time, stable and subject-ordered — set of rows than it did before. That's an improvement, not a regression, and nobody has a right to an order they didn't ask for. But it will move any golden file downstream that snapshots an unordered LIMIT result, and I'd rather we find that ourselves than have someone else find it.
Adherence to repo commitments:
- Patterns/abstractions: ✔ Extends the shared mechanisms rather than adding parallel ones —
Batch::filter_rows,exists::any_solutionandCompositeGroupKey::normalizedeach replace four to five hand-rolled copies, and the MINUS projection reuses the semijoin's existingrequired_where_varsseam. - Performance (speed first, memory second): ✔ Hot path throughout, and every hunk removes work from a per-row loop. No new allocation, clone, lock or
.collect()introduced into one;minus.rsalso stops materializingVec<Batch>before indexing. No performance-degradation risk. - Testing:
⚠️ CI is green on this head and I re-rangrp_query(471) and the lib suite (1602) locally, but the only new tests are the twoBatch::filter_rowsunit tests. The declared result-order change and the novelty behaviour of the new encoded-object comparison are both pinned by tests that arrive in #1936, not here. - Conventions: ✔ Self-describing subject, thorough five-bullet body, clippy and fmt green in CI,
docs/design/performance.mduntouched but nothing in it went stale at this layer.
Verified locally at 77c7dc8b8: cargo nextest run -p fluree-db-query -p fluree-db-api --test grp_query → 471 passed / 0 failed; cargo nextest run -p fluree-db-query --lib → 1602 passed, with both new test_batch_filter_rows* tests seen by name; full CI green on the exact head (fmt, clippy, test --all-features, testsuite-sparql, wasm32, sql-bridge).
Approving so you can merge when ready — but since #1936 sits on top of this and is the layer that actually pins the order guarantee, it's worth landing this one first and retargeting #1936 to main so it finally gets a CI run of its own.
| ctx: Option<&ExecutionContext<'_>>, | ||
| ) -> Result<Option<ComparableValue>> { | ||
| check_min_arity(args, 1, &self.to_string())?; | ||
| if args.is_empty() { |
There was a problem hiding this comment.
Optional — the two fixes for the same problem came out different, and I think the compare.rs one is the better of the two.
This is more of a question than a suggestion. CompareOp got self.symbol() at compare.rs:382 — zero-alloc, always, and Display for CompareOp already delegates to it (ir/expression.rs:736-740), so it's byte-identical to the old &self.to_string(). ArithmeticOp instead got if args.is_empty() { check_min_arity(args, 1, &self.to_string())?; }, which keeps the to_string() on a branch that can only ever be the error path.
check_min_arity(args, 1, ...) errors exactly when args.is_empty() (eval/helpers.rs:693-704), so the guard is a correct rewrite — it just reads like a conditional arity check when it isn't one.
Adding the same seven-line symbol() match to ArithmeticOp next to its Display impl at ir/expression.rs:752 would let both call sites read check_min_arity(args, 1, self.symbol())? and drop the guard entirely.
I recognize this is minor and non-blocking — but if you agree it's right, I'd rather see it folded in now than lost in the backlog.
| @@ -45,45 +46,15 @@ use fluree_db_core::Sid; | |||
| /// | |||
| /// Returns `None` if no rows pass the filter. | |||
| pub fn filter_batch( | |||
There was a problem hiding this comment.
Optional — filter_batch losing its schema parameter is a real contract change to a pub fn, and I don't think it's covered by the body's "Cleanup" heading.
The filtered batch now carries the input batch's schema instead of the operator's declared one. Four call sites are affected: having.rs:121, r2rml/operator.rs:539, fast_whole_graph_agg.rs:990, and filter.rs:696.
I traced it and I'm satisfied it's safe — the pre-existing "all rows kept, return input_batch" path in MINUS/semijoin/EXISTS already returned the input schema, so those operators were already required to agree, and trim_batch → Batch::retain selects columns by VarId rather than position, so column order can't silently transpose. Arguably this makes three operators consistent where they weren't.
We may want a sentence in the PR body saying so, though, since "these helpers replace duplicated code" reads as a no-op refactor and this one isn't quite.
There was a problem hiding this comment.
Addressed in the PR body: added a paragraph under Cleanup.
| self.groups.entry(group_key).or_insert_with(|| GroupState { | ||
| key_bindings, | ||
| agg_states: agg_specs_ref | ||
| if !self.groups.contains_key(&group_key) { |
There was a problem hiding this comment.
Optional — worth a comment here so nobody "fixes" this back into an entry().
The probe went from one entry() to contains_key → insert → get_mut, which is two hashes for an existing group and three for a new one.
It's clearly the right trade — it buys not allocating a Vec<GroupKeyOwned> per row, and your own numbers (93.7 → 39.3 ms) say so decisively. But the shape reads like an obvious entry() refactor waiting to happen, and the reason it can't be one — the key has to outlive the probe, and std's HashMap has no stable raw_entry — isn't written down anywhere.
Two lines of comment would save the next person the trace.
There was a problem hiding this comment.
Addressed in 1bc7b42. Rather than comment the three-probe shape, it now uses hashbrown's raw_entry_mut().from_key() (as distinct.rs already does): one hash per row, key cloned only when a new group opens.
| self.pending_subjects = self.subject_values.keys().cloned().collect(); | ||
| // Keep only subjects that have values for ALL predicates | ||
| let emitted_required = &self.emitted_required; | ||
| all_subject_values.retain(|_, (_sb, mask, values)| { |
There was a problem hiding this comment.
Optional — a question about the stack rather than about this hunk.
The move to IndexMap + a positional current_subject is only sound in this PR because subject_values stops being mutated once open() returns. #1936 then starts mutating it across chunks, where positional stability becomes load-bearing for a different reason (an append-only map keeps earlier indices valid).
I'm not suggesting a change. I'd just like the "positions are stable because the map is append-only after this point" invariant written on SubjectMap or on current_subject, since it's the thing that has to keep being true through #1936 and whatever comes after it.
There was a problem hiding this comment.
Addressed in 1bc7b42. The invariant is on SubjectMap, which also moved above the struct: it had been splitting PropertyJoinOperator's doc comment.
| (0..self.len).map(move |row| RowView { batch: self, row }) | ||
| } | ||
|
|
||
| /// Keep the rows whose `keep` flag is set, or `None` when none survive. |
There was a problem hiding this comment.
Praise — Batch::filter_rows is the good kind of extraction.
Four operators had each hand-rolled the same "count the keeps, early-return if zero, early-return if all, otherwise rebuild the columns" block — and filter.rs and the operators had separately re-derived the zero-column-batch length workaround from #1439.
Now there's one place that knows about it, it's unit-tested for exactly that case (binding.rs:1990), and taking self by value makes the all-kept path a move instead of a rebuild.
| &self.minus_patterns, | ||
| self.stats.clone(), | ||
| None, | ||
| Some(&self.shared_vars), |
There was a problem hiding this comment.
Praise — this is the hunk I was most prepared to find a hole in, and it holds.
Narrowing the MINUS subtree to the shared variables sounds like it should be able to change what MINUS removes, and it can't, for three reasons I traced rather than assumed: index_minus_batch only ever reads self.shared_vars, so no other column was being consumed; build_where_operators_seeded hardcodes where_dedup_safe: false (execute/where_plan.rs:2097), which makes property_join_needed_vars pin every variable object as needed and so blocks the existence-only semijoin demotion that projection pushdown would otherwise license (where_plan.rs:1535-1542); and augment_with_suffix keeps every variable a later pattern correlates on.
On top of that the MINUS side lands in a HashSet and a membership-tested Vec, so subtree multiplicity is meaningless even if it did change.
Matching what the EXISTS semijoin already did at semijoin.rs:155 is the right instinct.
- ArithmeticOp::symbol() mirrors CompareOp; arity check drops the error-path to_string() guard. - GROUP BY probe uses a hashbrown raw entry: one hash per row, key cloned only when a new group opens. - SubjectMap documents the append-only invariant positional emission relies on, and no longer splits PropertyJoinOperator's doc comment.
2 participants
A performance boost for several common query patterns, mostly those that join
?s a <Class>with other triples, plus some cleanup of duplicated helpers. No planner decisions change, so every query keeps the plan it had.Performance
?s rdf:type <C>decoded each row's object to an IRI string, just to compare it with the constant the cursor had already matched by id. It now compares the encoded(o_type, o_key). Literal constants still take the decoded comparison, since they match loosely across datatypes.PropertyJoinOperator. The operator now keeps one insertion-ordered subject map, filtered in place after the scans, and emits rows by position. Before, it rebuilt a second map from the first, cloned every key, and hashed once per subject while emitting.Cleanup
Batch::filter_rows,exists::any_solutionandCompositeGroupKey::normalizedreplace code copied across the EXISTS, semijoin, MINUS, FILTER, HAVING and membership-join operators.One of these is not a pure refactor.
filter_batchno longer takes a schema, so a filtered batch keeps its input batch's schema. Before, it was relabelled with the operator's schema. The old code copied columns by position and then applied that schema, so a child whose column order differed would have been silently mislabelled. The callers (FILTER, HAVING, the R2RML scan and the whole-graph histogram) all pass batches whose schema already matches the operator's, and HAVING re-trims byVarId, so results don't change.Result order
Queries without ORDER BY may return rows in a different order. Property-join rows now follow subject order instead of hash order. Grouped output was ordered by a randomly seeded hasher before, so it varied between runs; it is now stable.
Timings
The dataset is synthetic: 100k
ex:Personplus 25kex:Pet, about 825k triples, indexed. Each figure is the median over 9 runs.SELECT DISTINCT ?n { ?p a ex:Person ; ex:name ?n } LIMIT 1?p a ex:Person MINUS { ?p ex:email ?e }ex:nameFILTER NOT EXISTS, same two patterns?p a ex:Person ; ex:age ?a FILTER(?a > 60)GROUP BY ?c COUNT(*)over?p a ex:Person ; ex:city ?cGROUP BY ?c COUNT(DISTINCT ?f)over city × knows?x ex:knows ?z . ?y ex:knows ?z FILTER(?x != ?y)Patterns already served by a fast path, such as single-pattern DISTINCT, GROUP BY and range FILTER, are unchanged.