Skip to main content

uqa_storage_sqlite/inverted_index/
block_max.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Skip-pointer and scorer-versioned block-max materialization.
8
9use super::{
10    decode_index_u64, decode_index_usize, encode_index_u64, encode_index_usize, params,
11    quote_ident, table_exists, BlockMaxIndex, BlockMaxScorer, DocId, InvertedIndex,
12    OptionalExtension, SQLiteError, SQLiteInvertedIndex, StorageBackendResult, TokenTermKey,
13};
14
15impl SQLiteInvertedIndex {
16    /// Read the nearest materialized skip pointer without mutating storage.
17    /// Call [`Self::flush_skip_pointers`] from an explicit maintenance/write
18    /// boundary after postings change.
19    pub fn skip_to(
20        &self,
21        field: &str,
22        term: &str,
23        target_doc_id: DocId,
24    ) -> StorageBackendResult<(DocId, usize)> {
25        encode_index_u64("target document", target_doc_id)?;
26        if let Some(index) = self.native_index() {
27            return index.skip_to(field, term, target_doc_id);
28        }
29        self.require_graph_format()?;
30        let term = TokenTermKey::from_text(term);
31        let table = self.skip_table_name(field);
32        let target_doc_id = encode_index_u64("target document", target_doc_id)?;
33        Ok(self.conn.with(|conn| {
34            if !table_exists(conn, &table)? {
35                return Ok((0, 0));
36            }
37            let sql = format!(
38                "SELECT skip_doc_id, skip_offset FROM {}
39                     WHERE term = ?1 AND skip_doc_id <= ?2
40                     ORDER BY skip_doc_id DESC LIMIT 1",
41                quote_ident(&table)
42            );
43            let row: Option<(i64, i64)> = conn
44                .query_row(&sql, params![term.as_bytes(), target_doc_id], |row| {
45                    Ok((row.get(0)?, row.get(1)?))
46                })
47                .optional()?;
48            match row {
49                Some((doc_id, offset)) => Ok((
50                    decode_index_u64("skip document", doc_id)?,
51                    decode_index_usize("skip offset", offset)?,
52                )),
53                None => Ok((0, 0)),
54            }
55        })?)
56    }
57
58    pub fn build_block_max_scores<S: BlockMaxScorer + ?Sized>(
59        &self,
60        field: &str,
61        term: &str,
62        scorer: &S,
63    ) -> StorageBackendResult<()> {
64        self.build_block_max_scores_versioned(field, term, scorer, "")
65    }
66
67    /// Build one scorer-versioned block-max posting. The version is checked
68    /// on load so changed BM25 parameters or field statistics can never feed
69    /// an unsafe pruning bound.
70    pub fn build_block_max_scores_versioned<S: BlockMaxScorer + ?Sized>(
71        &self,
72        field: &str,
73        term: &str,
74        scorer: &S,
75        scorer_fingerprint: &str,
76    ) -> StorageBackendResult<()> {
77        self.build_block_max_scores_key(
78            field,
79            &TokenTermKey::from_text(term),
80            scorer,
81            scorer_fingerprint,
82        )
83    }
84
85    pub(super) fn build_block_max_scores_key<S: BlockMaxScorer + ?Sized>(
86        &self,
87        field: &str,
88        term: &TokenTermKey,
89        scorer: &S,
90        scorer_fingerprint: &str,
91    ) -> StorageBackendResult<()> {
92        if let Some(index) = self.native_index() {
93            return index.build_block_max_scores_key(field, term, scorer, scorer_fingerprint);
94        }
95        let mut cursor = self.posting_cursor_key(field, term)?;
96        if cursor.doc_freq() == 0 && !self.has_field(field)? {
97            return Ok(());
98        }
99        let df = cursor.doc_freq();
100        let scored_capacity = usize::try_from(df)
101            .map_err(|_| SQLiteError::StorageBackend("document frequency exceeds usize".into()))?;
102        let mut scored_entries = Vec::with_capacity(scored_capacity);
103        while let Some(entry) = cursor.current() {
104            scored_entries.push((entry.term_freq, entry.doc_length));
105            cursor.advance()?;
106        }
107        self.ensure_aux_tables(field)?;
108        let table = self.blockmax_table_name(field);
109        self.conn.with_mut(|conn| {
110            let tx = conn.savepoint()?;
111            tx.execute(
112                &format!("DELETE FROM {} WHERE term = ?1", quote_ident(&table)),
113                [term.as_bytes()],
114            )?;
115            for (block_idx, chunk) in scored_entries.chunks(Self::BLOCK_SIZE).enumerate() {
116                let mut max_score = 0.0_f64;
117                for &(tf, doc_length) in chunk {
118                    let score = scorer.score(tf, doc_length, df);
119                    if !score.is_finite() || score < 0.0 {
120                        return Err(SQLiteError::StorageBackend(format!(
121                            "block-max score must be finite and non-negative, got {score}"
122                        )));
123                    }
124                    max_score = max_score.max(score);
125                }
126                let block_idx = encode_index_usize("block index", block_idx)?;
127                tx.execute(
128                    &format!(
129                        "INSERT OR REPLACE INTO {}
130                            (term, block_idx, max_score, scorer_fingerprint)
131                         VALUES (?1, ?2, ?3, ?4)",
132                        quote_ident(&table)
133                    ),
134                    params![term.as_bytes(), block_idx, max_score, scorer_fingerprint],
135                )?;
136            }
137            tx.commit()?;
138            Ok(())
139        })?;
140        Ok(())
141    }
142
143    pub fn build_all_block_max_scores<S: BlockMaxScorer + ?Sized>(
144        &self,
145        field: &str,
146        scorer: &S,
147    ) -> StorageBackendResult<()> {
148        if let Some(index) = self.native_index() {
149            return index.build_all_block_max_scores(field, scorer);
150        }
151        let terms = self.vocabulary_keys(field)?;
152        for term in terms {
153            self.build_block_max_scores_key(field, &term, scorer, "")?;
154        }
155        Ok(())
156    }
157
158    pub fn get_block_max_score(
159        &self,
160        field: &str,
161        term: &str,
162        block_idx: usize,
163    ) -> StorageBackendResult<f64> {
164        encode_index_usize("block index", block_idx)?;
165        if let Some(index) = self.native_index() {
166            return index.get_block_max_score(field, term, block_idx);
167        }
168        self.require_graph_format()?;
169        let term = TokenTermKey::from_text(term);
170        let table = self.blockmax_table_name(field);
171        let block_idx = encode_index_usize("block index", block_idx)?;
172        Ok(self.conn.with(|conn| {
173            if !table_exists(conn, &table)? {
174                return Ok(0.0);
175            }
176            let sql = format!(
177                "SELECT max_score FROM {}
178                     WHERE term = ?1 AND block_idx = ?2",
179                quote_ident(&table)
180            );
181            let score: Option<f64> = conn
182                .query_row(&sql, params![term.as_bytes(), block_idx], |row| row.get(0))
183                .optional()?;
184            Ok(score.unwrap_or(0.0))
185        })?)
186    }
187
188    pub fn get_all_block_max_scores(
189        &self,
190        field: &str,
191        term: &str,
192    ) -> StorageBackendResult<Vec<f64>> {
193        self.get_all_block_max_scores_key(field, &TokenTermKey::from_text(term))
194    }
195
196    pub fn get_all_block_max_scores_key(
197        &self,
198        field: &str,
199        term: &TokenTermKey,
200    ) -> StorageBackendResult<Vec<f64>> {
201        if let Some(index) = self.native_index() {
202            return index.get_all_block_max_scores_key(field, term);
203        }
204        self.require_graph_format()?;
205        let table = self.blockmax_table_name(field);
206        Ok(self.conn.with(|conn| {
207            if !table_exists(conn, &table)? {
208                return Ok(Vec::new());
209            }
210            let sql = format!(
211                "SELECT block_idx, max_score FROM {}
212                     WHERE term = ?1 ORDER BY block_idx",
213                quote_ident(&table)
214            );
215            let mut stmt = conn.prepare(&sql)?;
216            let rows = stmt
217                .query_map([term.as_bytes()], |row| {
218                    Ok((row.get::<_, i64>(0)?, row.get::<_, f64>(1)?))
219                })?
220                .collect::<Result<Vec<_>, _>>()?;
221            let mut scores = Vec::with_capacity(rows.len());
222            for (expected, (block_idx, score)) in rows.into_iter().enumerate() {
223                let block_idx = decode_index_usize("block index", block_idx)?;
224                if block_idx != expected {
225                    return Err(SQLiteError::StorageBackend(format!(
226                        "corrupt inverted index: expected block index {expected}, found {block_idx}"
227                    )));
228                }
229                scores.push(score);
230            }
231            Ok(scores)
232        })?)
233    }
234
235    pub fn get_versioned_block_max_scores(
236        &self,
237        field: &str,
238        term: &str,
239        scorer_fingerprint: &str,
240    ) -> StorageBackendResult<Option<Vec<f64>>> {
241        Ok(self
242            .get_versioned_block_max_scores_bulk(field, &[term.to_string()], scorer_fingerprint)?
243            .pop()
244            .flatten())
245    }
246
247    pub fn get_versioned_block_max_scores_bulk(
248        &self,
249        field: &str,
250        terms: &[String],
251        scorer_fingerprint: &str,
252    ) -> StorageBackendResult<Vec<Option<Vec<f64>>>> {
253        let keys = terms
254            .iter()
255            .map(|term| TokenTermKey::from_text(term))
256            .collect::<Vec<_>>();
257        self.get_versioned_block_max_scores_keys_bulk(field, &keys, scorer_fingerprint)
258    }
259
260    pub fn get_versioned_block_max_scores_keys_bulk(
261        &self,
262        field: &str,
263        terms: &[TokenTermKey],
264        scorer_fingerprint: &str,
265    ) -> StorageBackendResult<Vec<Option<Vec<f64>>>> {
266        if let Some(index) = self.native_index() {
267            return index.get_versioned_block_max_scores_keys_bulk(
268                field,
269                terms,
270                scorer_fingerprint,
271            );
272        }
273        if terms.is_empty() {
274            return Ok(Vec::new());
275        }
276        let table = self.blockmax_table_name(field);
277        Ok(self.conn.with(|conn| {
278            self.require_graph_format_on(conn)?;
279            if !table_exists(conn, &table)? {
280                return Ok(vec![None; terms.len()]);
281            }
282            let pragma = format!("PRAGMA table_info({})", quote_ident(&table));
283            let mut columns = conn.prepare(&pragma)?;
284            let has_fingerprint = columns
285                .query_map([], |row| row.get::<_, String>(1))?
286                .collect::<Result<Vec<_>, _>>()?
287                .iter()
288                .any(|name| name == "scorer_fingerprint");
289            drop(columns);
290            if !has_fingerprint {
291                return Ok(vec![None; terms.len()]);
292            }
293
294            let unique_terms = terms
295                .iter()
296                .cloned()
297                .collect::<std::collections::BTreeSet<_>>();
298            let unique_terms = unique_terms.into_iter().collect::<Vec<_>>();
299            let mut by_term = std::collections::BTreeMap::<Vec<u8>, Vec<(i64, f64)>>::new();
300            for chunk in unique_terms.chunks(900) {
301                let placeholders = std::iter::repeat_n("?", chunk.len())
302                    .collect::<Vec<_>>()
303                    .join(", ");
304                let sql = format!(
305                    "SELECT term, block_idx, max_score FROM {}
306                     WHERE scorer_fingerprint = ? AND term IN ({placeholders})
307                     ORDER BY term, block_idx",
308                    quote_ident(&table)
309                );
310                let mut values = Vec::with_capacity(chunk.len() + 1);
311                values.push(rusqlite::types::Value::Text(scorer_fingerprint.to_string()));
312                values.extend(
313                    chunk
314                        .iter()
315                        .map(|term| rusqlite::types::Value::Blob(term.as_bytes().to_vec())),
316                );
317                let mut statement = conn.prepare(&sql)?;
318                let rows = statement.query_map(rusqlite::params_from_iter(values), |row| {
319                    Ok((
320                        row.get::<_, Vec<u8>>(0)?,
321                        row.get::<_, i64>(1)?,
322                        row.get::<_, f64>(2)?,
323                    ))
324                })?;
325                for row in rows {
326                    let (term, block_idx, score) = row?;
327                    by_term.entry(term).or_default().push((block_idx, score));
328                }
329            }
330
331            let mut decoded = std::collections::BTreeMap::<TokenTermKey, Option<Vec<f64>>>::new();
332            for term in unique_terms {
333                let rows = by_term.remove(term.as_bytes()).unwrap_or_default();
334                if rows.is_empty() {
335                    decoded.insert(term, None);
336                    continue;
337                }
338                let mut scores = Vec::with_capacity(rows.len());
339                for (expected, (block_idx, score)) in rows.into_iter().enumerate() {
340                    let block_idx = decode_index_usize("block index", block_idx)?;
341                    if block_idx != expected || !score.is_finite() || score < 0.0 {
342                        return Err(SQLiteError::StorageBackend(format!(
343                            "corrupt block-max index for `{field}.{term:?}` at block {block_idx}"
344                        )));
345                    }
346                    scores.push(score);
347                }
348                decoded.insert(term, Some(scores));
349            }
350            Ok(terms.iter().map(|term| decoded[term].clone()).collect())
351        })?)
352    }
353
354    pub fn load_block_max_into(&self, target: &mut BlockMaxIndex) -> StorageBackendResult<()> {
355        if let Some(index) = self.native_index() {
356            return index.load_block_max_into(target);
357        }
358        for field in self.fields_with_blockmax_tables()? {
359            for term in self.vocabulary_keys(&field)? {
360                let scores = self.get_all_block_max_scores_key(&field, &term)?;
361                if !scores.is_empty() {
362                    target.set_block_maxes_key(&self.table, &field, &term, scores)?;
363                }
364            }
365        }
366        Ok(())
367    }
368}