🥮 mooncakes.io

    #core/attr

    Attribute indexing strategies for filtered search.

    #Strategies

    • Basic: Hash map based indexing
    • Bitmap: Bitmap index for low-cardinality fields
    • BPTree: B+ tree for balanced read/write
    • LSM: Write-optimized with memtable

    #Key Types

    • AttrIndexStrategy: Strategy selection enum
    • NumEntry: Sorted entry for numeric index (value, id) pair
    • BasicAttrIndex: Hash map based attribute index
    • BitmapIndex: Bitmap index implementation
    • BPTree: B+ tree index implementation
    • LSMTree: LSM tree with memtable and levels

    #Usage

    let index = BasicAttrIndex::new()
    index.insert("category", @types.String("electronics"), 123L)
    let ids = index.find("category", @types.String("electronics"))

    BPTree

    source
    type BPTree

    B+ Tree structure

    BPTreeAttrIndex

    source
    pub struct BPTreeAttrIndex {
      field_trees : Map[String, BPTree]
      exists_trees : Map[String, BPTree]
      data : Map[
    VectorId    , 
    Attrs    ]
      order : Int
    }

    B+ Tree Attribute Index container

    BPTreeAttrIndex::all_ids

    source

    Return every indexed ID (from the data map).

    BPTreeAttrIndex::deserialize

    source
    fn BPTreeAttrIndex::deserialize(data : Bytes) -> BPTreeAttrIndex

    Deserialize a B+ tree attribute index from serialized bytes.

    Three on-disk layouts are supported (see IdFormat for the history). The legacy v2-tag-byte layout shipped by trkbt10/vcdb <= 0.3.0 is distinguished from the current length-prefixed layout by peeking the first byte of the first VectorId — the two encodings never share a possible first byte, so the choice is unambiguous when data exists. Empty indices default to the current layout.

    BPTreeAttrIndex::eq

    source

    Find IDs where key equals value

    BPTreeAttrIndex::exists

    source

    Find IDs where key exists

    BPTreeAttrIndex::get_attrs

    source

    Get attributes for an ID

    BPTreeAttrIndex::new

    source
    fn BPTreeAttrIndex::new(order? : Int) -> BPTreeAttrIndex

    Create a new BPTreeAttrIndex

    BPTreeAttrIndex::range

    source

    Find IDs matching a numeric range

    BPTreeAttrIndex::remove_id

    source

    Remove an ID from the index

    BPTreeAttrIndex::serialize

    source
    fn BPTreeAttrIndex::serialize(self : BPTreeAttrIndex) -> Bytes

    Serialize a B+ tree attribute index, including node graphs and stored attrs

    BPTreeAttrIndex::set_attrs

    source

    Set attributes for an ID

    BPTreeAttrIndex::size

    source
    fn BPTreeAttrIndex::size(self : BPTreeAttrIndex) -> Int

    Get the number of indexed IDs

    BasicAttrIndex

    source

    Basic Attribute Index - Hash map based implementation Provides fast equality lookups and range queries via sorted numeric arrays.

    BasicAttrIndex::eq

    source

    Find IDs where key equals value

    BasicAttrIndex::exists

    source

    Find IDs where key exists

    BasicAttrIndex::get_attrs

    source

    Get attributes for an ID

    BasicAttrIndex::new

    source

    Create a new empty BasicAttrIndex

    BasicAttrIndex::range

    source

    Find IDs matching a numeric range Returns None if range queries are not supported for this key

    BasicAttrIndex::remove_id

    source

    Remove an ID from the index

    BasicAttrIndex::set_attrs

    source

    Set attributes for an ID (replaces existing)

    BasicAttrIndex::size

    source
    fn BasicAttrIndex::size(self : BasicAttrIndex) -> Int

    Get the number of indexed IDs

    BitmapAttrIndex

    source

    Bitmap Attribute Index - Simplified index for low-cardinality fields Supports equality and existence queries only, no range queries.

    BitmapAttrIndex::eq

    source

    Find IDs where key equals value

    BitmapAttrIndex::exists

    source

    Find IDs where key exists

    BitmapAttrIndex::get_attrs

    source

    Get attributes for an ID

    BitmapAttrIndex::new

    source

    Create a new empty BitmapAttrIndex

    BitmapAttrIndex::range

    source

    Range queries not supported for Bitmap index

    BitmapAttrIndex::remove_id

    source

    Remove an ID from the index

    BitmapAttrIndex::set_attrs

    source

    Set attributes for an ID (replaces existing)

    BitmapAttrIndex::size

    source
    fn BitmapAttrIndex::size(self : BitmapAttrIndex) -> Int

    Get the number of indexed IDs

    BloomFilter

    source
    pub struct BloomFilter {
      bits : Bytes
      hash_count : Int
      bit_count : Int
    }

    Bloom filter for fast negative lookups

    BloomFilter::create

    source
    fn BloomFilter::create(keys : Array[Bytes], false_positive_rate : Double) -> BloomFilter

    Create a bloom filter from a set of keys

    BloomFilter::decode

    source
    fn BloomFilter::decode(buf : Bytes) -> BloomFilter?

    Decode bloom filter from bytes

    BloomFilter::encode

    source
    fn BloomFilter::encode(self : BloomFilter) -> Bytes

    Encode bloom filter to bytes

    BloomFilter::might_contain

    source
    fn BloomFilter::might_contain(self : BloomFilter, key : Bytes) -> Bool

    Check if a key might be in the bloom filter

    LSMAttrIndex

    source
    pub struct LSMAttrIndex {
      memtable : Memtable
      exists_memtable : Memtable
      data : Map[
    VectorId    , 
    Attrs    ]
      flush_threshold : Int
    }

    LSM Index

    LSMAttrIndex::clear_memtable

    source
    fn LSMAttrIndex::clear_memtable(self : LSMAttrIndex) -> Unit

    Clear memtable (for manual flush)

    LSMAttrIndex::eq

    source

    Find IDs where key equals value

    LSMAttrIndex::exists

    source

    Find IDs where key exists

    LSMAttrIndex::get_attrs

    source

    Get attributes for an ID

    LSMAttrIndex::memtable_size

    source
    fn LSMAttrIndex::memtable_size(self : LSMAttrIndex) -> Int

    Get memtable size (for flush threshold checking)

    LSMAttrIndex::new

    source
    fn LSMAttrIndex::new(flush_threshold? : Int) -> LSMAttrIndex

    Create a new LSM attribute index

    LSMAttrIndex::range

    source

    Find IDs matching a numeric range Note: Range queries scan through all entries - not optimal for large datasets

    LSMAttrIndex::remove_id

    source

    Remove an ID from the index

    LSMAttrIndex::set_attrs

    source

    Set attributes for an ID

    LSMAttrIndex::should_flush

    source
    fn LSMAttrIndex::should_flush(self : LSMAttrIndex) -> Bool

    Check if memtable should be flushed

    LSMAttrIndex::size

    source
    fn LSMAttrIndex::size(self : LSMAttrIndex) -> Int

    Get the number of indexed IDs

    Memtable

    source
    type Memtable

    Memtable structure

    NumEntry

    source
    pub struct NumEntry {
      value : Double
      id : 
    VectorId
    }

    Sorted entry for numeric index (value, id) pair
    impl Show for NumEntry

    NumEntry::compare

    source
    fn NumEntry::compare(self : NumEntry, other : NumEntry) -> Int

    Compare NumEntry by value for sorting

    SSTable

    source
    pub struct SSTable {
      records : Array[SSTableRecord]
      index : Array[SparseIndexEntry]
      bloom : BloomFilter?
      footer : SSTableFooter
    }

    Decoded SSTable structure (in-memory)

    SSTable::build

    source
    fn SSTable::build(records : Array[SSTableRecord], index_interval : Int) -> Bytes

    Build an SSTable from sorted records

    SSTable::find

    source
    fn SSTable::find(self : SSTable, key : Bytes) -> SSTableRecord?

    Find a record in SSTable by key

    SSTable::read

    source
    fn SSTable::read(buf : Bytes) -> SSTable?

    Read an SSTable from bytes

    SSTableFooter

    source
    pub struct SSTableFooter {
      magic : UInt
      version : UInt
      data_offset : Int
      data_size : Int
      index_offset : Int
      index_size : Int
      bloom_offset : Int
      bloom_size : Int
    }

    SSTable footer structure

    SSTableFooter::decode

    source
    fn SSTableFooter::decode(buf : Bytes) -> SSTableFooter?

    Decode footer from bytes

    SSTableFooter::encode

    source
    fn SSTableFooter::encode(self : SSTableFooter) -> Bytes

    Encode footer to bytes

    SSTableRecord

    source
    pub struct SSTableRecord {
      key : Bytes
      value : Bytes
    }

    SSTable record

    SSTableRecord::decode

    source
    fn SSTableRecord::decode(buf : Bytes, offset : Int) -> (SSTableRecord, Int)?

    Decode a single record from bytes at given offset

    SSTableRecord::encode

    source
    fn SSTableRecord::encode(self : SSTableRecord) -> Bytes

    Encode a single record to bytes

    SparseIndexEntry

    source
    pub struct SparseIndexEntry {
      key : Bytes
      offset : Int
    }

    Sparse index entry

    attr_value_to_key

    source
    fn attr_value_to_key(value : 
    AttrValue    ) -> String

    Convert AttrValue to string key for indexing Uses type prefix to disambiguate different types with same string representation

    attr_value_to_number

    source
    fn attr_value_to_number(value : 
    AttrValue    ) -> Double?

    Extract numeric value from AttrValue for range queries

    lower_bound

    source
    fn lower_bound(arr : Array[NumEntry], target : Double) -> Int

    Binary search for lower bound in sorted array Returns index of first element >= target

    remove_num_entry_swap

    source
    fn remove_num_entry_swap(arr : Array[NumEntry], id : 
    VectorId    ) -> Bool

    Remove a NumEntry by id from an array using swap-and-pop Returns true if the entry was found and removed

    remove_vectorid_swap

    source

    Remove an Int64 value from an array using swap-and-pop Returns true if the value was found and removed

    sort_num_entries

    source
    fn sort_num_entries(arr : Array[NumEntry]) -> Unit

    Sort NumEntry array by value

    upper_bound

    source
    fn upper_bound(arr : Array[NumEntry], target : Double) -> Int

    Binary search for upper bound in sorted array Returns index of first element > target

    Source Files

    Powered by MoonBit

    Site sourceReport issueModulesSkillsCLIBuild queueStatistics

    © 2026 mooncakes.io