From 44ad17d0145c01d1dfef6ab81daa285b24ae1a1a Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 3 Apr 2026 09:01:36 +0530 Subject: [PATCH] =?UTF-8?q?perf(query):=20fix=20O(n=C2=B2)=20aggregation?= =?UTF-8?q?=20grouping?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Issue: groups.iter().position() is O(g) per binding, making total complexity O(b × g) where b = bindings and g = groups. Fix: Use BTreeMap, Vec> keyed by group key. - Complexity reduced from O(b × g) to O(b × log g) - Value already implements Ord, so Vec works as BTreeMap key --- src/query/datalog/executor.rs | 13 +++++-------- 1 file changed, 5 insertions(+), 8 deletions(-) diff --git a/src/query/datalog/executor.rs b/src/query/datalog/executor.rs index 38cb7c11cc..55f360d51e 100644 --- a/src/query/datalog/executor.rs +++ b/src/query/datalog/executor.rs @@ -791,18 +791,15 @@ fn compute_aggregation( group_var_names.extend(with_vars.iter().map(|s| s.as_str())); } - // Group using Vec + PartialEq scan (Value::Float doesn't implement Hash). - let mut groups: Vec<(Vec, Vec)> = Vec::new(); + // Group using BTreeMap keyed by group key (O(log g) instead of O(g) per binding). + use std::collections::BTreeMap; + let mut groups: BTreeMap, Vec> = BTreeMap::new(); for b in bindings { let key: Vec = group_var_names .iter() .map(|v| b.get(*v).cloned().unwrap_or(Value::Null)) .collect(); - if let Some(pos) = groups.iter().position(|(k, _)| k == &key) { - groups[pos].1.push(b); - } else { - groups.push((key.clone(), vec![b])); - } + groups.entry(key).or_default().push(b); } // Build a position map for Variable specs only (indices 0..n_vars in the key vector). @@ -821,7 +818,7 @@ fn compute_aggregation( } let mut results: Vec = Vec::new(); - for (key, group_bindings) in &groups { + for (key, group_bindings) in groups.iter() { let mut binding = Binding::new(); let mut skip = false;