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

hawdb_executor/
binding.rs
