Repository: dbpunk-labs/db3 (language: rust)

Issue:
WIP: Propose index encode solution
## Motivations

<!--
If your feature request is related to a problem, please describe it.
-->

- Would you like to implement this feature? [y/n]


### Goal

- index key encode into/decode from bytes
- index bytes can be sorted
- index bytes order should be consistent with the original value order
- support Null encode
- support Emptry String encode
- define the order between types. Reference: https://www.mongodb.com/docs/manual/reference/bson-type-comparison-order/
- consider encode/decode performance and memory usage

### Reference
https://www.mongodb.com/docs/manual/reference/bson-type-comparison-order/

### Context

We currently support simple document index to converge the very basic use case. e.g (String index, Int64, Int32, Boolean)

In this issue, we aim to expand our support to include additional features such as Null value, empty String, null String, multi-index scenario, etc"

With respect to that, we need to review our index mechanism and then improve or redesign it if necessary.

## Solution

<!-- Describe the solution you'd like. -->

## Alternatives

<!-- Describe any alternative solutions or features you've considered. -->

## Additional context

<!-- Add any other context or screenshots about the feature request here. -->



Discussion / hints:
@jingchen2222  Has this issue been resolved?
not yep

On Fri, Apr 14, 2023 at 8:42 PM imotai ***@***.***> wrote:

> @jingchen2222 <https://github.com/jingchen2222> Has this issue been
> resolved?
>
> —
> Reply to this email directly, view it on GitHub
> <https://github.com/dbpunk-labs/db3/issues/321#issuecomment-1509488788>,
> or unsubscribe
> <https://github.com/notifications/unsubscribe-auth/ABP75ZND4PAPBGYD55DHFO3XBIKIRANCNFSM6AAAAAAU764KGA>
> .
> You are receiving this because you were mentioned.Message ID:
> ***@***.***>
>

