lance_index/
lib.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright The Lance Authors
3
4//! Lance secondary index library
5//!
6//! <section class="warning">
7//! This is internal crate used by <a href="https://github.com/lance-format/lance">the lance project</a>.
8//! <br/>
9//! API stability is not guaranteed.
10//! </section>
11
12use crate::frag_reuse::FRAG_REUSE_INDEX_NAME;
13use crate::mem_wal::MEM_WAL_INDEX_NAME;
14use serde::{Deserialize, Serialize};
15
16pub mod frag_reuse;
17pub mod mem_wal;
18pub mod metrics;
19pub mod optimize;
20pub mod prefilter;
21pub mod progress;
22pub mod registry;
23pub mod scalar;
24pub mod traits;
25pub mod vector;
26
27pub use crate::traits::*;
28
29// Re-export core traits from lance-index-core
30pub use lance_index_core::{Index, IndexParams, IndexType};
31
32pub const INDEX_FILE_NAME: &str = "index.idx";
33/// The name of the auxiliary index file.
34///
35/// This file is used to store additional information about the index, to improve performance.
36/// - For 'IVF_HNSW' index, it stores the partitioned PQ Storage.
37pub const INDEX_AUXILIARY_FILE_NAME: &str = "auxiliary.idx";
38pub const INDEX_METADATA_SCHEMA_KEY: &str = "lance:index";
39
40/// Default version for vector index metadata.
41///
42/// Most vector indices should use this version unless they need to bump for a
43/// format change.
44pub const VECTOR_INDEX_VERSION: u32 = 1;
45/// Version for IVF_RQ indices.
46pub const IVF_RQ_INDEX_VERSION: u32 = 2;
47
48/// The factor of threshold to trigger split / join for vector index.
49///
50/// If the number of rows in the single partition is greater than `MAX_PARTITION_SIZE_FACTOR * target_partition_size`,
51/// the partition will be split.
52/// If the number of rows in the single partition is less than `MIN_PARTITION_SIZE_PERCENT *target_partition_size / 100`,
53/// the partition will be joined.
54pub const MAX_PARTITION_SIZE_FACTOR: usize = 4;
55pub const MIN_PARTITION_SIZE_PERCENT: usize = 25;
56
57pub mod pb {
58    #![allow(clippy::use_self)]
59    include!(concat!(env!("OUT_DIR"), "/lance.index.pb.rs"));
60}
61
62pub mod pbold {
63    #![allow(clippy::use_self)]
64    include!(concat!(env!("OUT_DIR"), "/lance.table.rs"));
65}
66
67/// Protobuf headers for serialized index cache entries (FTS posting lists,
68/// scalar indices, and IVF vector partitions).
69pub mod cache_pb {
70    #![allow(clippy::use_self)]
71    include!(concat!(env!("OUT_DIR"), "/lance.index.cache.rs"));
72}
73
74#[derive(Serialize, Deserialize, Debug)]
75pub struct IndexMetadata {
76    #[serde(rename = "type")]
77    pub index_type: String,
78    pub distance_type: String,
79}
80
81pub fn is_system_index(index_meta: &lance_table::format::IndexMetadata) -> bool {
82    index_meta.name == FRAG_REUSE_INDEX_NAME || index_meta.name == MEM_WAL_INDEX_NAME
83}
84
85pub fn infer_system_index_type(
86    index_meta: &lance_table::format::IndexMetadata,
87) -> Option<IndexType> {
88    if index_meta.name == FRAG_REUSE_INDEX_NAME {
89        Some(IndexType::FragmentReuse)
90    } else if index_meta.name == MEM_WAL_INDEX_NAME {
91        Some(IndexType::MemWal)
92    } else {
93        None
94    }
95}
96
97#[cfg(test)]
98mod tests {
99    use super::*;
100
101    #[test]
102    fn test_ivf_rq_has_dedicated_index_version() {
103        assert!(IndexType::IvfRq.version() > IndexType::IvfPq.version());
104        assert_eq!(IndexType::IvfRq.version() as u32, IVF_RQ_INDEX_VERSION);
105    }
106
107    #[test]
108    fn test_max_vector_version_tracks_highest_supported() {
109        assert_eq!(IndexType::max_vector_version(), IVF_RQ_INDEX_VERSION);
110    }
111
112    #[test]
113    fn test_ivf_rq_target_partition_size() {
114        assert_eq!(IndexType::IvfRq.target_partition_size(), 4096);
115    }
116
117    #[test]
118    fn test_index_type_try_from_i32_covers_all_variants() {
119        let all = [
120            IndexType::Scalar,
121            IndexType::BTree,
122            IndexType::Bitmap,
123            IndexType::LabelList,
124            IndexType::Inverted,
125            IndexType::NGram,
126            IndexType::FragmentReuse,
127            IndexType::MemWal,
128            IndexType::ZoneMap,
129            IndexType::BloomFilter,
130            IndexType::RTree,
131            IndexType::Fm,
132            IndexType::Vector,
133            IndexType::IvfFlat,
134            IndexType::IvfSq,
135            IndexType::IvfPq,
136            IndexType::IvfHnswSq,
137            IndexType::IvfHnswPq,
138            IndexType::IvfHnswFlat,
139            IndexType::IvfRq,
140        ];
141
142        for index_type in all {
143            assert_eq!(
144                IndexType::try_from(index_type as i32).unwrap(),
145                index_type,
146                "IndexType::try_from(i32) should support {:?}",
147                index_type
148            );
149        }
150    }
151
152    #[test]
153    fn test_index_type_try_from_str_covers_all_parseable_variants() {
154        let cases = [
155            ("BTree", IndexType::BTree),
156            ("BTREE", IndexType::BTree),
157            ("Bitmap", IndexType::Bitmap),
158            ("BITMAP", IndexType::Bitmap),
159            ("LabelList", IndexType::LabelList),
160            ("LABELLIST", IndexType::LabelList),
161            ("Inverted", IndexType::Inverted),
162            ("INVERTED", IndexType::Inverted),
163            ("NGram", IndexType::NGram),
164            ("NGRAM", IndexType::NGram),
165            ("ZoneMap", IndexType::ZoneMap),
166            ("ZONEMAP", IndexType::ZoneMap),
167            ("BloomFilter", IndexType::BloomFilter),
168            ("BLOOMFILTER", IndexType::BloomFilter),
169            ("BLOOM_FILTER", IndexType::BloomFilter),
170            ("RTree", IndexType::RTree),
171            ("RTREE", IndexType::RTree),
172            ("R_TREE", IndexType::RTree),
173            ("Fm", IndexType::Fm),
174            ("FM", IndexType::Fm),
175            ("Vector", IndexType::Vector),
176            ("VECTOR", IndexType::Vector),
177            ("IVF_FLAT", IndexType::IvfFlat),
178            ("IVF_SQ", IndexType::IvfSq),
179            ("IVF_PQ", IndexType::IvfPq),
180            ("IVF_RQ", IndexType::IvfRq),
181            ("IVF_HNSW_FLAT", IndexType::IvfHnswFlat),
182            ("IVF_HNSW_SQ", IndexType::IvfHnswSq),
183            ("IVF_HNSW_PQ", IndexType::IvfHnswPq),
184            ("FragmentReuse", IndexType::FragmentReuse),
185            ("MemWal", IndexType::MemWal),
186        ];
187
188        for (text, expected) in cases {
189            assert_eq!(
190                IndexType::try_from(text).unwrap(),
191                expected,
192                "IndexType::try_from(&str) should support '{text}'"
193            );
194        }
195    }
196}
lance_index/lib.rs

lance_index/
lib.rs
