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
17mod graph_slots;
18pub use graph_slots::GraphSlots;
19
20use hawdb_core::{LabelId, Value};
21use hawdb_plan_cypher::SortDirection;
22use hawdb_storage::{NodeRecord, RelRecord};
23use std::cmp::Ordering;
24use std::collections::{BTreeMap, BTreeSet};
25
26#[derive(Debug, Clone, PartialEq, Eq)]
27pub struct Binding {
28    pub values: BTreeMap<String, Value>,
29    pub nodes: GraphSlots<NodeRecord>,
30    pub relationships: GraphSlots<RelRecord>,
31}
32
33impl Binding {
34    pub fn values(values: BTreeMap<String, Value>) -> Self {
35        Self {
36            values,
37            nodes: GraphSlots::new(),
38            relationships: GraphSlots::new(),
39        }
40    }
41
42    pub fn scalar(name: impl Into<String>, value: Value) -> Self {
43        Self::values(BTreeMap::from([(name.into(), value)]))
44    }
45}
46
47#[derive(Debug, Clone, PartialEq, Eq)]
48pub struct TopNBinding {
49    pub sort_values: Vec<(Value, SortDirection)>,
50    pub ordinal: u64,
51    pub binding: Binding,
52}
53
54impl TopNBinding {
55    pub fn memory_bytes(&self) -> usize {
56        binding_memory_bytes(&self.binding)
57            .saturating_add(sort_values_memory_bytes(&self.sort_values))
58    }
59}
60
61pub(crate) fn sort_values_memory_bytes(values: &Vec<(Value, SortDirection)>) -> usize {
62    let layout = std::mem::size_of::<Vec<(Value, SortDirection)>>().saturating_add(
63        values
64            .capacity()
65            .saturating_mul(std::mem::size_of::<(Value, SortDirection)>()),
66    );
67    values.iter().fold(layout, |total, (value, _)| {
68        total.saturating_add(value_memory_bytes(value).saturating_sub(std::mem::size_of::<Value>()))
69    })
70}
71
72impl Ord for TopNBinding {
73    fn cmp(&self, other: &Self) -> Ordering {
74        for ((left, direction), (right, other_direction)) in
75            self.sort_values.iter().zip(&other.sort_values)
76        {
77            debug_assert_eq!(direction, other_direction);
78            let ordering = match direction {
79                SortDirection::Asc => left.cmp(right),
80                SortDirection::Desc => left.cmp(right).reverse(),
81            };
82            if ordering != Ordering::Equal {
83                return ordering;
84            }
85        }
86        self.ordinal.cmp(&other.ordinal)
87    }
88}
89
90impl PartialOrd for TopNBinding {
91    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
92        Some(self.cmp(other))
93    }
94}
95
96pub fn map_payload_bytes(values: &BTreeMap<String, Value>) -> usize {
97    values.iter().fold(0usize, |total, (name, value)| {
98        total
99            .saturating_add(name.len())
100            .saturating_add(value_payload_bytes(value))
101    })
102}
103
104pub fn map_memory_bytes(values: &BTreeMap<String, Value>) -> usize {
105    map_memory_bytes_with_entries(values.iter().map(|(name, value)| (name.as_str(), value)))
106}
107
108fn map_memory_bytes_with_entries<'a>(values: impl Iterator<Item = (&'a str, &'a Value)>) -> usize {
109    std::mem::size_of::<BTreeMap<String, Value>>().saturating_add(values.fold(
110        0usize,
111        |total, (name, value)| {
112            total
113                .saturating_add(std::mem::size_of::<(String, Value)>() * 3)
114                .saturating_add(name.len())
115                .saturating_add(value_memory_bytes(value))
116        },
117    ))
118}
119
120/// Estimate the selected owned scan input with the same rules as its final
121/// node-only Binding, while all property payloads still belong to storage.
122pub(crate) fn projected_node_binding_memory_bytes(
123    variable: &str,
124    node: &NodeRecord,
125    required_properties: &BTreeSet<String>,
126) -> usize {
127    std::mem::size_of::<Binding>()
128        .saturating_add(variable.len())
129        .saturating_add(std::mem::size_of_val(&node.id))
130        .saturating_add(
131            node.labels
132                .len()
133                .saturating_mul(std::mem::size_of::<LabelId>()),
134        )
135        .saturating_add(map_memory_bytes_with_entries(
136            required_properties.iter().filter_map(|property| {
137                node.properties
138                    .get(property)
139                    .map(|value| (property.as_str(), value))
140            }),
141        ))
142        .saturating_add(graph_slot_memory_bytes(1))
143}
144
145pub fn value_memory_bytes(value: &Value) -> usize {
146    std::mem::size_of::<Value>().saturating_add(match value {
147        Value::Null | Value::Bool(_) | Value::Int(_) | Value::Float(_) | Value::Decimal(_) => 0,
148        Value::String(value) => value.len(),
149        Value::Binary(value) => value.len(),
150        Value::Vector(value) => value.encoded().len(),
151        Value::Uuid(_) => 16,
152        // Temporal values are stored inline in the `Value` slot, except
153        // durations, which are boxed to keep `Value` at 32 bytes.
154        Value::Date(_) | Value::LocalTime(_) | Value::LocalDateTime(_) | Value::DateTime(_) => 0,
155        Value::Duration(_) => std::mem::size_of::<hawdb_core::temporal::Duration>(),
156        Value::List(values) => values
157            .iter()
158            .fold(std::mem::size_of::<Vec<Value>>(), |total, value| {
159                total.saturating_add(value_memory_bytes(value))
160            }),
161        Value::Map(values) => map_memory_bytes(values),
162    })
163}
164
165pub fn binding_payload_bytes(binding: &Binding) -> usize {
166    map_payload_bytes(&binding.values).saturating_add(graph_binding_payload_bytes(binding))
167}
168
169fn graph_binding_payload_bytes(binding: &Binding) -> usize {
170    graph_binding_bytes(binding, map_payload_bytes)
171}
172
173fn graph_binding_bytes(
174    binding: &Binding,
175    property_bytes: fn(&BTreeMap<String, Value>) -> usize,
176) -> usize {
177    graph_binding_parts_bytes(
178        binding
179            .nodes
180            .iter()
181            .map(|(name, node)| (name.as_str(), node)),
182        binding
183            .relationships
184            .iter()
185            .map(|(name, row)| (name.as_str(), row)),
186        property_bytes,
187    )
188}
189
190fn graph_binding_parts_bytes<'a>(
191    nodes: impl Iterator<Item = (&'a str, &'a NodeRecord)>,
192    relationships: impl Iterator<Item = (&'a str, &'a RelRecord)>,
193    property_bytes: fn(&BTreeMap<String, Value>) -> usize,
194) -> usize {
195    nodes
196        .fold(0usize, |total, (name, node)| {
197            total
198                .saturating_add(name.len())
199                .saturating_add(std::mem::size_of_val(&node.id))
200                .saturating_add(
201                    node.labels
202                        .len()
203                        .saturating_mul(std::mem::size_of::<LabelId>()),
204                )
205                .saturating_add(property_bytes(&node.properties))
206        })
207        .saturating_add(relationships.fold(0usize, |total, (name, row)| {
208            total
209                .saturating_add(name.len())
210                .saturating_add(std::mem::size_of_val(&row.id))
211                .saturating_add(std::mem::size_of_val(&row.source))
212                .saturating_add(std::mem::size_of_val(&row.target))
213                .saturating_add(std::mem::size_of_val(&row.rel_type))
214                .saturating_add(property_bytes(&row.properties))
215        }))
216}
217
218pub(crate) fn binding_payload_bytes_with_parts<'a>(
219    values: impl Iterator<Item = (&'a str, &'a Value)>,
220    nodes: impl Iterator<Item = (&'a str, &'a NodeRecord)>,
221    relationships: impl Iterator<Item = (&'a str, &'a RelRecord)>,
222) -> usize {
223    values
224        .fold(0usize, |total, (name, value)| {
225            total
226                .saturating_add(name.len())
227                .saturating_add(value_payload_bytes(value))
228        })
229        .saturating_add(graph_binding_parts_bytes(
230            nodes,
231            relationships,
232            map_payload_bytes,
233        ))
234}
235
236pub fn binding_memory_bytes(binding: &Binding) -> usize {
237    binding_memory_bytes_with_values(
238        binding,
239        binding
240            .values
241            .iter()
242            .map(|(name, value)| (name.as_str(), value)),
243    )
244}
245
246/// Estimate an overwritten column from the final borrowed map. Resident
247/// container storage differs from transport payload and must be removed in full.
248pub(crate) fn binding_memory_bytes_replacing_value(
249    binding: &Binding,
250    name: &str,
251    value: &Value,
252) -> usize {
253    binding_memory_bytes_with_values(
254        binding,
255        binding
256            .values
257            .iter()
258            .filter(|(key, _)| key.as_str() != name)
259            .map(|(key, value)| (key.as_str(), value))
260            .chain(std::iter::once((name, value))),
261    )
262}
263
264/// Account a projection's borrowed values with the same retained graph and
265/// entry rules as its final owned Binding, before copying any of those values.
266pub(crate) fn binding_memory_bytes_with_values<'a>(
267    binding: &'a Binding,
268    values: impl Iterator<Item = (&'a str, &'a Value)>,
269) -> usize {
270    binding_memory_bytes_with_parts(
271        values,
272        binding
273            .nodes
274            .iter()
275            .map(|(name, node)| (name.as_str(), node)),
276        binding
277            .relationships
278            .iter()
279            .map(|(name, row)| (name.as_str(), row)),
280    )
281}
282
283pub(crate) fn binding_memory_bytes_with_parts<'a>(
284    values: impl Iterator<Item = (&'a str, &'a Value)>,
285    nodes: impl Iterator<Item = (&'a str, &'a NodeRecord)>,
286    relationships: impl Iterator<Item = (&'a str, &'a RelRecord)>,
287) -> usize {
288    let nodes_count = std::cell::Cell::new(0usize);
289    let relationships_count = std::cell::Cell::new(0usize);
290    let graph_bytes = graph_binding_parts_bytes(
291        nodes.inspect(|_| nodes_count.set(nodes_count.get().saturating_add(1))),
292        relationships
293            .inspect(|_| relationships_count.set(relationships_count.get().saturating_add(1))),
294        map_memory_bytes,
295    );
296    std::mem::size_of::<Binding>()
297        .saturating_add(graph_bytes)
298        // Charge every row as if its graph records were uniquely retained.
299        // Sharing reduces allocator traffic but never weakens admission. Include
300        // slot vectors, Arc headers, String/label layouts and record headers.
301        .saturating_add(graph_slot_memory_bytes(nodes_count.get()))
302        .saturating_add(graph_slot_memory_bytes(relationships_count.get()))
303        .saturating_add(values.fold(0usize, |total, (name, value)| {
304            total
305                .saturating_add(name.len())
306                .saturating_add(match value {
307                    Value::List(_) | Value::Map(_) => {
308                        value_memory_bytes(value).saturating_sub(std::mem::size_of::<Value>())
309                    }
310                    _ => value_payload_bytes(value),
311                })
312                .saturating_add(std::mem::size_of::<usize>() * 6)
313        }))
314}
315
316pub(crate) fn graph_slot_memory_bytes(entries: usize) -> usize {
317    if entries == 0 {
318        return 0;
319    }
320    // A Vec grown one slot at a time has capacity at most max(4, 2*len).
321    std::mem::size_of::<Vec<usize>>()
322        .saturating_add(2 * std::mem::size_of::<usize>())
323        .saturating_add(
324            entries
325                .saturating_mul(2)
326                .max(4)
327                .saturating_mul(2 * std::mem::size_of::<usize>()),
328        )
329        .saturating_add(entries.saturating_mul(10 * std::mem::size_of::<usize>()))
330}
331
332pub fn node_memory_bytes(node: &NodeRecord) -> usize {
333    std::mem::size_of::<NodeRecord>()
334        .saturating_add(
335            node.labels
336                .len()
337                .saturating_mul(std::mem::size_of::<LabelId>() * 3),
338        )
339        .saturating_add(map_memory_bytes(&node.properties))
340}
341
342pub fn relationship_memory_bytes(relationship: &RelRecord) -> usize {
343    std::mem::size_of::<RelRecord>().saturating_add(map_memory_bytes(&relationship.properties))
344}
345
346pub fn value_payload_bytes(value: &Value) -> usize {
347    value_ref_payload_bytes(value.as_ref())
348}
349
350pub fn value_ref_payload_bytes(value: hawdb_core::ValueRef<'_>) -> usize {
351    use hawdb_core::ValueRef;
352    match value {
353        ValueRef::Null => 0,
354        ValueRef::Bool(_) => std::mem::size_of::<bool>(),
355        ValueRef::Int(_) => std::mem::size_of::<i64>(),
356        ValueRef::Float(_) => std::mem::size_of::<f64>(),
357        ValueRef::Decimal(_) => 17,
358        ValueRef::String(value) => value.len(),
359        ValueRef::Binary(value) => value.len(),
360        ValueRef::Vector(value) => value.encoded().len(),
361        ValueRef::Uuid(_) => 16,
362        ValueRef::Date(_) => 4,
363        ValueRef::LocalTime(_) => 8,
364        ValueRef::LocalDateTime(_) => 12,
365        ValueRef::DateTime(_) => 16,
366        ValueRef::Duration(_) => 28,
367        ValueRef::List(values) => values.iter().fold(0usize, |total, value| {
368            total.saturating_add(value_payload_bytes(value))
369        }),
370        ValueRef::Map(values) => map_payload_bytes(values),
371    }
372}
373
374#[cfg(test)]
375mod tests {
376    use super::*;
377    use hawdb_core::RelTypeId;
378    use hawdb_storage::{NodeId, RelId};
379    use std::collections::BTreeSet;
380
381    #[test]
382    fn value_only_constructors_leave_graph_bindings_empty() {
383        let values = Binding::values(BTreeMap::from([("left".to_string(), Value::Int(1))]));
384        assert_eq!(values.values["left"], Value::Int(1));
385        assert!(values.nodes.is_empty());
386        assert!(values.relationships.is_empty());
387
388        let scalar = Binding::scalar("right", Value::Bool(true));
389        assert_eq!(scalar.values["right"], Value::Bool(true));
390        assert!(scalar.nodes.is_empty());
391        assert!(scalar.relationships.is_empty());
392    }
393
394    #[test]
395    fn binding_accounting_includes_nested_values_and_graph_records() {
396        let binding = Binding {
397            values: BTreeMap::from([(
398                "nested".to_string(),
399                Value::List(vec![Value::Int(1), Value::String("two".to_string())]),
400            )]),
401            nodes: BTreeMap::from([(
402                "n".to_string(),
403                NodeRecord {
404                    id: NodeId(7),
405                    labels: BTreeSet::from([LabelId(3)]),
406                    properties: BTreeMap::new(),
407                },
408            )])
409            .into(),
410            relationships: BTreeMap::from([(
411                "r".to_string(),
412                RelRecord {
413                    id: RelId(11),
414                    source: NodeId(7),
415                    target: NodeId(8),
416                    rel_type: RelTypeId(4),
417                    properties: BTreeMap::new(),
418                },
419            )])
420            .into(),
421        };
422
423        assert!(binding_payload_bytes(&binding) > "nested".len() + "two".len());
424        assert!(binding_memory_bytes(&binding) > binding_payload_bytes(&binding));
425    }
426
427    #[test]
428    fn projected_node_admission_matches_graph_slot_ownership() {
429        let node = NodeRecord {
430            id: NodeId(3),
431            labels: BTreeSet::from([LabelId(1)]),
432            properties: BTreeMap::from([
433                ("id".into(), Value::String("chosen".into())),
434                ("body".into(), Value::String("x".repeat(65536))),
435            ]),
436        };
437        let required = BTreeSet::from(["id".to_string()]);
438        let bytes = projected_node_binding_memory_bytes("n", &node, &required);
439        let mut projected = node.clone();
440        projected
441            .properties
442            .retain(|name, _| required.contains(name));
443        let binding = Binding {
444            values: BTreeMap::new(),
445            nodes: BTreeMap::from([("n".into(), projected)]).into(),
446            relationships: GraphSlots::new(),
447        };
448        assert_eq!(bytes, binding_memory_bytes(&binding));
449    }
450
451    #[test]
452    fn replacement_admission_matches_final_rows_without_mutating_input() {
453        let column = hawdb_plan_cypher::SCORING_RERANK_SCORE_COLUMN;
454        for previous in [
455            None,
456            Some(Value::Null),
457            Some(Value::Float(-1.0)),
458            Some(Value::List(vec![Value::Map(BTreeMap::from([(
459                "nested".into(),
460                Value::String("x".repeat(1_024)),
461            )]))])),
462        ] {
463            let mut input = Binding::scalar("score", Value::Float(0.5));
464            if let Some(previous) = previous {
465                input.values.insert(column.into(), previous);
466            }
467            let original = input.clone();
468            let estimate =
469                binding_memory_bytes_replacing_value(&input, column, &Value::Float(0.25));
470            assert_eq!(input, original, "admission must not alter the candidate");
471            let mut output = input;
472            output.values.insert(column.into(), Value::Float(0.25));
473            assert_eq!(estimate, binding_memory_bytes(&output));
474        }
475    }
476}
hawdb_executor/binding.rs

hawdb_executor/
binding.rs