> not yep
> […](#)
> On Fri, Apr 14, 2023 at 8:42 PM imotai ***@***.***> wrote: @jingchen2222 <https://github.com/jingchen2222> Has this issue been resolved? — Reply to this email directly, view it on GitHub <[#321 (comment)](https://github.com/dbpunk-labs/db3/issues/321#issuecomment-1509488788)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABP75ZND4PAPBGYD55DHFO3XBIKIRANCNFSM6AAAAAAU764KGA> . You are receiving this because you were mentioned.Message ID: ***@***.***>

We just solved the key order problem
### Index



| TYPE_ID | collection_id | index_field_id | fields_key  | document_id |
| ------- | ------------- | -------------- | ---- | ----------- |
|         |               |                |      |             |



#### fields_key

|FIELD1|FIELD2|...|FIELDN

#### FIELD

| FIELD_TYPE_ID                                                | FIELD_DATA |
| ------------------------------------------------------------ | ---------- |
| NullType, BoolType, I32Type, I64Type, F32Type, F64Type, DataTimeType, StringType | 



### TODO list

- [x] Add FieldKey as part of IndexId, implement a set of method for encode and decode fieldkey
- [x] Support Null and empty string
- [x] add unit test for single field key and multi fields keys including empty string and null


TODO:
replace the key encode&decode with storekey to cover more use cases https://github.com/surrealdb/storekey

Fix patch:
diff --git a/src/crypto/Cargo.toml b/src/crypto/Cargo.toml
index c1c91ce1..53c6aa83 100644
--- a/src/crypto/Cargo.toml
+++ b/src/crypto/Cargo.toml
@@ -26,8 +26,6 @@ schemars ="0.8.10"
 serde = { version = "1.0.144", features = ["derive"] }
 serde-name = "0.2.1"
 thiserror = "1.0.34"
-#serde_bytes = "0.11.7"
-#serde_json = "1.0.88"
 bson = "2.5.0"
 serde_json = { version = "1.0.64", default-features = false }
 serde_with = "2.1.0"
@@ -43,5 +41,8 @@ rust_secp256k1 = { version = "0.24.0", package = "secp256k1", features = ["bitco
 bip32 = "0.5.0"
 ethers = { workspace = true }
 chrono = "0.4.22"
+storekey = "0.5.0"
+enum-primitive-derive = "^0.2"
+num-traits = "^0.2"
 [dev-dependencies]
 tiny-bip39 = "1.0.0"
\ No newline at end of file
diff --git a/src/crypto/src/id.rs b/src/crypto/src/id.rs
index 524bc6ee..622dd056 100644
--- a/src/crypto/src/id.rs
+++ b/src/crypto/src/id.rs
@@ -21,11 +21,15 @@ use bson::Bson;
 use byteorder::{BigEndian, ReadBytesExt, WriteBytesExt};
 use bytes::Buf;
 use db3_error::{DB3Error, Result};
+use enum_primitive_derive::Primitive;
 use fastcrypto::hash::{HashFunction, Sha3_256};
+use num_traits::FromPrimitive;
 use rust_secp256k1::hashes::{sha256, Hash};
 use rust_secp256k1::ThirtyTwoByteHash;
+use serde::Serialize;
 use std::fmt;
 use std::io::Cursor;
+use storekey;
 
 // it's ethereum compatiable account id
 #[derive(Eq, Default, PartialEq, Ord, PartialOrd, Copy, Clone)]
@@ -323,130 +327,67 @@ impl fmt::Display for DocumentId {
         write!(f, "DOC|{}|{}", collection_id, document_entry_id)
     }
 }
+#[derive(Debug, Clone, Primitive, PartialEq)]
 pub enum FieldTypeId {
-    Null = 0x01,
-    Bool = 0x02,
-    I32 = 0x03,
-    I64 = 0x04,
-    F32 = 0x05,
-    F64 = 0x06,
-    DateTime = 0x07,
-    String = 0x0a,
+    Null = 1,
+    Bool = 10,
+    I32 = 20,
+    I64 = 21,
+    F32 = 22,
+    F64 = 23,
+    DateTime = 30,
+    String = 40,
 }
 #[derive(Eq, Default, PartialEq, Ord, PartialOrd, Clone, Debug)]
 pub struct FieldKey {
     data: Vec<u8>,
 }
 impl FieldKey {
-    fn encode_i32(input: i32) -> u32 {
-        match input < 0 {
-            true => {
-                if input == i32::MIN {
-                    0
-                } else {
-                    let new_input = input as u32;
-                    (new_input & 0x7fffffff) as u32
-                }
-            }
-            false => {
-                let new_input = input as u32;
-                (new_input | 0x80000000) as u32
-            }
-        }
-    }
-    fn decode_u32(input: u32) -> i32 {
-        if input == 0 {
-            i32::MIN
-        } else {
-            if input as i32 > 0 {
-                (input | 0x80000000) as i32
-            } else {
-                (input & 0x7fffffff) as i32
-            }
-        }
+    fn add_field_type(&mut self, field_type: FieldTypeId) {
+        self.data.push(field_type as u8);
     }
 
-    fn encode_i64(input: i64) -> u64 {
-        match input < 0 {
-            true => {
-                if input == i64::MIN {
-                    0
-                } else {
-                    let new_input = input as u64;
-                    (new_input & 0x7fffffffffffffff) as u64
-                }
-            }
-            false => {
-                let new_input = input as u64;
-                (new_input | 0x8000000000000000) as u64
-            }
-        }
-    }
-    fn decode_u64(input: u64) -> i64 {
-        if input == 0 {
-            i64::MIN
-        } else {
-            if input as i64 > 0 {
-                (input | 0x8000000000000000) as i64
-            } else {
-                (input & 0x7fffffffffffffff) as i64
-            }
-        }
+    fn add_encode_field<T>(&mut self, v: &T) -> std::result::Result<(), DB3Error>
+    where
+        T: Serialize + ?Sized,
+    {
+        let buf =
+            storekey::serialize(v).map_err(|e| DB3Error::DocumentDecodeError(format!("{e}")))?;
+        self.data.extend_from_slice(buf.as_ref());
+        Ok(())
     }
-
-    fn add(&mut self, field: &Option<Bson>) -> std::result::Result<(), DB3Error> {
+    fn add_field(&mut self, field: &Option<Bson>) -> std::result::Result<(), DB3Error> {
         match field {
             None => {
-                self.data
-                    .write_u8(FieldTypeId::Null as u8)
-                    .map_err(|e| DB3Error::DocumentDecodeError(format!("{e}")))?;
+                self.add_field_type(FieldTypeId::Null);
             }
 
             Some(Bson::Boolean(b)) => {
-                self.data
-                    .write_u8(FieldTypeId::Bool as u8)
-                    .map_err(|e| DB3Error::DocumentDecodeError(format!("{e}")))?;
-                self.data
-                    .write_u8(*b as u8)
-                    .map_err(|e| DB3Error::DocumentDecodeError(format!("{e}")))?;
+                self.add_field_type(FieldTypeId::Bool);
+                self.add_encode_field(b)?;
             }
             Some(Bson::Int64(n)) => {
-                self.data
-                    .write_u8(FieldTypeId::I64 as u8)
-                    .map_err(|e| DB3Error::DocumentDecodeError(format!("{e}")))?;
-                self.data
-                    .write_u64::<BigEndian>(Self::encode_i64(*n))
-                    .map_err(|e| DB3Error::DocumentDecodeError(format!("{e}")))?;
+                self.add_field_type(FieldTypeId::I64);
+                self.add_encode_field(n)?;
             }
             Some(Bson::Int32(n)) => {
-                self.data
-                    .write_u8(FieldTypeId::I32 as u8)
-                    .map_err(|e| DB3Error::DocumentDecodeError(format!("{e}")))?;
-                self.data
-                    .write_u32::<BigEndian>(Self::encode_i32(*n))
-                    .map_err(|e| DB3Error::DocumentDecodeError(format!("{e}")))?;
+                self.add_field_type(FieldTypeId::I32);
+                self.add_encode_field(n)?;
             }
             // TODO: add \0 as the end of string.
             Some(Bson::String(s)) => {
-                self.data
-                    .write_u8(FieldTypeId::String as u8)
-                    .map_err(|e| DB3Error::DocumentDecodeError(format!("{e}")))?;
-                self.data.extend_from_slice(s.as_bytes());
-                self.data.extend_from_slice(&[0]);
+                self.add_field_type(FieldTypeId::String);
+                self.add_encode_field(&s)?;
             }
             Some(Bson::DateTime(dt)) => {
-                self.data
-                    .write_u8(FieldTypeId::DateTime as u8)
-                    .map_err(|e| DB3Error::DocumentDecodeError(format!("{e}")))?;
-                let value: u64 = Self::encode_i64(dt.timestamp_millis());
-                self.data
-                    .write_u64::<BigEndian>(value)
-                    .map_err(|e| DB3Error::DocumentDecodeError(format!("{e}")))?;
+                self.add_field_type(FieldTypeId::DateTime);
+                self.add_encode_field(&dt.timestamp_millis())?;
             }
-            _ => {
-                return Err(DB3Error::DocumentDecodeError(
-                    "value type is not supported".to_string(),
-                ))
+            Some(v) => {
+                return Err(DB3Error::DocumentDecodeError(format!(
+                    "field type {:?} is not supported",
+                    v.element_type()
+                )))
             }
         }
         Ok(())
@@ -464,7 +405,7 @@ impl FieldKey {
             )));
         }
         for field in fields {
-            key.add(&field)?;
+            key.add_field(&field)?;
         }
         Ok(key)
     }
@@ -474,54 +415,43 @@ impl FieldKey {
     fn read_next_field(
         cursor: &mut Cursor<Vec<u8>>,
     ) -> std::result::Result<Option<Bson>, DB3Error> {
-        let field_type = cursor
+        let field_id = cursor
             .read_u8()
             .map_err(|e| DB3Error::DocumentDecodeError(format!("{e}")))?;
+
+        let field_type = FieldTypeId::from_u8(field_id)
+            .ok_or_else(|| DB3Error::DocumentDecodeError(format!("field type is not supported")))?;
         match field_type {
-            0x01 => Ok(None),
-            0x02 => {
-                let value = cursor
-                    .read_u8()
+            FieldTypeId::Null => Ok(None),
+            FieldTypeId::Bool => {
+                let b: bool = storekey::deserialize(cursor.remaining_slice())
                     .map_err(|e| DB3Error::DocumentDecodeError(format!("{e}")))?;
-                Ok(Some(Bson::Boolean(value != 0)))
+                cursor.advance(1);
+                Ok(Some(Bson::Boolean(b)))
             }
-            0x03 => {
-                let value = cursor
-                    .read_u32::<BigEndian>()
+            FieldTypeId::I32 => {
+                let n: i32 = storekey::deserialize(cursor.remaining_slice())
                     .map_err(|e| DB3Error::DocumentDecodeError(format!("{e}")))?;
-                Ok(Some(Bson::Int32(Self::decode_u32(value))))
+                cursor.advance(4);
+                Ok(Some(Bson::Int32(n)))
             }
-            0x04 => {
-                let value = cursor
-                    .read_u64::<BigEndian>()
+            FieldTypeId::I64 => {
+                let n: i64 = storekey::deserialize(cursor.remaining_slice())
                     .map_err(|e| DB3Error::DocumentDecodeError(format!("{e}")))?;
-                Ok(Some(Bson::Int64(Self::decode_u64(value))))
+                cursor.advance(8);
+                Ok(Some(Bson::Int64(n)))
             }
-            0x07 => {
-                let value = cursor
-                    .read_u64::<BigEndian>()
+            FieldTypeId::DateTime => {
+                let n: i64 = storekey::deserialize(cursor.remaining_slice())
                     .map_err(|e| DB3Error::DocumentDecodeError(format!("{e}")))?;
-                Ok(Some(Bson::DateTime(bson::DateTime::from_millis(
-                    Self::decode_u64(value),
-                ))))
+                cursor.advance(8);
+                Ok(Some(Bson::DateTime(bson::DateTime::from_millis(n))))
             }
-            0x0a => {
-                let mut buf = vec![];
-                while cursor.has_remaining() {
-                    let c = cursor
-                        .read_u8()
-                        .map_err(|e| DB3Error::DocumentDecodeError(format!("{e}")))?;
-                    if c == 0 {
-                        let value = String::from_utf8(buf)
-                            .map_err(|e| DB3Error::DocumentDecodeError(format!("{e}")))?;
-                        return Ok(Some(Bson::String(value)));
-                    }
-                    buf.push(c);
-                }
-
-                Err(DB3Error::DocumentDecodeError(
-                    "string field is not terminated by \0".to_string(),
-                ))
+            FieldTypeId::String => {
+                let s: String = storekey::deserialize(cursor.remaining_slice())
+                    .map_err(|e| DB3Error::DocumentDecodeError(format!("{e}")))?;
+                cursor.advance(s.len() + 1);
+                Ok(Some(Bson::String(s)))
             }
             _ => Err(DB3Error::DocumentDecodeError(
                 "field type is not supported".to_string(),
@@ -988,5 +918,25 @@ mod tests {
         assert_eq!(extract_fields[0], Some(Bson::Int64(10 as i64)));
         assert_eq!(extract_fields[1], Some(Bson::String("".to_string())));
         assert_eq!("10#", format!("{}", key));
+
+        let fields = vec![Some(Bson::Boolean(true)), Some(Bson::Int64(1 as i64))];
+        let key = FieldKey::create(&fields).unwrap();
+        let extract_fields = key.extract_fields().unwrap();
+        assert_eq!(extract_fields[0], Some(Bson::Boolean(true)));
+        assert_eq!(extract_fields[1], Some(Bson::Int64(1 as i64)));
+        assert_eq!("true#1", format!("{}", key));
+    }
+
+    #[test]
+    fn storekey_encode_ut() {
+        let v1: i32 = 1;
+        let serialized = storekey::serialize(&v1).unwrap();
+        let v2: i32 = storekey::deserialize(&serialized).unwrap();
+        assert_eq!(v1, v2);
+
+        let s1 = "abc";
+        let serialized = storekey::serialize(&s1).unwrap();
+        let s2: &str = storekey::deserialize(&serialized).unwrap();
+        assert_eq!(s1, s2);
     }
 }
diff --git a/src/crypto/src/lib.rs b/src/crypto/src/lib.rs
index e1fc48d0..3ba8cdb7 100644
--- a/src/crypto/src/lib.rs
+++ b/src/crypto/src/lib.rs
@@ -1,3 +1,4 @@
+#![feature(cursor_remaining)]
 //
 //
 // lib.rs
@@ -27,3 +28,5 @@ pub mod db3_verifier;
 pub mod id;
 pub mod key_derive;
 pub mod signature_scheme;
+extern crate enum_primitive_derive;
+extern crate num_traits;
diff --git a/src/storage/src/db3_document.rs b/src/storage/src/db3_document.rs
index 008a3db7..eac73f0a 100644
--- a/src/storage/src/db3_document.rs
+++ b/src/storage/src/db3_document.rs
@@ -395,7 +395,7 @@ mod tests {
             fields: vec![index_field],
         };
         if let Ok(Some(keys)) = document.get_keys(&index) {
-            assert_eq!(vec![4, 128, 0, 0, 0, 0, 0, 0, 43], *keys.as_ref());
+            assert_eq!(vec![21, 128, 0, 0, 0, 0, 0, 0, 43], *keys.as_ref());
         } else {
             assert!(false);
         }


Test patch: