alopex_sql/storage/
key.rs

1use alopex_core::{CanonicalRowKey, RowKeyRange};
2
3use super::error::{Result, StorageError};
4use super::value::SqlValue;
5
6/// KeyEncoder generates lexicographically ordered keys for table rows and indexes.
7///
8/// Layouts:
9/// - Row key:   0x01 | table_id (u32 BE) | row_id (u64 BE)
10/// - Index key: 0x02 | index_id (u32 BE) | encoded_value(s) | row_id (u64 BE)
11/// - Sequence:  0x04 | table_id (u32 BE)
12pub struct KeyEncoder;
13
14impl KeyEncoder {
15    /// SQL row key.
16    pub fn row_key(table_id: u32, row_id: u64) -> Vec<u8> {
17        CanonicalRowKey::new(table_id, row_id).encode()
18    }
19
20    /// Decode SQL row key.
21    pub fn decode_row_key(key: &[u8]) -> Result<(u32, u64)> {
22        let key = CanonicalRowKey::decode(key).map_err(|_| StorageError::InvalidKeyFormat)?;
23        Ok((key.table_id(), key.row_id()))
24    }
25
26    /// Prefix for all rows of a table.
27    pub fn table_prefix(table_id: u32) -> Vec<u8> {
28        CanonicalRowKey::table_prefix(table_id)
29    }
30
31    /// Rechecks an encoded primary key against a canonical physical range.
32    ///
33    /// Secondary-index order is unrelated to a table's primary-key range, so
34    /// callers must use this after resolving every index hit.
35    pub fn primary_key_is_in_range(key: &[u8], range: RowKeyRange) -> Result<bool> {
36        let key = CanonicalRowKey::decode(key).map_err(|_| StorageError::InvalidKeyFormat)?;
37        Ok(range.contains(key))
38    }
39
40    /// Index key (single value).
41    pub fn index_key(index_id: u32, value: &SqlValue, row_id: u64) -> Result<Vec<u8>> {
42        let mut buf = Vec::with_capacity(1 + 4 + 16);
43        buf.push(0x02);
44        buf.extend_from_slice(&index_id.to_be_bytes());
45        encode_index_value(value, &mut buf)?;
46        buf.extend_from_slice(&row_id.to_be_bytes());
47        Ok(buf)
48    }
49
50    /// Index key (composite).
51    pub fn composite_index_key(index_id: u32, values: &[SqlValue], row_id: u64) -> Result<Vec<u8>> {
52        let mut buf = Vec::with_capacity(1 + 4 + values.len() * 16 + 8);
53        buf.push(0x02);
54        buf.extend_from_slice(&index_id.to_be_bytes());
55        for v in values {
56            encode_index_value(v, &mut buf)?;
57        }
58        buf.extend_from_slice(&row_id.to_be_bytes());
59        Ok(buf)
60    }
61
62    /// Prefix for all entries of an index.
63    pub fn index_prefix(index_id: u32) -> Vec<u8> {
64        let mut buf = Vec::with_capacity(1 + 4);
65        buf.push(0x02);
66        buf.extend_from_slice(&index_id.to_be_bytes());
67        buf
68    }
69
70    /// Prefix for equality lookups on a specific value within an index.
71    pub fn index_value_prefix(index_id: u32, value: &SqlValue) -> Result<Vec<u8>> {
72        let mut buf = Vec::with_capacity(1 + 4 + 16);
73        buf.push(0x02);
74        buf.extend_from_slice(&index_id.to_be_bytes());
75        encode_index_value(value, &mut buf)?;
76        Ok(buf)
77    }
78
79    /// Prefix for equality lookups on a composite value within an index.
80    pub fn composite_index_prefix(index_id: u32, values: &[SqlValue]) -> Result<Vec<u8>> {
81        let mut buf = Vec::with_capacity(1 + 4 + values.len() * 16);
82        buf.push(0x02);
83        buf.extend_from_slice(&index_id.to_be_bytes());
84        for v in values {
85            encode_index_value(v, &mut buf)?;
86        }
87        Ok(buf)
88    }
89
90    /// Sequence key for auto-increment RowID tracking.
91    pub fn sequence_key(table_id: u32) -> Vec<u8> {
92        let mut buf = Vec::with_capacity(1 + 4);
93        buf.push(0x04);
94        buf.extend_from_slice(&table_id.to_be_bytes());
95        buf
96    }
97}
98
99fn encode_index_value(value: &SqlValue, buf: &mut Vec<u8>) -> Result<()> {
100    match value {
101        SqlValue::Null => {
102            buf.push(0x00);
103        }
104        SqlValue::Integer(v) => {
105            buf.push(0x01);
106            let x = (*v as u32) ^ 0x8000_0000;
107            buf.extend_from_slice(&x.to_be_bytes());
108        }
109        SqlValue::BigInt(v) => {
110            buf.push(0x02);
111            let x = (*v as u64) ^ 0x8000_0000_0000_0000;
112            buf.extend_from_slice(&x.to_be_bytes());
113        }
114        SqlValue::Float(v) => {
115            buf.push(0x03);
116            buf.extend_from_slice(&encode_ordered_f32(*v).to_be_bytes());
117        }
118        SqlValue::Double(v) => {
119            buf.push(0x04);
120            buf.extend_from_slice(&encode_ordered_f64(*v).to_be_bytes());
121        }
122        SqlValue::Text(s) => {
123            buf.push(0x05);
124            buf.extend_from_slice(s.as_bytes());
125            buf.push(0x00); // terminator
126        }
127        SqlValue::Blob(bytes) => {
128            buf.push(0x06);
129            let len = u32::try_from(bytes.len())
130                .expect("blob length exceeds u32::MAX (index encoding limit)");
131            buf.extend_from_slice(&len.to_be_bytes());
132            buf.extend_from_slice(bytes);
133        }
134        SqlValue::Boolean(b) => {
135            buf.push(0x07);
136            buf.push(u8::from(*b));
137        }
138        SqlValue::Timestamp(v) => {
139            buf.push(0x08);
140            let x = (*v as u64) ^ 0x8000_0000_0000_0000;
141            buf.extend_from_slice(&x.to_be_bytes());
142        }
143        SqlValue::Vector(_values) => {
144            // Vector ordering is undefined for BTree lexicographic indexes.
145            return Err(StorageError::TypeMismatch {
146                expected: "indexable scalar type".into(),
147                actual: "Vector".into(),
148            });
149        }
150    }
151    Ok(())
152}
153
154fn encode_ordered_f32(v: f32) -> u32 {
155    let bits = v.to_bits();
156    if bits & 0x8000_0000 != 0 {
157        !bits
158    } else {
159        bits ^ 0x8000_0000
160    }
161}
162
163fn encode_ordered_f64(v: f64) -> u64 {
164    let bits = v.to_bits();
165    if bits & 0x8000_0000_0000_0000 != 0 {
166        !bits
167    } else {
168        bits ^ 0x8000_0000_0000_0000
169    }
170}
171
172#[cfg(test)]
173mod tests {
174    use super::*;
175    use proptest::prelude::*;
176    use std::cmp::Ordering;
177
178    #[test]
179    fn row_key_roundtrip() {
180        let key = KeyEncoder::row_key(10, 42);
181        assert_eq!(key.len(), 13);
182        let (t, r) = KeyEncoder::decode_row_key(&key).unwrap();
183        assert_eq!((t, r), (10, 42));
184    }
185
186    #[test]
187    fn table_prefix_matches_row_key_prefix() {
188        let prefix = KeyEncoder::table_prefix(7);
189        let key = KeyEncoder::row_key(7, 1);
190        assert!(key.starts_with(&prefix));
191    }
192
193    #[test]
194    fn sql_row_keys_share_the_core_canonical_interval_contract() {
195        use alopex_core::{CanonicalRowKey, RowKeyRange};
196
197        let range = RowKeyRange::new(7, Some(10), Some(20)).unwrap();
198        let encoded = range.encoded_bounds();
199
200        assert_eq!(encoded.lower_inclusive, KeyEncoder::row_key(7, 10));
201        assert_eq!(encoded.upper_exclusive, KeyEncoder::row_key(7, 20));
202        assert!(range.contains(CanonicalRowKey::decode(&KeyEncoder::row_key(7, 19)).unwrap()));
203        assert!(!range.contains(CanonicalRowKey::decode(&KeyEncoder::row_key(7, 20)).unwrap()));
204    }
205
206    #[test]
207    fn secondary_index_hits_are_rechecked_against_the_primary_row_key_range() {
208        use alopex_core::{CanonicalRowKey, RowKeyRange};
209
210        let range = RowKeyRange::new(7, Some(10), Some(20)).unwrap();
211        let resolved_index_hits = [
212            CanonicalRowKey::decode(&KeyEncoder::row_key(7, 19)).unwrap(),
213            CanonicalRowKey::decode(&KeyEncoder::row_key(7, 20)).unwrap(),
214            CanonicalRowKey::decode(&KeyEncoder::row_key(8, 19)).unwrap(),
215        ];
216
217        let accepted = resolved_index_hits
218            .into_iter()
219            .filter(|row_key| range.contains(*row_key))
220            .collect::<Vec<_>>();
221
222        assert_eq!(accepted, vec![CanonicalRowKey::new(7, 19)]);
223    }
224
225    #[test]
226    fn encoded_primary_key_range_recheck_rejects_wrong_table_and_upper_bound() {
227        use alopex_core::RowKeyRange;
228
229        let range = RowKeyRange::new(7, Some(10), Some(20)).unwrap();
230        assert!(KeyEncoder::primary_key_is_in_range(&KeyEncoder::row_key(7, 19), range).unwrap());
231        assert!(!KeyEncoder::primary_key_is_in_range(&KeyEncoder::row_key(7, 20), range).unwrap());
232        assert!(!KeyEncoder::primary_key_is_in_range(&KeyEncoder::row_key(8, 19), range).unwrap());
233    }
234
235    #[test]
236    fn index_prefix_matches_index_key_prefix() {
237        let prefix = KeyEncoder::index_prefix(5);
238        let key = KeyEncoder::index_key(5, &SqlValue::Integer(1), 99).unwrap();
239        assert!(key.starts_with(&prefix));
240    }
241
242    #[test]
243    fn integer_ordering_matches_lexicographic() {
244        assert_monotonic_ints((-128..=127).collect());
245    }
246
247    #[test]
248    fn bigint_ordering_matches_lexicographic() {
249        assert_monotonic_i64(vec![i64::MIN, -10, -1, 0, 1, 2, 100, i64::MAX]);
250    }
251
252    #[test]
253    fn float_ordering_matches_lexicographic_with_specials() {
254        let values = vec![
255            -f32::INFINITY,
256            -1.5,
257            -0.0,
258            0.0,
259            0.5,
260            f32::INFINITY,
261            f32::NAN,
262        ];
263        assert_monotonic_f32(values);
264    }
265
266    #[test]
267    fn double_ordering_matches_lexicographic_with_specials() {
268        let values = vec![
269            -f64::INFINITY,
270            -123.456,
271            -0.0,
272            0.0,
273            1.2345,
274            f64::INFINITY,
275            f64::NAN,
276        ];
277        assert_monotonic_f64(values);
278    }
279
280    #[test]
281    fn text_ordering_handles_ascii_and_multibyte() {
282        let values = vec!["", "a", "aa", "b", "é", "あ", "あい", "🍣"];
283        assert_monotonic_text(values);
284    }
285
286    #[test]
287    fn blob_ordering_respects_length_then_bytes() {
288        let values = vec![
289            vec![],
290            vec![0x00],
291            vec![0x00, 0x01],
292            vec![0x01],
293            vec![0x01, 0x00],
294            vec![0xFF],
295        ];
296        assert_monotonic_blob(values);
297    }
298
299    #[test]
300    fn boolean_ordering() {
301        assert_monotonic_bool();
302    }
303
304    #[test]
305    fn vector_is_rejected_for_index_key() {
306        let err = KeyEncoder::index_key(1, &SqlValue::Vector(vec![1.0, 2.0]), 0).unwrap_err();
307        match err {
308            StorageError::TypeMismatch { actual, .. } => {
309                assert_eq!(actual, "Vector");
310            }
311            other => panic!("expected TypeMismatch for Vector, got {other:?}"),
312        }
313    }
314
315    #[test]
316    fn timestamp_ordering() {
317        let values = vec![-5, -1, 0, 1, 10, i64::MAX];
318        assert_monotonic_timestamp(values);
319    }
320
321    #[test]
322    fn composite_key_maintains_lexicographic_tuple_order() {
323        let mut tuples = [(0, 0), (0, 1), (1, 0), (1, 2), (2, 0), (2, 2)].to_vec();
324        tuples.sort();
325
326        let mut prev: Option<Vec<u8>> = None;
327        for (i, (a, b)) in tuples.iter().enumerate() {
328            let key = KeyEncoder::composite_index_key(
329                9,
330                &[SqlValue::Integer(*a), SqlValue::Integer(*b)],
331                i as u64,
332            )
333            .unwrap();
334            if let Some(p) = prev {
335                assert!(
336                    p < key,
337                    "composite key ordering violated for ({a},{b}) at position {i}"
338                );
339            }
340            prev = Some(key);
341        }
342    }
343
344    fn assert_monotonic_ints(values: Vec<i32>) {
345        let mut sorted = values;
346        sorted.sort();
347        let mut prev: Option<(Vec<u8>, i32)> = None;
348        for (i, v) in sorted.iter().enumerate() {
349            let key = KeyEncoder::index_key(1, &SqlValue::Integer(*v), i as u64).unwrap();
350            if let Some((prev_key, prev_v)) = prev {
351                let ordering = prev_v.cmp(v);
352                let key_ord = prev_key.cmp(&key);
353                assert!(
354                    ordering == key_ord
355                        || (ordering == Ordering::Equal && key_ord == Ordering::Less),
356                    "integer ordering mismatch: prev={prev_v}, curr={v}"
357                );
358            }
359            prev = Some((key, *v));
360        }
361    }
362
363    fn assert_monotonic_i64(values: Vec<i64>) {
364        let mut sorted = values;
365        sorted.sort();
366        let mut prev: Option<(Vec<u8>, i64)> = None;
367        for (i, v) in sorted.iter().enumerate() {
368            let key = KeyEncoder::index_key(1, &SqlValue::BigInt(*v), i as u64).unwrap();
369            if let Some((prev_key, prev_v)) = prev {
370                let ordering = prev_v.cmp(v);
371                let key_ord = prev_key.cmp(&key);
372                assert!(
373                    ordering == key_ord
374                        || (ordering == Ordering::Equal && key_ord == Ordering::Less),
375                    "bigint ordering mismatch: prev={prev_v}, curr={v}"
376                );
377            }
378            prev = Some((key, *v));
379        }
380    }
381
382    fn assert_monotonic_f32(values: Vec<f32>) {
383        let mut sorted = values;
384        sorted.sort_by(|a, b| a.total_cmp(b));
385        let mut prev: Option<(Vec<u8>, f32)> = None;
386        for (i, v) in sorted.iter().enumerate() {
387            let key = KeyEncoder::index_key(1, &SqlValue::Float(*v), i as u64).unwrap();
388            if let Some((prev_key, prev_v)) = prev {
389                let ordering = prev_v.total_cmp(v);
390                let key_ord = prev_key.cmp(&key);
391                assert!(
392                    ordering == key_ord
393                        || (ordering == Ordering::Equal && key_ord == Ordering::Less),
394                    "float ordering mismatch: prev={prev_v}, curr={v}"
395                );
396            }
397            prev = Some((key, *v));
398        }
399    }
400
401    fn assert_monotonic_f64(values: Vec<f64>) {
402        let mut sorted = values;
403        sorted.sort_by(|a, b| a.total_cmp(b));
404        let mut prev: Option<(Vec<u8>, f64)> = None;
405        for (i, v) in sorted.iter().enumerate() {
406            let key = KeyEncoder::index_key(1, &SqlValue::Double(*v), i as u64).unwrap();
407            if let Some((prev_key, prev_v)) = prev {
408                let ordering = prev_v.total_cmp(v);
409                let key_ord = prev_key.cmp(&key);
410                assert!(
411                    ordering == key_ord
412                        || (ordering == Ordering::Equal && key_ord == Ordering::Less),
413                    "double ordering mismatch: prev={prev_v}, curr={v}"
414                );
415            }
416            prev = Some((key, *v));
417        }
418    }
419
420    fn assert_monotonic_text(values: Vec<&str>) {
421        let mut sorted = values;
422        sorted.sort();
423        let mut prev: Option<(Vec<u8>, &str)> = None;
424        for (i, v) in sorted.iter().enumerate() {
425            let key =
426                KeyEncoder::index_key(1, &SqlValue::Text((*v).to_string()), i as u64).unwrap();
427            if let Some((prev_key, prev_v)) = prev {
428                let ordering = prev_v.cmp(v);
429                let key_ord = prev_key.cmp(&key);
430                assert!(
431                    ordering == key_ord
432                        || (ordering == Ordering::Equal && key_ord == Ordering::Less),
433                    "text ordering mismatch: prev={prev_v}, curr={v}"
434                );
435            }
436            prev = Some((key, *v));
437        }
438    }
439
440    fn assert_monotonic_blob(values: Vec<Vec<u8>>) {
441        let mut sorted = values;
442        sorted.sort_by(|a, b| match a.len().cmp(&b.len()) {
443            Ordering::Equal => a.cmp(b),
444            other => other,
445        });
446        let mut prev: Option<(Vec<u8>, Vec<u8>)> = None;
447        for (i, v) in sorted.iter().enumerate() {
448            let key = KeyEncoder::index_key(1, &SqlValue::Blob(v.clone()), i as u64).unwrap();
449            if let Some((prev_key, prev_v)) = prev {
450                let ordering = match prev_v.len().cmp(&v.len()) {
451                    Ordering::Equal => prev_v.cmp(v),
452                    other => other,
453                };
454                let key_ord = prev_key.cmp(&key);
455                assert!(
456                    ordering == key_ord
457                        || (ordering == Ordering::Equal && key_ord == Ordering::Less),
458                    "blob ordering mismatch: prev={prev_v:?}, curr={v:?}"
459                );
460            }
461            prev = Some((key, v.clone()));
462        }
463    }
464
465    fn assert_monotonic_bool() {
466        let values = [false, true];
467        let mut prev: Option<(Vec<u8>, bool)> = None;
468        for (i, v) in values.iter().enumerate() {
469            let key = KeyEncoder::index_key(1, &SqlValue::Boolean(*v), i as u64).unwrap();
470            if let Some((prev_key, prev_v)) = prev {
471                let ordering = prev_v.cmp(v);
472                let key_ord = prev_key.cmp(&key);
473                assert_eq!(ordering, key_ord);
474            }
475            prev = Some((key, *v));
476        }
477    }
478
479    fn assert_monotonic_timestamp(values: Vec<i64>) {
480        let mut sorted = values;
481        sorted.sort();
482        let mut prev: Option<(Vec<u8>, i64)> = None;
483        for (i, v) in sorted.iter().enumerate() {
484            let key = KeyEncoder::index_key(1, &SqlValue::Timestamp(*v), i as u64).unwrap();
485            if let Some((prev_key, prev_v)) = prev {
486                let ordering = prev_v.cmp(v);
487                let key_ord = prev_key.cmp(&key);
488                assert!(
489                    ordering == key_ord
490                        || (ordering == Ordering::Equal && key_ord == Ordering::Less),
491                    "timestamp ordering mismatch: prev={prev_v}, curr={v}"
492                );
493            }
494            prev = Some((key, *v));
495        }
496    }
497
498    proptest! {
499        #[test]
500        fn prop_integer_order_matches_encoded(a in any::<i32>(), b in any::<i32>()) {
501            let va = SqlValue::Integer(a);
502            let vb = SqlValue::Integer(b);
503            let ka = KeyEncoder::index_key(1, &va, 0).unwrap();
504            let kb = KeyEncoder::index_key(1, &vb, 1).unwrap();
505            let ord = a.cmp(&b);
506            let kord = ka.cmp(&kb);
507            prop_assert!(ord == kord || (ord == Ordering::Equal && kord == Ordering::Less));
508        }
509
510        #[test]
511        fn prop_bigint_order_matches_encoded(a in any::<i64>(), b in any::<i64>()) {
512            let va = SqlValue::BigInt(a);
513            let vb = SqlValue::BigInt(b);
514            let ka = KeyEncoder::index_key(1, &va, 0).unwrap();
515            let kb = KeyEncoder::index_key(1, &vb, 1).unwrap();
516            let ord = a.cmp(&b);
517            let kord = ka.cmp(&kb);
518            prop_assert!(ord == kord || (ord == Ordering::Equal && kord == Ordering::Less));
519        }
520
521        #[test]
522        fn prop_float_order_matches_encoded(a in any::<f32>(), b in any::<f32>()) {
523            let va = SqlValue::Float(a);
524            let vb = SqlValue::Float(b);
525            let ka = KeyEncoder::index_key(1, &va, 0).unwrap();
526            let kb = KeyEncoder::index_key(1, &vb, 1).unwrap();
527            let ord = a.total_cmp(&b);
528            let kord = ka.cmp(&kb);
529            prop_assert!(ord == kord || (ord == Ordering::Equal && kord == Ordering::Less));
530        }
531
532        #[test]
533        fn prop_double_order_matches_encoded(a in any::<f64>(), b in any::<f64>()) {
534            let va = SqlValue::Double(a);
535            let vb = SqlValue::Double(b);
536            let ka = KeyEncoder::index_key(1, &va, 0).unwrap();
537            let kb = KeyEncoder::index_key(1, &vb, 1).unwrap();
538            let ord = a.total_cmp(&b);
539            let kord = ka.cmp(&kb);
540            prop_assert!(ord == kord || (ord == Ordering::Equal && kord == Ordering::Less));
541        }
542
543        #[test]
544        fn prop_text_order_matches_encoded(a in r"[^\x00]*", b in r"[^\x00]*") {
545            let va = SqlValue::Text(a.clone());
546            let vb = SqlValue::Text(b.clone());
547            let ka = KeyEncoder::index_key(1, &va, 0).unwrap();
548            let kb = KeyEncoder::index_key(1, &vb, 1).unwrap();
549            let ord = a.cmp(&b);
550            let kord = ka.cmp(&kb);
551            prop_assert!(ord == kord || (ord == Ordering::Equal && kord == Ordering::Less));
552        }
553
554        #[test]
555        fn prop_blob_order_matches_encoded(a in proptest::collection::vec(any::<u8>(), 0..32), b in proptest::collection::vec(any::<u8>(), 0..32)) {
556            let va = SqlValue::Blob(a.clone());
557            let vb = SqlValue::Blob(b.clone());
558            let ka = KeyEncoder::index_key(1, &va, 0).unwrap();
559            let kb = KeyEncoder::index_key(1, &vb, 1).unwrap();
560            let ord = match a.len().cmp(&b.len()) {
561                Ordering::Equal => a.cmp(&b),
562                other => other,
563            };
564            let kord = ka.cmp(&kb);
565            prop_assert!(ord == kord || (ord == Ordering::Equal && kord == Ordering::Less));
566        }
567    }
568}
alopex_sql/storage/key.rs

alopex_sql/storage/
key.rs
