From 675f42dd1877f07fc9a4919d983dd03a4e4b5568 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Mon, 26 Oct 2026 17:10:32 +0530 Subject: [PATCH] fix(query): count window result columns against memory limit (#761) --- src/query/datalog/aggregate.rs | 70 +++++++++++++++++++++++++---- src/query/engine/tests.rs | 81 ++++++++++++++++++++++++++++++++++ src/query/engine/window.rs | 54 ++++++++++++++++++++--- 3 files changed, 191 insertions(+), 14 deletions(-) diff --git a/src/query/datalog/aggregate.rs b/src/query/datalog/aggregate.rs index 13080f96c2..aa78fe3fdc 100644 --- a/src/query/datalog/aggregate.rs +++ b/src/query/datalog/aggregate.rs @@ -9,7 +9,9 @@ use crate::graph::types::Value; use anyhow::Result; use std::any::Any; use std::cmp::Ordering; +use std::collections::TryReserveError; use std::collections::{BTreeMap, BTreeSet}; +use std::mem::size_of; /// The class of a value in [`value_order`]: numbers, strings, booleans, /// refs, keywords, `nil`, sets. @@ -654,6 +656,27 @@ impl Running { } } +/// One completed result column and its charged slot/payload bytes. +pub(crate) struct WindowColumn { + pub(crate) values: Vec, + /// Charged slots and owned payload; excludes the outer vector's entry. + pub(crate) bytes: usize, +} + +/// Account for result columns without coupling the window calculation to the +/// engine's meter type. +pub(crate) trait WindowColumnMeter { + fn charge(&mut self, bytes: usize) -> Result<()>; + fn reserve( + &mut self, + result: std::result::Result<(), TryReserveError>, + charged: usize, + refused: usize, + ) -> Result<()>; + /// Charge the owned payload of a value (its slot is already charged). + fn charge_payload(&mut self, value: &Value) -> Result; +} + /// The value of each window of `find` for each row (spec §4), one list per /// window in `:find` order, by row position. `rows` holds each row's /// values of the [`named_vars`] of `find`, which hold every variable a @@ -664,12 +687,13 @@ impl Running { /// (spec §4.1). Rows with order-equal `:order-by` values are peers: `rank` /// is equal for them, and a running aggregate gives every peer its value at /// the last peer (spec §4.2). `lag` and `lead` read adjacent rows in the -/// sorted order, ignoring peer groups. Used by the executor and the engine. +/// sorted order, ignoring peer groups. pub(crate) fn windows( find: &[FindSpec], rows: &[Vec], registry: &FunctionRegistry, -) -> Result>> { + meter: &mut impl WindowColumnMeter, +) -> Result> { static NULL: Value = Value::Null; let named = named_vars(find); let col = |var: &str| named.iter().position(|v| v == var); @@ -692,7 +716,17 @@ pub(crate) fn windows( partitions.entry(read(r, part)).or_default().push(r); } - let mut values = vec![Value::Null; rows.len()]; + // Charge slots before allocating, then payloads as each slot is + // filled. The outer vector's entry stays charged until it is dropped. + let slots = rows.len().saturating_mul(size_of::()); + let entry = size_of::(); + let charged = slots.saturating_add(entry); + meter.charge(charged)?; + meter.reserve(out.try_reserve(1), charged, entry)?; + let mut values = Vec::new(); + meter.reserve(values.try_reserve_exact(rows.len()), charged, slots)?; + values.resize(rows.len(), Value::Null); + let mut bytes = slots; for mut keyed in partitions.into_values() { keyed.sort_by(|&a, &b| { let by_key = match ws.order { @@ -721,8 +755,11 @@ pub(crate) fn windows( pos.checked_add(1) }; let neighbor = adjacent.and_then(|p| keyed.get(p)); + let source = neighbor.map_or(&NULL, |&r| read(r, var)); + let payload = meter.charge_payload(source)?; + bytes = bytes.saturating_add(payload); if let Some(v) = values.get_mut(row) { - *v = neighbor.map_or(Value::Null, |&r| read(r, var).clone()); + *v = source.clone(); } } continue; @@ -746,11 +783,26 @@ pub(crate) fn windows( } } for (pos, &r) in (start..end).zip(peers) { - let value = match (&running, &ws.func) { - (Some(acc), _) => acc.value()?, - (None, WindowFunc::RowNumber) => position(pos)?, - (None, _) => position(start)?, + let (value, payload) = match (&running, &ws.func) { + (Some(acc @ (Running::Min(_) | Running::Max(_))), _) => { + let best = match acc { + Running::Min(e) | Running::Max(e) => { + e.best.as_ref().unwrap_or(&NULL) + } + _ => unreachable!(), + }; + let payload = meter.charge_payload(best)?; + (acc.value()?, payload) + } + (Some(acc), _) => { + let value = acc.value()?; + let payload = meter.charge_payload(&value)?; + (value, payload) + } + (None, WindowFunc::RowNumber) => (position(pos)?, 0), + (None, _) => (position(start)?, 0), }; + bytes = bytes.saturating_add(payload); if let Some(v) = values.get_mut(r) { *v = value; } @@ -758,7 +810,7 @@ pub(crate) fn windows( start = end; } } - out.push(values); + out.push(WindowColumn { values, bytes }); } Ok(out) } diff --git a/src/query/engine/tests.rs b/src/query/engine/tests.rs index 32d0c4d2b3..8c111eafef 100644 --- a/src/query/engine/tests.rs +++ b/src/query/engine/tests.rs @@ -2612,6 +2612,87 @@ fn qry_012_names_the_holder_over_the_limit() { assert!(err.to_string().contains("Recursive needs"), "Recursive"); } +/// #761: result columns coexist with the named input values. Long values in +/// two windows must use the same limit as the rest of Window's held state. +#[test] +fn window_result_columns_count_toward_query_memory_limit() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("window-memory.graph"); + { + let db = Minigraf::open(&path).unwrap(); + let suffix = "x".repeat(2048); + let facts: String = (0..40) + .map(|i| format!("[:e{i} :text \"{i:03}{suffix}\"]")) + .collect(); + db.execute(&format!("(transact [{facts}])")).unwrap(); + db.checkpoint().unwrap(); + } + let db = crate::OpenOptions::new() + .query_memory_limit(200_000) + .path(&path) + .open() + .unwrap(); + let mut cursor = db + .query( + "(query [:find ?e (min ?v :over (:order-by ?v)) \ + (max ?v :over (:order-by ?v)) :where [?e :text ?v]])", + ) + .unwrap(); + let meter = cursor.stream_mut().expect("engine").meter().clone(); + let err = match cursor.next_batch(1) { + Ok(_) => panic!("window result columns must count"), + Err(err) => err, + }; + assert_eq!(err.code(), "QRY-012"); + assert!(err.to_string().contains("Window needs")); + assert_eq!( + meter.used(), + 0, + "an error releases the held columns and input" + ); + drop(cursor); + drop(db); + + let db = crate::OpenOptions::new().path(&path).open().unwrap(); + let mut cursor = db + .query( + "(query [:find ?e (min ?v :over (:order-by ?v)) \ + (max ?v :over (:order-by ?v)) :where [?e :text ?v]])", + ) + .unwrap(); + let meter = cursor.stream_mut().expect("engine").meter().clone(); + let mut rows = 0; + while let Some(batch) = cursor.next_batch(100).unwrap() { + rows += batch.len(); + } + assert_eq!(rows, 40); + assert!( + meter.peak() > 200_000, + "both columns coexist with input values" + ); + assert_eq!(meter.used(), 0, "draining releases both columns and rows"); +} + +/// With no input rows, Window's first reserve is for its result column. +#[test] +fn window_result_column_allocator_refusal_is_qry_012() { + let db = Minigraf::in_memory().unwrap(); + let mut cursor = db + .query("(query [:find ?e (rank :over (:order-by ?v)) :where [?e :missing ?v]])") + .unwrap(); + let meter = cursor.stream_mut().expect("engine").meter().clone(); + super::meter::FAIL_RESERVE.with(|f| f.set(Some("Window"))); + let result = cursor.next_batch(1); + super::meter::FAIL_RESERVE.with(|f| f.set(None)); + let err = match result { + Ok(_) => panic!("result column allocation must fail"), + Err(err) => err, + }; + assert_eq!(err.code(), "QRY-012"); + assert!(err.to_string().contains("the allocator refused")); + assert_eq!(meter.used(), 0); +} + /// A refused allocation is `QRY-012` naming the holder (spec §4, second /// form), through the test hook. #[test] diff --git a/src/query/engine/window.rs b/src/query/engine/window.rs index 7783a7c71c..e52ff62c8e 100644 --- a/src/query/engine/window.rs +++ b/src/query/engine/window.rs @@ -14,9 +14,10 @@ use super::meter::{Held, Meter, cell_bytes, growth, row_bytes, value_bytes}; use super::project::value; use super::{BATCH_ROWS, Counters, Ctx, Operator}; use crate::graph::types::Value; -use crate::query::datalog::aggregate::windows; +use crate::query::datalog::aggregate::{WindowColumn, WindowColumnMeter, windows}; use crate::query::datalog::types::FindSpec; use anyhow::Result; +use std::collections::TryReserveError; use std::mem::size_of; use std::sync::Arc; @@ -38,6 +39,8 @@ pub(crate) struct Window { held: Held, /// `values`, until the windows are computed. held_values: Held, + /// Retained window result columns, including their outer vector. + held_columns: Held, counters: Counters, } @@ -59,6 +62,7 @@ impl Window { out: None, held: Held::new(meter, "Window"), held_values: Held::new(meter, "Window"), + held_columns: Held::new(meter, "Window"), counters: Counters::new("Window"), } } @@ -94,13 +98,24 @@ impl Window { /// Every row, in input order, with its windows' cells. fn finish(&mut self, ctx: &mut Ctx<'_>) -> Result>> { + let result = self.finish_rows(ctx); + if result.is_err() { + self.held.release(); + self.held_values.release(); + self.held_columns.release(); + } + result + } + + fn finish_rows(&mut self, ctx: &mut Ctx<'_>) -> Result>> { let values = std::mem::take(&mut self.values); let mut rows = std::mem::take(&mut self.cells); - let columns = windows(&self.find, &values, ctx.functions)?; + let mut columns = windows(&self.find, &values, ctx.functions, &mut self.held_columns)?; drop(values); self.held_values.release(); - for column in columns { - for (row, v) in rows.iter_mut().zip(&column) { + let outer = columns.len() * size_of::(); + for column in columns.drain(..) { + for (row, v) in rows.iter_mut().zip(&column.values) { let c = Cell::of_value(ctx.ids, ctx.keys, v)?; let n = cell_bytes(&c); self.held.charge(n)?; @@ -108,7 +123,12 @@ impl Window { self.held.reserve(row.try_reserve(1), n, refused)?; row.push(c); } + let bytes = column.bytes; + drop(column); + self.held_columns.uncharge(bytes); } + drop(columns); + self.held_columns.uncharge(outer); rows.reverse(); Ok(rows) } @@ -149,6 +169,7 @@ impl Operator for Window { self.out = None; self.held.release(); self.held_values.release(); + self.held_columns.release(); self.child.rewind(seed); } @@ -158,14 +179,37 @@ impl Operator for Window { self.out = Some(Vec::new()); self.held.release(); self.held_values.release(); + self.held_columns.release(); self.child.close(); } fn counters(&self, out: &mut Vec) { out.push(Counters { - bytes_held: (self.held.bytes() + self.held_values.bytes()) as u64, + bytes_held: (self.held.bytes() + self.held_values.bytes() + self.held_columns.bytes()) + as u64, ..self.counters }); self.child.counters(out); } } + +impl WindowColumnMeter for Held { + fn charge(&mut self, bytes: usize) -> Result<()> { + Held::charge(self, bytes) + } + + fn reserve( + &mut self, + result: std::result::Result<(), TryReserveError>, + charged: usize, + refused: usize, + ) -> Result<()> { + Held::reserve(self, result, charged, refused) + } + + fn charge_payload(&mut self, value: &Value) -> Result { + let bytes = value_bytes(value) - size_of::(); + Held::charge(self, bytes)?; + Ok(bytes) + } +}