indexing but its broken

5 files changed, 121 insertions, 31 deletions

diff --git a/database/src/kv/index.rs b/database/src/kv/index.rs
index 522ae18..23b8349 100644
--- a/database/src/kv/index.rs
+++ b/database/src/kv/index.rs
@@ -4,17 +4,17 @@
     Copyright (C) 2026 metamuffin <metamuffin.org>
 */
 
-use anyhow::Result;
-use jellyobject::Object;
-
 use crate::{
-    RowNum,
+    RowNum, Sort,
     kv::{
         SubtreeNum,
         helpers::{read_counter, write_counter},
         index_key::{IndexKey, SortKey},
+        prefix_iterator::PrefixIterator,
     },
 };
+use anyhow::Result;
+use jellyobject::Object;
 
 pub fn update_index(
     txn: &mut dyn jellykv::Transaction,
@@ -54,12 +54,31 @@ pub fn update_index(
     Ok(())
 }
 
-pub fn read_count_index(
-    txn: &dyn jellykv::Transaction,
-    is: SubtreeNum,
+pub fn read_count_index(txn: &dyn jellykv::Transaction, prefix: Vec<u8>) -> Result<u64> {
+    read_counter(txn, &prefix, 0)
+}
+
+pub fn iter_index<'a>(
+    txn: &'a dyn jellykv::Transaction,
     prefix: Vec<u8>,
-) -> Result<u64> {
-    let mut k = is.to_be_bytes().to_vec();
-    k.extend(&prefix);
-    read_counter(txn, &k, 0)
+    sort: &Sort,
+) -> Result<Box<dyn Iterator<Item = Result<(RowNum, Vec<u8>)>> + 'a>> {
+    Ok(match sort {
+        Sort::None => Box::new(
+            PrefixIterator {
+                inner: txn.iter(&prefix, false)?,
+                prefix: prefix.into(),
+            }
+            .map(|k| {
+                k.map(|k| {
+                    (
+                        RowNum::from_be_bytes(k[k.len() - 8..].try_into().unwrap()),
+                        k[4..].to_vec(),
+                    )
+                })
+            }),
+        ),
+        Sort::Value(value_sort) => todo!(),
+        Sort::TextSearch(path, _) => todo!(),
+    })
 }
diff --git a/database/src/kv/merge_iterator.rs b/database/src/kv/merge_iterator.rs
new file mode 100644
index 0000000..5658416
--- /dev/null
+++ b/database/src/kv/merge_iterator.rs
@@ -0,0 +1,23 @@
+/*
+    This file is part of jellything (https://codeberg.org/metamuffin/jellything)
+    which is licensed under the GNU Affero General Public License (version 3); see /COPYING.
+    Copyright (C) 2026 metamuffin <metamuffin.org>
+*/
+
+use crate::RowNum;
+use anyhow::Result;
+
+pub struct MergeIterator<'a> {
+    iters: Vec<Box<dyn Iterator<Item = Result<(RowNum, Vec<u8>)>> + 'a>>,
+}
+impl<'a> MergeIterator<'a> {
+    pub fn new(iters: Vec<Box<dyn Iterator<Item = Result<(RowNum, Vec<u8>)>> + 'a>>) -> Self {
+        Self { iters }
+    }
+}
+impl<'a> Iterator for MergeIterator<'a> {
+    type Item = Result<(RowNum, Vec<u8>)>;
+    fn next(&mut self) -> Option<Self::Item> {
+        todo!()
+    }
+}
diff --git a/database/src/kv/mod.rs b/database/src/kv/mod.rs
index 2d2f3cc..9cb05fc 100644
--- a/database/src/kv/mod.rs
+++ b/database/src/kv/mod.rs
@@ -8,17 +8,19 @@ pub mod binning;
 pub mod helpers;
 pub mod index;
 pub mod index_key;
+pub mod merge_iterator;
 pub mod prefix_iterator;
 pub mod sort;
 
 use std::borrow::Cow;
 
 use crate::{
-    Database, Query, RowIter, RowNum, Transaction,
+    Database, Query, RowNum, Transaction,
     kv::{
         helpers::{read_counter, write_counter},
-        index::{read_count_index, update_index},
+        index::{iter_index, read_count_index, update_index},
         index_key::{IndexKey, SortKey},
+        merge_iterator::MergeIterator,
         prefix_iterator::PrefixIterator,
     },
 };
@@ -91,27 +93,36 @@ impl Transaction for &mut dyn jellykv::Transaction {
         Ok(jellykv::Transaction::get(*self, &row_key(row))?.map(ObjectBuffer::from))
     }
 
