Skip to content
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
70 changes: 61 additions & 9 deletions src/query/datalog/aggregate.rs
Original file line number Diff line number Diff line change
Expand Up @@ -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.
Expand Down Expand Up @@ -654,6 +656,27 @@ impl Running {
}
}

/// One completed result column and its charged slot/payload bytes.
pub(crate) struct WindowColumn {
pub(crate) values: Vec<Value>,
/// 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<usize>;
}

/// 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
Expand All @@ -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<Value>],
registry: &FunctionRegistry,
) -> Result<Vec<Vec<Value>>> {
meter: &mut impl WindowColumnMeter,
) -> Result<Vec<WindowColumn>> {
static NULL: Value = Value::Null;
let named = named_vars(find);
let col = |var: &str| named.iter().position(|v| v == var);
Expand All @@ -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::<Value>());
let entry = size_of::<WindowColumn>();
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 {
Expand Down Expand Up @@ -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;
Expand All @@ -746,19 +783,34 @@ 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;
}
}
start = end;
}
}
out.push(values);
out.push(WindowColumn { values, bytes });
}
Ok(out)
}
Expand Down
81 changes: 81 additions & 0 deletions src/query/engine/tests.rs
Original file line number Diff line number Diff line change
Expand Up @@ -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]
Expand Down
54 changes: 49 additions & 5 deletions src/query/engine/window.rs
Original file line number Diff line number Diff line change
Expand Up @@ -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;

Expand All @@ -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,
}

Expand All @@ -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"),
}
}
Expand Down Expand Up @@ -94,21 +98,37 @@ impl Window {

/// Every row, in input order, with its windows' cells.
fn finish(&mut self, ctx: &mut Ctx<'_>) -> Result<Vec<Vec<Cell>>> {
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<Vec<Vec<Cell>>> {
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::<WindowColumn>();
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)?;
let refused = growth(row.capacity(), size_of::<Cell>());
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)
}
Expand Down Expand Up @@ -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);
}

Expand All @@ -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<Counters>) {
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<usize> {
let bytes = value_bytes(value) - size_of::<Value>();
Held::charge(self, bytes)?;
Ok(bytes)
}
}
Loading