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        SqlValue::Date(v) => {
151            buf.push(0x0a);
152            buf.extend_from_slice(&((*v as u32) ^ 0x8000_0000).to_be_bytes());
153        }
154        SqlValue::Time(v) => {
155            buf.push(0x0b);
156            buf.extend_from_slice(&((*v as u64) ^ 0x8000_0000_0000_0000).to_be_bytes());
157        }
158        SqlValue::Interval { .. } => {
159            return Err(StorageError::TypeMismatch {
160                expected: "indexable scalar type".into(),
161                actual: "Interval".into(),
162            });
163        }
164        SqlValue::Decimal(_) => {
165            return Err(StorageError::TypeMismatch {
166                expected: "indexable scalar type".into(),
167                actual: "Decimal".into(),
168            });
169        }
170        SqlValue::Json(_) => {
171            return Err(StorageError::TypeMismatch {
172                expected: "indexable scalar type".into(),
173                actual: "Json".into(),
174            });
175        }
176        SqlValue::Array(_) | SqlValue::Map(_) | SqlValue::Struct(_) => {
177            return Err(StorageError::TypeMismatch {
178                expected: "indexable scalar type".into(),
179                actual: value.type_name().into(),
180            });
181        }
182    }
183    Ok(())
184}
185
186fn encode_ordered_f32(v: f32) -> u32 {
187    let bits = v.to_bits();
188    if bits & 0x8000_0000 != 0 {
189        !bits
190    } else {
191        bits ^ 0x8000_0000
192    }
193}
194
195fn encode_ordered_f64(v: f64) -> u64 {
196    let bits = v.to_bits();
197    if bits & 0x8000_0000_0000_0000 != 0 {
198        !bits
199    } else {
200        bits ^ 0x8000_0000_0000_0000
201    }
202}
203
204#[cfg(test)]
205mod tests {
206    use super::*;
207    use proptest::prelude::*;
208    use std::cmp::Ordering;
209
210    #[test]
211    fn row_key_roundtrip() {
212        let key = KeyEncoder::row_key(10, 42);
213        assert_eq!(key.len(), 13);
214        let (t, r) = KeyEncoder::decode_row_key(&key).unwrap();
215        assert_eq!((t, r), (10, 42));
216    }
217
218    #[test]
219    fn table_prefix_matches_row_key_prefix() {
220        let prefix = KeyEncoder::table_prefix(7);
221        let key = KeyEncoder::row_key(7, 1);
222        assert!(key.starts_with(&prefix));
223    }
224
225    #[test]
226    fn sql_row_keys_share_the_core_canonical_interval_contract() {
227        use alopex_core::{CanonicalRowKey, RowKeyRange};
228
229        let range = RowKeyRange::new(7, Some(10), Some(20)).unwrap();
230        let encoded = range.encoded_bounds();
231
232        assert_eq!(encoded.lower_inclusive, KeyEncoder::row_key(7, 10));
233        assert_eq!(encoded.upper_exclusive, KeyEncoder::row_key(7, 20));
234        assert!(range.contains(CanonicalRowKey::decode(&KeyEncoder::row_key(7, 19)).unwrap()));
235        assert!(!range.contains(CanonicalRowKey::decode(&KeyEncoder::row_key(7, 20)).unwrap()));
236    }
237
238    #[test]
239    fn secondary_index_hits_are_rechecked_against_the_primary_row_key_range() {
240        use alopex_core::{CanonicalRowKey, RowKeyRange};
241
242        let range = RowKeyRange::new(7, Some(10), Some(20)).unwrap();
243        let resolved_index_hits = [
244            CanonicalRowKey::decode(&KeyEncoder::row_key(7, 19)).unwrap(),
245            CanonicalRowKey::decode(&KeyEncoder::row_key(7, 20)).unwrap(),
246            CanonicalRowKey::decode(&KeyEncoder::row_key(8, 19)).unwrap(),
247        ];
248
249        let accepted = resolved_index_hits
250            .into_iter()
251            .filter(|row_key| range.contains(*row_key))
252            .collect::<Vec<_>>();
253
254        assert_eq!(accepted, vec![CanonicalRowKey::new(7, 19)]);
255    }
256
257    #[test]
258    fn encoded_primary_key_range_recheck_rejects_wrong_table_and_upper_bound() {
259        use alopex_core::RowKeyRange;
260
261        let range = RowKeyRange::new(7, Some(10), Some(20)).unwrap();
262        assert!(KeyEncoder::primary_key_is_in_range(&KeyEncoder::row_key(7, 19), range).unwrap());
263        assert!(!KeyEncoder::primary_key_is_in_range(&KeyEncoder::row_key(7, 20), range).unwrap());
264        assert!(!KeyEncoder::primary_key_is_in_range(&KeyEncoder::row_key(8, 19), range).unwrap());
265    }
266
267    #[test]
268    fn index_prefix_matches_index_key_prefix() {
269        let prefix = KeyEncoder::index_prefix(5);
270        let key = KeyEncoder::index_key(5, &SqlValue::Integer(1), 99).unwrap();
271        assert!(key.starts_with(&prefix));
272    }
273
274    #[test]
275    fn integer_ordering_matches_lexicographic() {
276        assert_monotonic_ints((-128..=127).collect());
277    }
278
279    #[test]
280    fn bigint_ordering_matches_lexicographic() {
281        assert_monotonic_i64(vec![i64::MIN, -10, -1, 0, 1, 2, 100, i64::MAX]);
282    }
283
284    #[test]
285    fn float_ordering_matches_lexicographic_with_specials() {
286        let values = vec![
287            -f32::INFINITY,
288            -1.5,
289            -0.0,
290            0.0,
291            0.5,
292            f32::INFINITY,
293            f32::NAN,
294        ];
295        assert_monotonic_f32(values);
296    }
297
298    #[test]
299    fn double_ordering_matches_lexicographic_with_specials() {
300        let values = vec![
301            -f64::INFINITY,
302            -123.456,
303            -0.0,
304            0.0,
305            1.2345,
306            f64::INFINITY,
307            f64::NAN,
308        ];
309        assert_monotonic_f64(values);
310    }
311
312    #[test]
313    fn text_ordering_handles_ascii_and_multibyte() {
314        let values = vec!["", "a", "aa", "b", "é", "あ", "あい", "🍣"];
315        assert_monotonic_text(values);
316    }
317
318    #[test]
319    fn blob_ordering_respects_length_then_bytes() {
320        let values = vec![
321            vec![],
322            vec![0x00],
323            vec![0x00, 0x01],
324            vec![0x01],
325            vec![0x01, 0x00],
326            vec![0xFF],
327        ];
328        assert_monotonic_blob(values);
329    }
330
331    #[test]
332    fn boolean_ordering() {
333        assert_monotonic_bool();
334    }
335
336    #[test]
337    fn vector_is_rejected_for_index_key() {
338        let err = KeyEncoder::index_key(1, &SqlValue::Vector(vec![1.0, 2.0]), 0).unwrap_err();
339        match err {
340            StorageError::TypeMismatch { actual, .. } => {
341                assert_eq!(actual, "Vector");
342            }
343            other => panic!("expected TypeMismatch for Vector, got {other:?}"),
344        }
345    }
346
347    #[test]
348    fn timestamp_ordering() {
349        let values = vec![-5, -1, 0, 1, 10, i64::MAX];
350        assert_monotonic_timestamp(values);
351    }
352
353    #[test]
354    fn composite_key_maintains_lexicographic_tuple_order() {
355        let mut tuples = [(0, 0), (0, 1), (1, 0), (1, 2), (2, 0), (2, 2)].to_vec();
356        tuples.sort();
357
358        let mut prev: Option<Vec<u8>> = None;
359        for (i, (a, b)) in tuples.iter().enumerate() {
360            let key = KeyEncoder::composite_index_key(
361                9,
362                &[SqlValue::Integer(*a), SqlValue::Integer(*b)],
363                i as u64,
364            )
365            .unwrap();
366            if let Some(p) = prev {
367                assert!(
368                    p < key,
369                    "composite key ordering violated for ({a},{b}) at position {i}"
370                );
371            }
372            prev = Some(key);
373        }
374    }
375
376    fn assert_monotonic_ints(values: Vec<i32>) {
377        let mut sorted = values;
378        sorted.sort();
379        let mut prev: Option<(Vec<u8>, i32)> = None;
380        for (i, v) in sorted.iter().enumerate() {
381            let key = KeyEncoder::index_key(1, &SqlValue::Integer(*v), i as u64).unwrap();
382            if let Some((prev_key, prev_v)) = prev {
383                let ordering = prev_v.cmp(v);
384                let key_ord = prev_key.cmp(&key);
385                assert!(
386                    ordering == key_ord
387                        || (ordering == Ordering::Equal && key_ord == Ordering::Less),
388                    "integer ordering mismatch: prev={prev_v}, curr={v}"
389                );
390            }
391            prev = Some((key, *v));
392        }
393    }
394
395    fn assert_monotonic_i64(values: Vec<i64>) {
396        let mut sorted = values;
397        sorted.sort();
398        let mut prev: Option<(Vec<u8>, i64)> = None;
399        for (i, v) in sorted.iter().enumerate() {
400            let key = KeyEncoder::index_key(1, &SqlValue::BigInt(*v), i as u64).unwrap();
401            if let Some((prev_key, prev_v)) = prev {
402                let ordering = prev_v.cmp(v);
403                let key_ord = prev_key.cmp(&key);
404                assert!(
405                    ordering == key_ord
406                        || (ordering == Ordering::Equal && key_ord == Ordering::Less),
407                    "bigint ordering mismatch: prev={prev_v}, curr={v}"
408                );
409            }
410            prev = Some((key, *v));
411        }
412    }
413
414    fn assert_monotonic_f32(values: Vec<f32>) {
415        let mut sorted = values;
416        sorted.sort_by(|a, b| a.total_cmp(b));
417        let mut prev: Option<(Vec<u8>, f32)> = None;
418        for (i, v) in sorted.iter().enumerate() {
419            let key = KeyEncoder::index_key(1, &SqlValue::Float(*v), i as u64).unwrap();
420            if let Some((prev_key, prev_v)) = prev {
421                let ordering = prev_v.total_cmp(v);
422                let key_ord = prev_key.cmp(&key);
423                assert!(
424                    ordering == key_ord
425                        || (ordering == Ordering::Equal && key_ord == Ordering::Less),
426                    "float ordering mismatch: prev={prev_v}, curr={v}"
427                );
428            }
429            prev = Some((key, *v));
430        }
431    }
432
433    fn assert_monotonic_f64(values: Vec<f64>) {
434        let mut sorted = values;
435        sorted.sort_by(|a, b| a.total_cmp(b));
436        let mut prev: Option<(Vec<u8>, f64)> = None;
437        for (i, v) in sorted.iter().enumerate() {
438            let key = KeyEncoder::index_key(1, &SqlValue::Double(*v), i as u64).unwrap();
439            if let Some((prev_key, prev_v)) = prev {
440                let ordering = prev_v.total_cmp(v);
441                let key_ord = prev_key.cmp(&key);
442                assert!(
443                    ordering == key_ord
444                        || (ordering == Ordering::Equal && key_ord == Ordering::Less),
445                    "double ordering mismatch: prev={prev_v}, curr={v}"
446                );
447            }
448            prev = Some((key, *v));
449        }
450    }
451
452    fn assert_monotonic_text(values: Vec<&str>) {
453        let mut sorted = values;
454        sorted.sort();
455        let mut prev: Option<(Vec<u8>, &str)> = None;
456        for (i, v) in sorted.iter().enumerate() {
457            let key =
458                KeyEncoder::index_key(1, &SqlValue::Text((*v).to_string()), i as u64).unwrap();
459            if let Some((prev_key, prev_v)) = prev {
460                let ordering = prev_v.cmp(v);
461                let key_ord = prev_key.cmp(&key);
462                assert!(
463                    ordering == key_ord
464                        || (ordering == Ordering::Equal && key_ord == Ordering::Less),
465                    "text ordering mismatch: prev={prev_v}, curr={v}"
466                );
467            }
468            prev = Some((key, *v));
469        }
470    }
471
472    fn assert_monotonic_blob(values: Vec<Vec<u8>>) {
473        let mut sorted = values;
474        sorted.sort_by(|a, b| match a.len().cmp(&b.len()) {
475            Ordering::Equal => a.cmp(b),
476            other => other,
477        });
478        let mut prev: Option<(Vec<u8>, Vec<u8>)> = None;
479        for (i, v) in sorted.iter().enumerate() {
480            let key = KeyEncoder::index_key(1, &SqlValue::Blob(v.clone()), i as u64).unwrap();
481            if let Some((prev_key, prev_v)) = prev {
482                let ordering = match prev_v.len().cmp(&v.len()) {
483                    Ordering::Equal => prev_v.cmp(v),
484                    other => other,
485                };
486                let key_ord = prev_key.cmp(&key);
487                assert!(
488                    ordering == key_ord
489                        || (ordering == Ordering::Equal && key_ord == Ordering::Less),
490                    "blob ordering mismatch: prev={prev_v:?}, curr={v:?}"
491                );
492            }
493            prev = Some((key, v.clone()));
494        }
495    }
496
497    fn assert_monotonic_bool() {
498        let values = [false, true];
499        let mut prev: Option<(Vec<u8>, bool)> = None;
500        for (i, v) in values.iter().enumerate() {
501            let key = KeyEncoder::index_key(1, &SqlValue::Boolean(*v), i as u64).unwrap();
502            if let Some((prev_key, prev_v)) = prev {
503                let ordering = prev_v.cmp(v);
504                let key_ord = prev_key.cmp(&key);
505                assert_eq!(ordering, key_ord);
506            }
507            prev = Some((key, *v));
508        }
509    }
510
511    fn assert_monotonic_timestamp(values: Vec<i64>) {
512        let mut sorted = values;
513        sorted.sort();
514        let mut prev: Option<(Vec<u8>, i64)> = None;
515        for (i, v) in sorted.iter().enumerate() {
516            let key = KeyEncoder::index_key(1, &SqlValue::Timestamp(*v), i as u64).unwrap();
517            if let Some((prev_key, prev_v)) = prev {
518                let ordering = prev_v.cmp(v);
519                let key_ord = prev_key.cmp(&key);
520                assert!(
521                    ordering == key_ord
522                        || (ordering == Ordering::Equal && key_ord == Ordering::Less),
523                    "timestamp ordering mismatch: prev={prev_v}, curr={v}"
524                );
525            }
526            prev = Some((key, *v));
527        }
528    }
529
530    proptest! {
531        #[test]
532        fn prop_integer_order_matches_encoded(a in any::<i32>(), b in any::<i32>()) {
533            let va = SqlValue::Integer(a);
534            let vb = SqlValue::Integer(b);
535            let ka = KeyEncoder::index_key(1, &va, 0).unwrap();
536            let kb = KeyEncoder::index_key(1, &vb, 1).unwrap();
537            let ord = a.cmp(&b);
538            let kord = ka.cmp(&kb);
539            prop_assert!(ord == kord || (ord == Ordering::Equal && kord == Ordering::Less));
540        }
541
542        #[test]
543        fn prop_bigint_order_matches_encoded(a in any::<i64>(), b in any::<i64>()) {
544            let va = SqlValue::BigInt(a);
545            let vb = SqlValue::BigInt(b);
546            let ka = KeyEncoder::index_key(1, &va, 0).unwrap();
547            let kb = KeyEncoder::index_key(1, &vb, 1).unwrap();
548            let ord = a.cmp(&b);
549            let kord = ka.cmp(&kb);
550            prop_assert!(ord == kord || (ord == Ordering::Equal && kord == Ordering::Less));
551        }
552
553        #[test]
554        fn prop_float_order_matches_encoded(a in any::<f32>(), b in any::<f32>()) {
555            let va = SqlValue::Float(a);
556            let vb = SqlValue::Float(b);
557            let ka = KeyEncoder::index_key(1, &va, 0).unwrap();
558            let kb = KeyEncoder::index_key(1, &vb, 1).unwrap();
559            let ord = a.total_cmp(&b);
560            let kord = ka.cmp(&kb);
561            prop_assert!(ord == kord || (ord == Ordering::Equal && kord == Ordering::Less));
562        }
563
564        #[test]
565        fn prop_double_order_matches_encoded(a in any::<f64>(), b in any::<f64>()) {
566            let va = SqlValue::Double(a);
567            let vb = SqlValue::Double(b);
568            let ka = KeyEncoder::index_key(1, &va, 0).unwrap();
569            let kb = KeyEncoder::index_key(1, &vb, 1).unwrap();
570            let ord = a.total_cmp(&b);
571            let kord = ka.cmp(&kb);
572            prop_assert!(ord == kord || (ord == Ordering::Equal && kord == Ordering::Less));
573        }
574
575        #[test]
576        fn prop_text_order_matches_encoded(a in r"[^\x00]*", b in r"[^\x00]*") {
577            let va = SqlValue::Text(a.clone());
578            let vb = SqlValue::Text(b.clone());
579            let ka = KeyEncoder::index_key(1, &va, 0).unwrap();
580            let kb = KeyEncoder::index_key(1, &vb, 1).unwrap();
581            let ord = a.cmp(&b);
582            let kord = ka.cmp(&kb);
583            prop_assert!(ord == kord || (ord == Ordering::Equal && kord == Ordering::Less));
584        }
585
586        #[test]
587        fn prop_blob_order_matches_encoded(a in proptest::collection::vec(any::<u8>(), 0..32), b in proptest::collection::vec(any::<u8>(), 0..32)) {
588            let va = SqlValue::Blob(a.clone());
589            let vb = SqlValue::Blob(b.clone());
590            let ka = KeyEncoder::index_key(1, &va, 0).unwrap();
591            let kb = KeyEncoder::index_key(1, &vb, 1).unwrap();
592            let ord = match a.len().cmp(&b.len()) {
593                Ordering::Equal => a.cmp(&b),
594                other => other,
595            };
596            let kord = ka.cmp(&kb);
597            prop_assert!(ord == kord || (ord == Ordering::Equal && kord == Ordering::Less));
598        }
599    }
600}
alopex_sql/storage/key.rs

alopex_sql/storage/
key.rs