-    fn query(&mut self, query: Query) -> Result<RowIter> {
-        // query
-        //     .filter
-        //     .get_bins()
-        //     .into_iter()
-        //     .flat_map(|b| {
-        //         let ikey = (b, query.sort.key());
-        //         self.indices.get(&ikey)
-        //     })
-        //     .map(|i| i.query(txn, &query.sort))
-        todo!()
+    fn query<'a>(
+        &'a mut self,
+        query: Query,
+    ) -> Result<Box<dyn Iterator<Item = Result<(RowNum, Vec<u8>)>> + 'a>> {
+        let mut prefixes = Vec::new();
+        for (binning, mut prefix) in query.filter.get_bins() {
+            let ik = IndexKey(binning, query.sort.key());
+            let is = get_or_create_index(*self, &ik)?;
+            prefix.splice(0..0, is.to_be_bytes());
+            prefixes.push(prefix);
+        }
+        let mut iters = Vec::new();
+        for prefix in prefixes {
+            iters.push(iter_index(*self, prefix, &query.sort)?)
+        }
+        if iters.len() == 1 {
+            return Ok(iters.pop().unwrap());
+        }
+        Ok(Box::new(MergeIterator::new(iters)))
     }
     fn query_single(&mut self, query: Query) -> Result<Option<RowNum>> {
-        self.query(query)?.next().transpose()
+        Ok(self.query(query)?.next().transpose()?.map(|(e, _)| e))
     }
     fn count(&mut self, query: Query) -> Result<u64> {
         let mut total = 0;
-        for (binning, prefix) in query.filter.get_bins() {
+        for (binning, mut prefix) in query.filter.get_bins() {
             let ik = IndexKey(binning, SortKey::Count);
             let is = get_or_create_index(*self, &ik)?;
-            total += read_count_index(*self, is, prefix)?;
+            prefix.splice(0..0, is.to_be_bytes());
+            total += read_count_index(*self, prefix)?;
         }
         Ok(total)
     }
@@ -183,10 +194,11 @@ fn inv_row_key(k: &[u8]) -> RowNum {
 #[cfg(test)]
 mod test {
     use crate::{
-        Database,
-        test_shared::{NAME, new_bob},
+        Database, Filter, Query, Sort,
+        test_shared::{AGE, NAME, new_alice, new_bob, new_charlie},
     };
     use anyhow::Result;
+    use jellyobject::Path;
 
     #[test]
     pub fn insert_get() -> Result<()> {
@@ -232,4 +244,31 @@ mod test {
         assert_eq!(bob.unwrap().as_object().get(NAME).unwrap(), "Better Bob");
         Ok(())
     }
+
+    #[test]
+    pub fn filter() -> Result<()> {
+        let db = jellykv::memory::new();
+
+        let mut rows = [0, 0, 0];
+        let mut result = None;
+
+        db.transaction(&mut |txn| {
+            rows = [
+                txn.insert(new_bob())?,
+                txn.insert(new_alice())?,
+                txn.insert(new_charlie())?,
+            ];
+            Ok(())
+        })?;
+        db.transaction(&mut |txn| {
+            result = txn.query_single(Query {
+                filter: Filter::Match(Path(vec![AGE.0]), 35_u32.to_be_bytes().to_vec()),
+                sort: Sort::None,
+            })?;
+            Ok(())
+        })?;
+
+        assert_eq!(result.unwrap(), 0);
+        Ok(())
+    }
 }
diff --git a/database/src/lib.rs b/database/src/lib.rs
index d4b9fba..c4b2d47 100644
--- a/database/src/lib.rs
+++ b/database/src/lib.rs
@@ -11,7 +11,7 @@ use anyhow::Result;
 use jellyobject::{ObjectBuffer, Path};
 
 pub type RowNum = u64;
-pub type RowIter = Box<dyn Iterator<Item = Result<RowNum>>>;
+pub type RowIter = Box<dyn Iterator<Item = Result<(RowNum, Vec<u8>)>>>;
 
 pub trait Database: Send + Sync {
     fn transaction(&self, f: &mut dyn FnMut(&mut dyn Transaction) -> Result<()>) -> Result<()>;
@@ -22,7 +22,10 @@ pub trait Transaction {
     fn remove(&mut self, row: RowNum) -> Result<()>;
     fn update(&mut self, row: RowNum, entry: ObjectBuffer) -> Result<()>;
     fn get(&self, row: RowNum) -> Result<Option<ObjectBuffer>>;
-    fn query(&mut self, query: Query) -> Result<RowIter>;
+    fn query<'a>(
+        &'a mut self,
+        query: Query,
+    ) -> Result<Box<dyn Iterator<Item = Result<(RowNum, Vec<u8>)>> + 'a>>;
     fn query_single(&mut self, query: Query) -> Result<Option<RowNum>>;
     fn count(&mut self, query: Query) -> Result<u64>;
 }
diff --git a/database/src/test_shared.rs b/database/src/test_shared.rs
index fbd9501..82e9ba4 100644
--- a/database/src/test_shared.rs
+++ b/database/src/test_shared.rs
@@ -26,3 +26,9 @@ pub(crate) fn new_bob() -> ObjectBuffer {
         (FRIEND.0, &"Charlie"),
     ])
 }
+pub(crate) fn new_alice() -> ObjectBuffer {
+    ObjectBuffer::new(&mut [(NAME.0, &"Alice"), (AGE.0, &31_u32), (FRIEND.0, &"Bob")])
+}
+pub(crate) fn new_charlie() -> ObjectBuffer {
+    ObjectBuffer::new(&mut [(NAME.0, &"Charlie"), (AGE.0, &31_u32), (FRIEND.0, &"Bob")])
+}