hawdb_executor/
binding.rs

1// Copyright 2026 Nowledge
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Executor-owned row bindings and deterministic memory accounting.
16
17use hawdb_core::{LabelId, Value};
18use hawdb_plan_cypher::SortDirection;
19use hawdb_storage::{NodeRecord, RelRecord};
20use std::cmp::Ordering;
21use std::collections::{BTreeMap, BTreeSet};
22
23#[derive(Debug, Clone, PartialEq, Eq)]
24pub struct Binding {
25    pub values: BTreeMap<String, Value>,
26    pub nodes: BTreeMap<String, NodeRecord>,
27    pub relationships: BTreeMap<String, RelRecord>,
28}
29
30impl Binding {
31    pub fn values(values: BTreeMap<String, Value>) -> Self {
32        Self {
33            values,
34            nodes: BTreeMap::new(),
35            relationships: BTreeMap::new(),
36        }
37    }
38
39    pub fn scalar(name: impl Into<String>, value: Value) -> Self {
40        Self::values(BTreeMap::from([(name.into(), value)]))
41    }
42}
43
44#[derive(Debug, Clone, PartialEq, Eq)]
45pub struct TopNBinding {
46    pub sort_values: Vec<(Value, SortDirection)>,
47    pub ordinal: u64,
48    pub binding: Binding,
49}
50
51impl TopNBinding {
52    pub fn memory_bytes(&self) -> usize {
53        binding_memory_bytes(&self.binding)
54            .saturating_add(sort_values_memory_bytes(&self.sort_values))
55    }
56}
57
58pub(crate) fn sort_values_memory_bytes(values: &Vec<(Value, SortDirection)>) -> usize {
59    let layout = std::mem::size_of::<Vec<(Value, SortDirection)>>().saturating_add(
60        values
61            .capacity()
62            .saturating_mul(std::mem::size_of::<(Value, SortDirection)>()),
63    );
64    values.iter().fold(layout, |total, (value, _)| {
65        total.saturating_add(value_memory_bytes(value).saturating_sub(std::mem::size_of::<Value>()))
66    })
67}
68
69impl Ord for TopNBinding {
70    fn cmp(&self, other: &Self) -> Ordering {
71        for ((left, direction), (right, other_direction)) in
72            self.sort_values.iter().zip(&other.sort_values)
73        {
74            debug_assert_eq!(direction, other_direction);
75            let ordering = match direction {
76                SortDirection::Asc => left.cmp(right),
77                SortDirection::Desc => left.cmp(right).reverse(),
78            };
79            if ordering != Ordering::Equal {
80                return ordering;
81            }
82        }
83        self.ordinal.cmp(&other.ordinal)
84    }
85}
86
87impl PartialOrd for TopNBinding {
88    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
89        Some(self.cmp(other))
90    }
91}
92
93pub fn map_payload_bytes(values: &BTreeMap<String, Value>) -> usize {
94    values.iter().fold(0usize, |total, (name, value)| {
95        total
96            .saturating_add(name.len())
97            .saturating_add(value_payload_bytes(value))
98    })
99}
100
101pub fn map_memory_bytes(values: &BTreeMap<String, Value>) -> usize {
102    map_memory_bytes_with_entries(values.iter().map(|(name, value)| (name.as_str(), value)))
103}
104
105fn map_memory_bytes_with_entries<'a>(values: impl Iterator<Item = (&'a str, &'a Value)>) -> usize {
106    std::mem::size_of::<BTreeMap<String, Value>>().saturating_add(values.fold(
107        0usize,
108        |total, (name, value)| {
109            total
110                .saturating_add(std::mem::size_of::<(String, Value)>() * 3)
111                .saturating_add(name.len())
112                .saturating_add(value_memory_bytes(value))
113        },
114    ))
115}
116
117/// Estimate the selected owned scan input with the same rules as its final
118/// node-only Binding, while all property payloads still belong to storage.
119pub(crate) fn projected_node_binding_memory_bytes(
120    variable: &str,
121    node: &NodeRecord,
122    required_properties: &BTreeSet<String>,
123) -> usize {
124    std::mem::size_of::<Binding>()
125        .saturating_add(variable.len())
126        .saturating_add(std::mem::size_of_val(&node.id))
127        .saturating_add(
128            node.labels
129                .len()
130                .saturating_mul(std::mem::size_of::<LabelId>()),
131        )
132        .saturating_add(map_memory_bytes_with_entries(
133            required_properties.iter().filter_map(|property| {
134                node.properties
135                    .get(property)
136                    .map(|value| (property.as_str(), value))
137            }),
138        ))
139        .saturating_add(std::mem::size_of::<usize>() * 6)
140}
141
142pub fn value_memory_bytes(value: &Value) -> usize {
143    std::mem::size_of::<Value>().saturating_add(match value {
144        Value::Null | Value::Bool(_) | Value::Int(_) | Value::Float(_) => 0,
145        Value::String(value) => value.len(),
146        Value::Binary(value) => value.len(),
147        Value::Uuid(_) => 16,
148        Value::List(values) => values
149            .iter()
150            .fold(std::mem::size_of::<Vec<Value>>(), |total, value| {
151                total.saturating_add(value_memory_bytes(value))
152            }),
153        Value::Map(values) => map_memory_bytes(values),
154    })
155}
156
157pub fn binding_payload_bytes(binding: &Binding) -> usize {
158    map_payload_bytes(&binding.values).saturating_add(graph_binding_payload_bytes(binding))
159}
160
161fn graph_binding_payload_bytes(binding: &Binding) -> usize {
162    graph_binding_bytes(binding, map_payload_bytes)
163}
164
165fn graph_binding_bytes(
166    binding: &Binding,
167    property_bytes: fn(&BTreeMap<String, Value>) -> usize,
168) -> usize {
169    graph_binding_parts_bytes(
170        binding
171            .nodes
172            .iter()
173            .map(|(name, node)| (name.as_str(), node)),
174        binding
175            .relationships
176            .iter()
177            .map(|(name, row)| (name.as_str(), row)),
178        property_bytes,
179    )
180}
181
182fn graph_binding_parts_bytes<'a>(
183    nodes: impl Iterator<Item = (&'a str, &'a NodeRecord)>,
184    relationships: impl Iterator<Item = (&'a str, &'a RelRecord)>,
185    property_bytes: fn(&BTreeMap<String, Value>) -> usize,
186) -> usize {
187    nodes
188        .fold(0usize, |total, (name, node)| {
189            total
190                .saturating_add(name.len())
191                .saturating_add(std::mem::size_of_val(&node.id))
192                .saturating_add(
193                    node.labels
194                        .len()
195                        .saturating_mul(std::mem::size_of::<LabelId>()),
196                )
197                .saturating_add(property_bytes(&node.properties))
198        })
199        .saturating_add(relationships.fold(0usize, |total, (name, row)| {
200            total
201                .saturating_add(name.len())
202                .saturating_add(std::mem::size_of_val(&row.id))
203                .saturating_add(std::mem::size_of_val(&row.source))
204                .saturating_add(std::mem::size_of_val(&row.target))
205                .saturating_add(std::mem::size_of_val(&row.rel_type))
206                .saturating_add(property_bytes(&row.properties))
207        }))
208}
209
210pub(crate) fn binding_payload_bytes_with_parts<'a>(
211    values: impl Iterator<Item = (&'a str, &'a Value)>,
212    nodes: impl Iterator<Item = (&'a str, &'a NodeRecord)>,
213    relationships: impl Iterator<Item = (&'a str, &'a RelRecord)>,
214) -> usize {
215    values
216        .fold(0usize, |total, (name, value)| {
217            total
218                .saturating_add(name.len())
219                .saturating_add(value_payload_bytes(value))
220        })
221        .saturating_add(graph_binding_parts_bytes(
222            nodes,
223            relationships,
224            map_payload_bytes,
225        ))
226}
227
228pub fn binding_memory_bytes(binding: &Binding) -> usize {
229    binding_memory_bytes_with_values(
230        binding,
231        binding
232            .values
233            .iter()
234            .map(|(name, value)| (name.as_str(), value)),
235    )
236}
237
238/// Estimate an overwritten column from the final borrowed map. Resident
239/// container storage differs from transport payload and must be removed in full.
240pub(crate) fn binding_memory_bytes_replacing_value(
241    binding: &Binding,
242    name: &str,
243    value: &Value,
244) -> usize {
245    binding_memory_bytes_with_values(
246        binding,
247        binding
248            .values
249            .iter()
250            .filter(|(key, _)| key.as_str() != name)
251            .map(|(key, value)| (key.as_str(), value))
252            .chain(std::iter::once((name, value))),
253    )
254}
255
256/// Account a projection's borrowed values with the same retained graph and
257/// entry rules as its final owned Binding, before copying any of those values.
258pub(crate) fn binding_memory_bytes_with_values<'a>(
259    binding: &'a Binding,
260    values: impl Iterator<Item = (&'a str, &'a Value)>,
261) -> usize {
262    binding_memory_bytes_with_parts(
263        values,
264        binding
265            .nodes
266            .iter()
267            .map(|(name, node)| (name.as_str(), node)),
268        binding
269            .relationships
270            .iter()
271            .map(|(name, row)| (name.as_str(), row)),
272    )
273}
274
275pub(crate) fn binding_memory_bytes_with_parts<'a>(
276    values: impl Iterator<Item = (&'a str, &'a Value)>,
277    nodes: impl Iterator<Item = (&'a str, &'a NodeRecord)>,
278    relationships: impl Iterator<Item = (&'a str, &'a RelRecord)>,
279) -> usize {
280    let entries = std::cell::Cell::new(0usize);
281    let graph_bytes = graph_binding_parts_bytes(
282        nodes.inspect(|_| entries.set(entries.get().saturating_add(1))),
283        relationships.inspect(|_| entries.set(entries.get().saturating_add(1))),
284        map_memory_bytes,
285    );
286    std::mem::size_of::<Binding>()
287        .saturating_add(graph_bytes)
288        .saturating_add(
289            entries
290                .get()
291                .saturating_mul(std::mem::size_of::<usize>() * 6),
292        )
293        .saturating_add(values.fold(0usize, |total, (name, value)| {
294            total
295                .saturating_add(name.len())
296                .saturating_add(match value {
297                    Value::List(_) | Value::Map(_) => {
298                        value_memory_bytes(value).saturating_sub(std::mem::size_of::<Value>())
299                    }
300                    _ => value_payload_bytes(value),
301                })
302                .saturating_add(std::mem::size_of::<usize>() * 6)
303        }))
304}
305
306pub fn node_memory_bytes(node: &NodeRecord) -> usize {
307    std::mem::size_of::<NodeRecord>()
308        .saturating_add(
309            node.labels
310                .len()
311                .saturating_mul(std::mem::size_of::<LabelId>() * 3),
312        )
313        .saturating_add(map_memory_bytes(&node.properties))
314}
315
316pub fn relationship_memory_bytes(relationship: &RelRecord) -> usize {
317    std::mem::size_of::<RelRecord>().saturating_add(map_memory_bytes(&relationship.properties))
318}
319
320pub fn value_payload_bytes(value: &Value) -> usize {
321    match value {
322        Value::Null => 0,
323        Value::Bool(_) => std::mem::size_of::<bool>(),
324        Value::Int(_) => std::mem::size_of::<i64>(),
325        Value::Float(_) => std::mem::size_of::<f64>(),
326        Value::String(value) => value.len(),
327        Value::Binary(value) => value.len(),
328        Value::Uuid(_) => 16,
329        Value::List(values) => values.iter().fold(0usize, |total, value| {
330            total.saturating_add(value_payload_bytes(value))
331        }),
332        Value::Map(values) => map_payload_bytes(values),
333    }
334}
335
336#[cfg(test)]
337mod tests {
338    use super::*;
339    use hawdb_core::RelTypeId;
340    use hawdb_storage::{NodeId, RelId};
341    use std::collections::BTreeSet;
342
343    #[test]
344    fn value_only_constructors_leave_graph_bindings_empty() {
345        let values = Binding::values(BTreeMap::from([("left".to_string(), Value::Int(1))]));
346        assert_eq!(values.values["left"], Value::Int(1));
347        assert!(values.nodes.is_empty());
348        assert!(values.relationships.is_empty());
349
350        let scalar = Binding::scalar("right", Value::Bool(true));
351        assert_eq!(scalar.values["right"], Value::Bool(true));
352        assert!(scalar.nodes.is_empty());
353        assert!(scalar.relationships.is_empty());
354    }
355
356    #[test]
357    fn binding_accounting_includes_nested_values_and_graph_records() {
358        let binding = Binding {
359            values: BTreeMap::from([(
360                "nested".to_string(),
361                Value::List(vec![Value::Int(1), Value::String("two".to_string())]),
362            )]),
363            nodes: BTreeMap::from([(
364                "n".to_string(),
365                NodeRecord {
366                    id: NodeId(7),
367                    labels: BTreeSet::from([LabelId(3)]),
368                    properties: BTreeMap::new(),
369                },
370            )]),
371            relationships: BTreeMap::from([(
372                "r".to_string(),
373                RelRecord {
374                    id: RelId(11),
375                    source: NodeId(7),
376                    target: NodeId(8),
377                    rel_type: RelTypeId(4),
378                    properties: BTreeMap::new(),
379                },
380            )]),
381        };
382
383        assert!(binding_payload_bytes(&binding) > "nested".len() + "two".len());
384        assert!(binding_memory_bytes(&binding) > binding_payload_bytes(&binding));
385    }
386
387    #[test]
388    fn replacement_admission_matches_final_rows_without_mutating_input() {
389        let column = hawdb_plan_cypher::SCORING_RERANK_SCORE_COLUMN;
390        for previous in [
391            None,
392            Some(Value::Null),
393            Some(Value::Float(-1.0)),
394            Some(Value::List(vec![Value::Map(BTreeMap::from([(
395                "nested".into(),
396                Value::String("x".repeat(1_024)),
397            )]))])),
398        ] {
399            let mut input = Binding::scalar("score", Value::Float(0.5));
400            if let Some(previous) = previous {
401                input.values.insert(column.into(), previous);
402            }
403            let original = input.clone();
404            let estimate =
405                binding_memory_bytes_replacing_value(&input, column, &Value::Float(0.25));
406            assert_eq!(input, original, "admission must not alter the candidate");
407            let mut output = input;
408            output.values.insert(column.into(), Value::Float(0.25));
409            assert_eq!(estimate, binding_memory_bytes(&output));
410        }
411    }
412}
hawdb_executor/binding.rs

hawdb_executor/
binding.rs
