1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
//! Complete bounded sorting; no prefix answers, cursor state or generic sorter.
use super::{
MAX_COMPARISON_KEY, MAX_DISTINCT_VALUES, MAX_STATE_BYTES, Plan, QueryPage, Request,
admit_output, copy_projection, projection_size,
};
use crate::{EntitySchema, Error, IndexValue};
pub(super) struct Collection {
rows: Vec<Row>,
state_bytes: usize,
limit: usize,
descending: bool,
distinct: bool,
}
struct Row {
key: Vec<u8>,
bytes: Vec<u8>,
// Key prefix before the unique primary tie-breaker. Sorted DISTINCT admits
// exactly the projected fields here, so equality needs no second key buffer.
projected_key_end: usize,
}
impl Collection {
pub(super) fn new(request: &Request<'_>, distinct: bool) -> Self {
Self {
rows: Vec::new(),
state_bytes: 0,
limit: request.rows,
descending: request.descending,
distinct,
}
}
pub(super) fn push(
&mut self,
entity: &EntitySchema,
plan: &Plan<'_>,
values: &[IndexValue<'_>],
bytes: &[u8],
spans: &[(u16, u16)],
) -> Result<(), Error> {
let mut key = Vec::new();
let mut projected_key_end = 0;
for &(position, descending) in plan.sort.as_ref().ok_or(Error::InvalidQuery)? {
if entity.fields[position].name == entity.primary_key {
projected_key_end = key.len();
}
let start = key.len();
values[position].append_component(entity.fields[position].optional, &mut key);
if key.len() > MAX_COMPARISON_KEY {
return Err(Error::Limit);
}
// Components are prefix-free (including text terminators and absence).
// Complementing one component reverses it without changing later ties.
if descending {
for byte in &mut key[start..] {
*byte = !*byte;
}
}
}
if self.distinct {
// Admission makes this prefix exactly the projected tuple, regardless
// of field directions. Reuse retained keys; duplicate input consumes
// scan work, but no additional state or output buffer.
if self
.rows
.iter()
.any(|row| row.key[..row.projected_key_end] == key[..projected_key_end])
{
return Ok(());
}
if self.rows.len() == MAX_DISTINCT_VALUES {
return Err(Error::Limit);
}
} else if self.rows.len() == self.limit {
// At most 32 retained rows: find the worst cached key directly. The
// primary tie-breaker makes selection deterministic in either direction.
let (worst, row) = self
.rows
.iter()
.enumerate()
.max_by(|(_, a), (_, b)| {
if self.descending {
b.key.cmp(&a.key)
} else {
a.key.cmp(&b.key)
}
})
.ok_or(Error::InvalidQuery)?;
let better = if self.descending {
key > row.key
} else {
key < row.key
};
if !better {
return Ok(());
}
// Release the losing output before copying its replacement. A later
// refusal drops the whole collection, never exposing a partial answer.
let removed = self.rows.swap_remove(worst);
self.state_bytes -= removed.key.capacity() + removed.bytes.capacity();
drop(removed);
}
let size = plan
.projection
.map_or(bytes.len(), |mask| projection_size(spans, mask));
if self.state_bytes + key.capacity() + size > MAX_STATE_BYTES {
return Err(Error::Limit);
}
let row = plan.projection.map_or_else(
|| bytes.to_vec(),
|mask| copy_projection(bytes, spans, mask, size),
);
let charge = key.capacity() + row.capacity();
if self.state_bytes + charge > MAX_STATE_BYTES {
return Err(Error::Limit);
}
self.state_bytes += charge;
self.rows.push(Row {
key,
bytes: row,
projected_key_end,
});
Ok(())
}
// Only called after the scanner observes exhaustion. Keys include the unique
// primary tie-breaker; compare admitted bytes without decoding inside the sort.
pub(super) fn finish(
mut self,
byte_limit: usize,
page: &mut QueryPage<Vec<u8>>,
) -> Result<(), Error> {
self.rows.sort_unstable_by(|left, right| {
if self.descending {
right.key.cmp(&left.key)
} else {
left.key.cmp(&right.key)
}
});
for row in self.rows.into_iter().take(self.limit) {
admit_output(row.bytes.len(), byte_limit, &mut page.output_bytes)?;
page.rows.push(row.bytes);
}
Ok(())
}
}