Skip to main content

shard_telemetry/
query_index.rs

1use std::borrow::Cow;
2use std::collections::HashMap;
3use std::mem::size_of;
4use std::sync::Arc;
5
6use shard_stream_core::{LogicalOffset, LogicalPartitionId, TopicId, TopicPartition};
7
8use crate::{
9    LogQuery, QueryOrder, StructuralRecordView, TelemetryError, TelemetryResult, analyze_message,
10};
11
12const QUERY_INDEX_MAGIC: &[u8; 8] = b"STLGQIX1";
13const COMPRESSED_QUERY_INDEX_MAGIC: &[u8; 8] = b"STLGQIZ1";
14const DELTA_POSTING: u8 = 0;
15const RUN_POSTING: u8 = 1;
16const MESSAGE_TERM_CACHE_ENTRIES: usize = 1_024;
17const TERM_CACHE_ENTRIES: usize = 4_096;
18const MESSAGE_TRIGRAM_FILTER_BITS: usize = 65_536;
19const MESSAGE_TRIGRAM_FILTER_WORDS: usize = MESSAGE_TRIGRAM_FILTER_BITS / u64::BITS as usize;
20const MESSAGE_TRIGRAM_FILTER_BYTES: usize = MESSAGE_TRIGRAM_FILTER_WORDS * size_of::<u64>();
21
22struct CachedMessageTerms<'a> {
23    message: &'a str,
24    term_ids: Vec<usize>,
25}
26
27#[derive(Clone, Copy)]
28struct CachedTerm {
29    term_id: usize,
30}
31
32/// Lossless block-level rejection filter for literal message predicates.
33///
34/// Every bit represents a deterministic hash of one UTF-8 byte trigram after
35/// Unicode lowercase normalization. A missing bit proves that the literal is
36/// absent. A present bit remains only a candidate because hashes can collide.
37#[derive(Debug, Clone, PartialEq, Eq)]
38struct MessageTrigramFilter {
39    words: Box<[u64]>,
40}
41
42impl MessageTrigramFilter {
43    fn new() -> Self {
44        Self {
45            words: vec![0; MESSAGE_TRIGRAM_FILTER_WORDS].into_boxed_slice(),
46        }
47    }
48
49    fn from_bytes(encoded: &[u8]) -> TelemetryResult<Self> {
50        if encoded.len() != MESSAGE_TRIGRAM_FILTER_BYTES {
51            return Err(TelemetryError::InvalidBlockEncoding(
52                "invalid message trigram filter length",
53            ));
54        }
55        let mut filter = Self::new();
56        for (word, bytes) in filter.words.iter_mut().zip(encoded.chunks_exact(8)) {
57            *word = u64::from_le_bytes(bytes.try_into().map_err(|_| {
58                TelemetryError::InvalidBlockEncoding("invalid trigram filter word")
59            })?);
60        }
61        Ok(filter)
62    }
63
64    fn insert_message(&mut self, message: &str) {
65        visit_normalized_trigrams(message, |slot| {
66            self.words[slot / u64::BITS as usize] |= 1u64 << (slot % u64::BITS as usize);
67        });
68    }
69
70    fn might_contain_all(&self, slots: &[usize]) -> bool {
71        slots.iter().all(|slot| {
72            self.words[*slot / u64::BITS as usize] & (1u64 << (*slot % u64::BITS as usize)) != 0
73        })
74    }
75}
76
77fn visit_normalized_trigrams(message: &str, mut observe: impl FnMut(usize)) {
78    if message.is_ascii() {
79        for trigram in message.as_bytes().windows(3) {
80            observe(message_trigram_slot([
81                trigram[0].to_ascii_lowercase(),
82                trigram[1].to_ascii_lowercase(),
83                trigram[2].to_ascii_lowercase(),
84            ]));
85        }
86    } else {
87        for trigram in message.to_lowercase().as_bytes().windows(3) {
88            observe(message_trigram_slot([trigram[0], trigram[1], trigram[2]]));
89        }
90    }
91}
92
93#[inline]
94fn message_trigram_slot(trigram: [u8; 3]) -> usize {
95    let mut hash =
96        u32::from(trigram[0]) | (u32::from(trigram[1]) << 8) | (u32::from(trigram[2]) << 16);
97    hash ^= hash >> 16;
98    hash = hash.wrapping_mul(0x7feb_352d);
99    hash ^= hash >> 15;
100    hash = hash.wrapping_mul(0x846c_a68b);
101    hash ^= hash >> 16;
102    hash as usize & (MESSAGE_TRIGRAM_FILTER_BITS - 1)
103}
104
105fn required_message_trigram_slots(literals: &[&str]) -> Vec<usize> {
106    let mut slots = Vec::new();
107    for literal in literals {
108        visit_normalized_trigrams(literal, |slot| slots.push(slot));
109    }
110    slots.sort_unstable();
111    slots.dedup();
112    slots
113}
114
115/// Offset and timestamp bounds for one independently compressed block.
116#[derive(Debug, Clone, Copy, PartialEq, Eq)]
117pub struct QueryBlockMetadata {
118    /// Stable ordinal used by the pack manifest.
119    pub block_ordinal: u32,
120    /// Logical partition represented by the block.
121    pub topic_partition: TopicPartition,
122    /// Lowest durable offset in the block.
123    pub first_offset: LogicalOffset,
124    /// Highest durable offset in the block.
125    pub last_offset: LogicalOffset,
126    /// Lowest event timestamp in the block.
127    pub min_timestamp_unix_nanos: u64,
128    /// Highest event timestamp in the block.
129    pub max_timestamp_unix_nanos: u64,
130    /// Number of records in the block.
131    pub record_count: u32,
132}
133
134/// Exact location of a candidate record inside a sealed block.
135#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
136pub struct QueryHit {
137    /// Manifest block ordinal.
138    pub block_ordinal: u32,
139    /// Zero-based record ordinal inside the decoded structural block.
140    pub record_ordinal: u32,
141}
142
143#[derive(Debug, Clone, PartialEq, Eq)]
144struct BlockPosting {
145    block_ordinal: u32,
146    record_ordinals: PostingList,
147}
148
149#[derive(Debug, Clone, Copy, PartialEq, Eq)]
150struct OrdinalRun {
151    start: u32,
152    length: u32,
153}
154
155#[derive(Debug, Clone, PartialEq, Eq)]
156enum PostingList {
157    Ordinals(Vec<u32>),
158    Runs {
159        runs: Vec<OrdinalRun>,
160        cardinality: usize,
161    },
162}
163
164impl PostingList {
165    fn from_ordinals(ordinals: Vec<u32>) -> TelemetryResult<Self> {
166        if ordinals.is_empty() {
167            return Err(TelemetryError::InvalidBlockEncoding("empty query posting"));
168        }
169        if ordinals.windows(2).any(|pair| pair[0] >= pair[1]) {
170            return Err(TelemetryError::InvalidBlockEncoding(
171                "query posting is not ordered",
172            ));
173        }
174        let runs = posting_runs(&ordinals);
175        if runs.len().saturating_mul(2) < ordinals.len() {
176            Ok(Self::Runs {
177                runs,
178                cardinality: ordinals.len(),
179            })
180        } else {
181            Ok(Self::Ordinals(ordinals))
182        }
183    }
184
185    const fn cardinality(&self) -> usize {
186        match self {
187            Self::Ordinals(ordinals) => ordinals.len(),
188            Self::Runs { cardinality, .. } => *cardinality,
189        }
190    }
191
192    fn storage_bytes(&self) -> usize {
193        match self {
194            Self::Ordinals(ordinals) => ordinals.capacity() * size_of::<u32>(),
195            Self::Runs { runs, .. } => runs.capacity() * size_of::<OrdinalRun>(),
196        }
197    }
198
199    fn to_vec(&self) -> Vec<u32> {
200        match self {
201            Self::Ordinals(ordinals) => ordinals.clone(),
202            Self::Runs { runs, cardinality } => {
203                let mut ordinals = Vec::with_capacity(*cardinality);
204                for run in runs {
205                    ordinals.extend(run.start..run.start + run.length);
206                }
207                ordinals
208            }
209        }
210    }
211
212    fn take_ordered(&self, newest_first: bool, limit: usize) -> Vec<u32> {
213        match self {
214            Self::Ordinals(ordinals) => {
215                let take = limit.min(ordinals.len());
216                if newest_first {
217                    ordinals[ordinals.len() - take..]
218                        .iter()
219                        .rev()
220                        .copied()
221                        .collect()
222                } else {
223                    ordinals[..take].to_vec()
224                }
225            }
226            Self::Runs { runs, .. } => {
227                let mut ordinals = Vec::with_capacity(limit.min(self.cardinality()));
228                if newest_first {
229                    for run in runs.iter().rev() {
230                        for ordinal in (run.start..run.start + run.length).rev() {
231                            ordinals.push(ordinal);
232                            if ordinals.len() == limit {
233                                return ordinals;
234                            }
235                        }
236                    }
237                } else {
238                    for run in runs {
239                        for ordinal in run.start..run.start + run.length {
240                            ordinals.push(ordinal);
241                            if ordinals.len() == limit {
242                                return ordinals;
243                            }
244                        }
245                    }
246                }
247                ordinals
248            }
249        }
250    }
251
252    fn contains(&self, ordinal: u32) -> bool {
253        match self {
254            Self::Ordinals(ordinals) => ordinals.binary_search(&ordinal).is_ok(),
255            Self::Runs { runs, .. } => {
256                let position = runs.partition_point(|run| run.start <= ordinal);
257                position > 0
258                    && ordinal
259                        < runs[position - 1]
260                            .start
261                            .saturating_add(runs[position - 1].length)
262            }
263        }
264    }
265}
266
267type PartitionTermBlockPostings = HashMap<TopicPartition, HashMap<Arc<str>, Vec<BlockPosting>>>;
268type PartitionFieldBlockPostings =
269    HashMap<TopicPartition, HashMap<Arc<str>, HashMap<Arc<str>, Vec<BlockPosting>>>>;
270
271/// Exact term and metadata postings for one structural block.
272#[derive(Debug, Clone, PartialEq, Eq)]
273pub struct BlockQueryIndex {
274    record_count: u32,
275    message_trigrams: MessageTrigramFilter,
276    term_postings: HashMap<Arc<str>, PostingList>,
277    field_postings: HashMap<Arc<str>, HashMap<Arc<str>, PostingList>>,
278}
279
280impl BlockQueryIndex {
281    /// Builds exact record-ordinal postings from normalized structural records.
282    pub fn build<R: StructuralRecordView>(records: &[R]) -> TelemetryResult<Self> {
283        let record_count =
284            u32::try_from(records.len()).map_err(|_| TelemetryError::RecordTooLarge)?;
285        let mut term_ids = HashMap::<Arc<str>, usize>::new();
286        let mut term_entries = Vec::<(Arc<str>, Vec<u32>)>::new();
287        let mut message_cache = std::iter::repeat_with(|| None)
288            .take(MESSAGE_TERM_CACHE_ENTRIES)
289            .collect::<Vec<Option<CachedMessageTerms<'_>>>>();
290        let mut term_cache = vec![None::<CachedTerm>; TERM_CACHE_ENTRIES];
291        let mut message_trigrams = MessageTrigramFilter::new();
292        let mut field_postings = HashMap::<Arc<str>, HashMap<Arc<str>, Vec<u32>>>::new();
293        for (record_ordinal, record) in records.iter().enumerate() {
294            let record_ordinal =
295                u32::try_from(record_ordinal).map_err(|_| TelemetryError::RecordTooLarge)?;
296            let message = record.structural_message();
297            let cache_slot = message_term_cache_slot(message.as_bytes());
298            if let Some(cached) = &message_cache[cache_slot]
299                && same_message(cached.message, message)
300            {
301                for &term_id in &cached.term_ids {
302                    let postings = &mut term_entries[term_id].1;
303                    if postings.last().copied() != Some(record_ordinal) {
304                        postings.push(record_ordinal);
305                    }
306                }
307            } else {
308                message_trigrams.insert_message(message);
309                let mut message_term_ids = message_cache[cache_slot]
310                    .take()
311                    .map(|cached| cached.term_ids)
312                    .unwrap_or_default();
313                message_term_ids.clear();
314                let _ = analyze_message(message, &[], |term| {
315                    let cache_slot = term_cache_slot(term.as_bytes());
316                    let term_id = if let Some(cached) = term_cache[cache_slot]
317                        && term_matches_cached(&term_entries[cached.term_id].0, term)
318                    {
319                        cached.term_id
320                    } else {
321                        let normalized = normalize_term(term);
322                        let term_id = match term_ids.get(normalized.as_ref()).copied() {
323                            Some(term_id) => term_id,
324                            None => {
325                                let term = Arc::<str>::from(normalized.as_ref());
326                                let term_id = term_entries.len();
327                                term_ids.insert(Arc::clone(&term), term_id);
328                                term_entries.push((term, Vec::new()));
329                                term_id
330                            }
331                        };
332                        term_cache[cache_slot] = Some(CachedTerm { term_id });
333                        term_id
334                    };
335                    message_term_ids.push(term_id);
336                });
337                for &term_id in &message_term_ids {
338                    let postings = &mut term_entries[term_id].1;
339                    if postings.last().copied() != Some(record_ordinal) {
340                        postings.push(record_ordinal);
341                    }
342                }
343                message_cache[cache_slot] = Some(CachedMessageTerms {
344                    message,
345                    term_ids: message_term_ids,
346                });
347            }
348
349            for field_index in 0..record.structural_field_count() {
350                let (key, value) = record.structural_field(field_index).ok_or(
351                    TelemetryError::InvalidBlockEncoding(
352                        "record field count changed while indexing",
353                    ),
354                )?;
355                let values = match field_postings.get_mut(key) {
356                    Some(values) => values,
357                    None => {
358                        field_postings.insert(Arc::from(key), HashMap::new());
359                        field_postings.get_mut(key).expect("field key was inserted")
360                    }
361                };
362                let postings = match values.get_mut(value) {
363                    Some(postings) => postings,
364                    None => {
365                        values.insert(Arc::from(value), Vec::new());
366                        values.get_mut(value).expect("field value was inserted")
367                    }
368                };
369                if postings.last().copied() != Some(record_ordinal) {
370                    postings.push(record_ordinal);
371                }
372            }
373        }
374        let term_postings = term_entries
375            .into_iter()
376            .map(|(term, posting)| Ok((term, PostingList::from_ordinals(posting)?)))
377            .collect::<TelemetryResult<HashMap<_, _>>>()?;
378        let field_postings = field_postings
379            .into_iter()
380            .map(|(key, values)| {
381                let values = values
382                    .into_iter()
383                    .map(|(value, posting)| Ok((value, PostingList::from_ordinals(posting)?)))
384                    .collect::<TelemetryResult<HashMap<_, _>>>()?;
385                Ok((key, values))
386            })
387            .collect::<TelemetryResult<HashMap<_, _>>>()?;
388        Ok(Self {
389            record_count,
390            message_trigrams,
391            term_postings,
392            field_postings,
393        })
394    }
395
396    /// Number of indexed records.
397    #[must_use]
398    pub const fn record_count(&self) -> u32 {
399        self.record_count
400    }
401}
402
403#[inline]
404fn same_message(left: &str, right: &str) -> bool {
405    left.len() == right.len()
406        && (std::ptr::eq(left.as_ptr(), right.as_ptr()) || left.as_bytes() == right.as_bytes())
407}
408
409fn message_term_cache_slot(message: &[u8]) -> usize {
410    let mut hash = message.len() as u64 ^ 0x9e37_79b9_7f4a_7c15;
411    if message.len() >= 16 {
412        let first = u64::from_le_bytes(
413            message[..8]
414                .try_into()
415                .expect("eight-byte prefix is present"),
416        );
417        let last = u64::from_le_bytes(
418            message[message.len() - 8..]
419                .try_into()
420                .expect("eight-byte suffix is present"),
421        );
422        hash ^= first.rotate_left(17) ^ last.rotate_left(41);
423    } else {
424        for byte in message {
425            hash = (hash ^ u64::from(*byte)).wrapping_mul(0x0000_0100_0000_01b3);
426        }
427    }
428    hash ^= hash >> 33;
429    hash = hash.wrapping_mul(0xff51_afd7_ed55_8ccd);
430    (hash as usize) & (MESSAGE_TERM_CACHE_ENTRIES - 1)
431}
432
433fn term_cache_slot(term: &[u8]) -> usize {
434    let mut hash = term.len() as u64 ^ 0x517c_c1b7_2722_0a95;
435    if let Some(first) = term.first() {
436        hash ^= u64::from(*first) << 8;
437    }
438    if let Some(last) = term.last() {
439        hash ^= u64::from(*last) << 24;
440    }
441    if term.len() >= 8 {
442        hash ^= u64::from_le_bytes(term[..8].try_into().expect("eight-byte prefix is present"));
443    } else {
444        for byte in term {
445            hash = (hash ^ u64::from(*byte)).wrapping_mul(0x0000_0100_0000_01b3);
446        }
447    }
448    hash ^= hash >> 32;
449    (hash as usize) & (TERM_CACHE_ENTRIES - 1)
450}
451
452fn term_matches_cached(indexed: &str, observed: &str) -> bool {
453    if observed.is_ascii() {
454        indexed.eq_ignore_ascii_case(observed)
455    } else {
456        normalize_term(observed).as_ref() == indexed
457    }
458}
459
460/// Immutable query directory for a set of sealed structural blocks.
461#[derive(Debug, Clone, PartialEq, Eq)]
462pub struct PersistentQueryIndex {
463    blocks: Vec<QueryBlockMetadata>,
464    message_trigram_words: Box<[u64]>,
465    message_trigram_union: MessageTrigramFilter,
466    message_trigram_intersection: MessageTrigramFilter,
467    partition_blocks: HashMap<TopicPartition, Vec<u32>>,
468    term_postings: PartitionTermBlockPostings,
469    field_postings: PartitionFieldBlockPostings,
470}
471
472impl PersistentQueryIndex {
473    /// Builds one immutable directory from block-local exact postings.
474    pub fn from_blocks(
475        mut blocks: Vec<(QueryBlockMetadata, BlockQueryIndex)>,
476    ) -> TelemetryResult<Self> {
477        blocks.sort_unstable_by_key(|(metadata, _)| metadata.block_ordinal);
478        if blocks
479            .windows(2)
480            .any(|pair| pair[0].0.block_ordinal == pair[1].0.block_ordinal)
481        {
482            return Err(TelemetryError::InvalidBlockEncoding(
483                "duplicate query block ordinal",
484            ));
485        }
486        let mut metadata_entries = Vec::with_capacity(blocks.len());
487        let mut message_trigram_words =
488            Vec::with_capacity(blocks.len().saturating_mul(MESSAGE_TRIGRAM_FILTER_WORDS));
489        let mut partition_blocks = HashMap::<TopicPartition, Vec<u32>>::new();
490        let mut term_postings =
491            HashMap::<TopicPartition, HashMap<Arc<str>, Vec<BlockPosting>>>::new();
492        let mut field_postings = HashMap::<
493            TopicPartition,
494            HashMap<Arc<str>, HashMap<Arc<str>, Vec<BlockPosting>>>,
495        >::new();
496        for (metadata, index) in blocks {
497            if metadata.record_count != index.record_count
498                || metadata.first_offset > metadata.last_offset
499                || metadata.min_timestamp_unix_nanos > metadata.max_timestamp_unix_nanos
500            {
501                return Err(TelemetryError::InvalidBlockEncoding(
502                    "invalid query block metadata",
503                ));
504            }
505            partition_blocks
506                .entry(metadata.topic_partition)
507                .or_default()
508                .push(metadata.block_ordinal);
509            let partition_terms = term_postings.entry(metadata.topic_partition).or_default();
510            for (term, record_ordinals) in index.term_postings {
511                partition_terms.entry(term).or_default().push(BlockPosting {
512                    block_ordinal: metadata.block_ordinal,
513                    record_ordinals,
514                });
515            }
516            let partition_fields = field_postings.entry(metadata.topic_partition).or_default();
517            for (key, values) in index.field_postings {
518                let indexed_values = partition_fields.entry(key).or_default();
519                for (value, record_ordinals) in values {
520                    indexed_values.entry(value).or_default().push(BlockPosting {
521                        block_ordinal: metadata.block_ordinal,
522                        record_ordinals,
523                    });
524                }
525            }
526            message_trigram_words.extend_from_slice(&index.message_trigrams.words);
527            metadata_entries.push(metadata);
528        }
529        let (message_trigram_union, message_trigram_intersection) =
530            aggregate_message_trigrams(&message_trigram_words);
531        Ok(Self {
532            blocks: metadata_entries,
533            message_trigram_words: message_trigram_words.into_boxed_slice(),
534            message_trigram_union,
535            message_trigram_intersection,
536            partition_blocks,
537            term_postings,
538            field_postings,
539        })
540    }
541
542    /// Returns the immutable block directory.
543    #[must_use]
544    pub fn blocks(&self) -> &[QueryBlockMetadata] {
545        &self.blocks
546    }
547
548    /// Heap bytes occupied by record-ordinal arrays and run tables.
549    ///
550    /// This excludes hash-table buckets and interned term/field strings.
551    #[must_use]
552    pub fn posting_storage_bytes(&self) -> usize {
553        self.term_postings
554            .values()
555            .flat_map(HashMap::values)
556            .flatten()
557            .chain(
558                self.field_postings
559                    .values()
560                    .flat_map(HashMap::values)
561                    .flat_map(HashMap::values)
562                    .flatten(),
563            )
564            .map(|posting| posting.record_ordinals.storage_bytes())
565            .sum()
566    }
567
568    /// Heap bytes occupied by block-level message trigram rejection filters.
569    #[must_use]
570    pub fn message_trigram_filter_bytes(&self) -> usize {
571        self.message_trigram_words
572            .len()
573            .saturating_mul(size_of::<u64>())
574    }
575
576    /// Logical number of record ordinals represented by all postings.
577    #[must_use]
578    pub fn posting_cardinality(&self) -> usize {
579        self.term_postings
580            .values()
581            .flat_map(HashMap::values)
582            .flatten()
583            .chain(
584                self.field_postings
585                    .values()
586                    .flat_map(HashMap::values)
587                    .flat_map(HashMap::values)
588                    .flatten(),
589            )
590            .map(|posting| posting.record_ordinals.cardinality())
591            .sum()
592    }
593
594    /// Plans safe term/field candidates before payload reads and decoding.
595    ///
596    /// Posting-only queries may return exact hits. Queries containing residual
597    /// predicates return a superset. Always pass decoded records through
598    /// [`LogQuery::select`] before returning them to a caller. Offset and
599    /// timestamp ranges prune whole blocks here, while boundary records are
600    /// checked after selective decoding. A limit is applied during planning
601    /// only when the complete query can be answered safely by postings.
602    #[must_use]
603    pub fn candidate_hits(&self, query: &LogQuery) -> Vec<QueryHit> {
604        if query.limit == Some(0) || query.has_invalid_range() {
605            return Vec::new();
606        }
607        let required = query.required_index_constraints();
608        if required.impossible {
609            return Vec::new();
610        }
611        let Some(required_message_slots) =
612            self.prepare_required_message_trigrams(&required.message_literals)
613        else {
614            return Vec::new();
615        };
616        let mut constraints = Vec::<&[BlockPosting]>::with_capacity(
617            required.terms.len().saturating_add(required.fields.len()),
618        );
619        let partition_terms = self.term_postings.get(&query.topic_partition);
620        for term in required.terms {
621            let normalized = normalize_term(term);
622            let Some(postings) = partition_terms.and_then(|terms| terms.get(normalized.as_ref()))
623            else {
624                return Vec::new();
625            };
626            constraints.push(postings);
627        }
628        let partition_fields = self.field_postings.get(&query.topic_partition);
629        for (key, value) in required.fields {
630            let Some(postings) = partition_fields
631                .and_then(|keys| keys.get(key))
632                .and_then(|values| values.get(value))
633            else {
634                return Vec::new();
635            };
636            constraints.push(postings);
637        }
638
639        let mut candidate_blocks = if constraints.is_empty() {
640            self.partition_blocks
641                .get(&query.topic_partition)
642                .cloned()
643                .unwrap_or_default()
644        } else {
645            constraints.sort_unstable_by_key(|postings| postings.len());
646            let mut candidates = constraints[0]
647                .iter()
648                .map(|posting| posting.block_ordinal)
649                .collect::<Vec<_>>();
650            for postings in &constraints[1..] {
651                intersect_block_ordinals(&mut candidates, postings);
652                if candidates.is_empty() {
653                    return Vec::new();
654                }
655            }
656            candidates
657        };
658        candidate_blocks.retain(|ordinal| {
659            self.block(*ordinal)
660                .is_some_and(|metadata| block_overlaps(metadata, query))
661                && self.message_might_match(*ordinal, &required_message_slots)
662        });
663        if query.order == QueryOrder::NewestFirst {
664            candidate_blocks.reverse();
665        }
666
667        let safe_limit = query
668            .can_apply_index_limit()
669            .then_some(query.limit)
670            .flatten()
671            .unwrap_or(usize::MAX);
672        let mut hits = Vec::new();
673        for block_ordinal in candidate_blocks {
674            let Some(metadata) = self.block(block_ordinal) else {
675                continue;
676            };
677            let mut record_constraints = Vec::<&PostingList>::with_capacity(constraints.len());
678            for constraint in &constraints {
679                let Ok(position) = constraint
680                    .binary_search_by_key(&block_ordinal, |posting| posting.block_ordinal)
681                else {
682                    record_constraints.clear();
683                    break;
684                };
685                record_constraints.push(&constraint[position].record_ordinals);
686            }
687            let remaining = safe_limit.saturating_sub(hits.len());
688            let newest_first = query.order == QueryOrder::NewestFirst;
689            let record_ordinals = if record_constraints.is_empty() {
690                if constraints.is_empty() {
691                    if newest_first {
692                        (0..metadata.record_count).rev().take(remaining).collect()
693                    } else {
694                        (0..metadata.record_count).take(remaining).collect()
695                    }
696                } else {
697                    continue;
698                }
699            } else if record_constraints.len() == 1 {
700                record_constraints[0].take_ordered(newest_first, remaining)
701            } else {
702                record_constraints.sort_unstable_by_key(|postings| postings.cardinality());
703                if remaining.saturating_mul(8) < record_constraints[0].cardinality() {
704                    intersect_postings_limited(&record_constraints, newest_first, remaining)
705                } else {
706                    let mut candidates = record_constraints[0].to_vec();
707                    for postings in &record_constraints[1..] {
708                        intersect_posting(&mut candidates, postings);
709                        if candidates.is_empty() {
710                            break;
711                        }
712                    }
713                    if newest_first {
714                        candidates.reverse();
715                    }
716                    candidates.truncate(remaining);
717                    candidates
718                }
719            };
720            hits.extend(
721                record_ordinals
722                    .into_iter()
723                    .take(remaining)
724                    .map(|record_ordinal| QueryHit {
725                        block_ordinal,
726                        record_ordinal,
727                    }),
728            );
729            if hits.len() >= safe_limit {
730                break;
731            }
732        }
733        hits
734    }
735
736    /// Returns candidate block ordinals in deterministic offset order.
737    ///
738    /// This is the bounded entry point for sealed queries that require
739    /// post-decode filtering. Call [`Self::candidate_hits_in_block`] for one
740    /// returned block at a time, decode and filter those records, and stop once
741    /// an offset-ordered page is complete.
742    #[must_use]
743    pub fn candidate_blocks(&self, query: &LogQuery) -> Vec<u32> {
744        if query.limit == Some(0) || query.has_invalid_range() {
745            return Vec::new();
746        }
747        let required = query.required_index_constraints();
748        if required.impossible {
749            return Vec::new();
750        }
751        let Some(required_message_slots) =
752            self.prepare_required_message_trigrams(&required.message_literals)
753        else {
754            return Vec::new();
755        };
756        let mut constraints = Vec::<&[BlockPosting]>::with_capacity(
757            required.terms.len().saturating_add(required.fields.len()),
758        );
759        let partition_terms = self.term_postings.get(&query.topic_partition);
760        for term in required.terms {
761            let normalized = normalize_term(term);
762            let Some(postings) = partition_terms.and_then(|terms| terms.get(normalized.as_ref()))
763            else {
764                return Vec::new();
765            };
766            constraints.push(postings);
767        }
768        let partition_fields = self.field_postings.get(&query.topic_partition);
769        for (key, value) in required.fields {
770            let Some(postings) = partition_fields
771                .and_then(|keys| keys.get(key))
772                .and_then(|values| values.get(value))
773            else {
774                return Vec::new();
775            };
776            constraints.push(postings);
777        }
778
779        let mut blocks = if constraints.is_empty() {
780            self.partition_blocks
781                .get(&query.topic_partition)
782                .cloned()
783                .unwrap_or_default()
784        } else {
785            constraints.sort_unstable_by_key(|postings| postings.len());
786            let mut blocks = constraints[0]
787                .iter()
788                .map(|posting| posting.block_ordinal)
789                .collect::<Vec<_>>();
790            for postings in &constraints[1..] {
791                intersect_block_ordinals(&mut blocks, postings);
792                if blocks.is_empty() {
793                    return blocks;
794                }
795            }
796            blocks
797        };
798        blocks.retain(|ordinal| {
799            self.block(*ordinal)
800                .is_some_and(|metadata| block_overlaps(metadata, query))
801                && self.message_might_match(*ordinal, &required_message_slots)
802        });
803        blocks.sort_unstable_by_key(|ordinal| {
804            self.block(*ordinal).map(|metadata| metadata.first_offset)
805        });
806        if query.order == QueryOrder::NewestFirst {
807            blocks.reverse();
808        }
809        blocks
810    }
811
812    /// Plans the unbounded candidate records inside one selected block.
813    ///
814    /// This method deliberately ignores the query's global limit. The caller
815    /// must decode these candidates, apply [`LogQuery::matches`], and enforce
816    /// the limit only after residual filtering.
817    #[must_use]
818    pub fn candidate_hits_in_block(&self, query: &LogQuery, block_ordinal: u32) -> Vec<QueryHit> {
819        if query.limit == Some(0) || query.has_invalid_range() {
820            return Vec::new();
821        }
822        let Some(metadata) = self.block(block_ordinal) else {
823            return Vec::new();
824        };
825        if metadata.topic_partition != query.topic_partition || !block_overlaps(metadata, query) {
826            return Vec::new();
827        }
828        let required = query.required_index_constraints();
829        if required.impossible {
830            return Vec::new();
831        }
832        let Some(required_message_slots) =
833            self.prepare_required_message_trigrams(&required.message_literals)
834        else {
835            return Vec::new();
836        };
837        if !self.message_might_match(block_ordinal, &required_message_slots) {
838            return Vec::new();
839        }
840        let mut constraints = Vec::<&PostingList>::with_capacity(
841            required.terms.len().saturating_add(required.fields.len()),
842        );
843        let partition_terms = self.term_postings.get(&query.topic_partition);
844        for term in required.terms {
845            let normalized = normalize_term(term);
846            let Some(posting) = partition_terms
847                .and_then(|terms| terms.get(normalized.as_ref()))
848                .and_then(|postings| posting_for_block(postings, block_ordinal))
849            else {
850                return Vec::new();
851            };
852            constraints.push(posting);
853        }
854        let partition_fields = self.field_postings.get(&query.topic_partition);
855        for (key, value) in required.fields {
856            let Some(posting) = partition_fields
857                .and_then(|keys| keys.get(key))
858                .and_then(|values| values.get(value))
859                .and_then(|postings| posting_for_block(postings, block_ordinal))
860            else {
861                return Vec::new();
862            };
863            constraints.push(posting);
864        }
865
866        let newest_first = query.order == QueryOrder::NewestFirst;
867        let mut record_ordinals = if constraints.is_empty() {
868            (0..metadata.record_count).collect::<Vec<_>>()
869        } else {
870            constraints.sort_unstable_by_key(|posting| posting.cardinality());
871            let mut record_ordinals = constraints[0].to_vec();
872            for posting in &constraints[1..] {
873                intersect_posting(&mut record_ordinals, posting);
874                if record_ordinals.is_empty() {
875                    break;
876                }
877            }
878            record_ordinals
879        };
880        if newest_first {
881            record_ordinals.reverse();
882        }
883        record_ordinals
884            .into_iter()
885            .map(|record_ordinal| QueryHit {
886                block_ordinal,
887                record_ordinal,
888            })
889            .collect()
890    }
891
892    /// Encodes the complete immutable directory with hybrid delta/run postings.
893    pub fn encode(&self) -> TelemetryResult<Vec<u8>> {
894        let mut encoded = Vec::new();
895        encoded.extend_from_slice(QUERY_INDEX_MAGIC);
896        write_varint(
897            u64::try_from(self.blocks.len()).map_err(|_| TelemetryError::RecordTooLarge)?,
898            &mut encoded,
899        );
900        for (block_index, metadata) in self.blocks.iter().enumerate() {
901            write_varint(u64::from(metadata.block_ordinal), &mut encoded);
902            encoded.extend_from_slice(&metadata.topic_partition.topic_id.get().to_le_bytes());
903            encoded.extend_from_slice(&metadata.topic_partition.partition_id.get().to_le_bytes());
904            write_varint(metadata.first_offset.get(), &mut encoded);
905            write_varint(metadata.last_offset.get(), &mut encoded);
906            write_varint(metadata.min_timestamp_unix_nanos, &mut encoded);
907            write_varint(metadata.max_timestamp_unix_nanos, &mut encoded);
908            write_varint(u64::from(metadata.record_count), &mut encoded);
909            let trigram_start = block_index.saturating_mul(MESSAGE_TRIGRAM_FILTER_WORDS);
910            for word in &self.message_trigram_words
911                [trigram_start..trigram_start + MESSAGE_TRIGRAM_FILTER_WORDS]
912            {
913                encoded.extend_from_slice(&word.to_le_bytes());
914            }
915
916            let mut terms = self
917                .term_postings
918                .get(&metadata.topic_partition)
919                .into_iter()
920                .flat_map(HashMap::iter)
921                .filter_map(|(term, postings)| {
922                    posting_for_block(postings, metadata.block_ordinal)
923                        .map(|posting| (term.as_ref(), posting))
924                })
925                .collect::<Vec<_>>();
926            terms.sort_unstable_by(|left, right| left.0.cmp(right.0));
927            write_varint(
928                u64::try_from(terms.len()).map_err(|_| TelemetryError::RecordTooLarge)?,
929                &mut encoded,
930            );
931            for (term, posting) in terms {
932                append_bytes(term.as_bytes(), &mut encoded)?;
933                encode_posting(posting, &mut encoded)?;
934            }
935
936            let mut fields = self
937                .field_postings
938                .get(&metadata.topic_partition)
939                .into_iter()
940                .flat_map(HashMap::iter)
941                .flat_map(|(key, values)| {
942                    values.iter().filter_map(move |(value, postings)| {
943                        posting_for_block(postings, metadata.block_ordinal)
944                            .map(|posting| (key.as_ref(), value.as_ref(), posting))
945                    })
946                })
947                .collect::<Vec<_>>();
948            fields.sort_unstable_by(|left, right| {
949                left.0.cmp(right.0).then_with(|| left.1.cmp(right.1))
950            });
951            write_varint(
952                u64::try_from(fields.len()).map_err(|_| TelemetryError::RecordTooLarge)?,
953                &mut encoded,
954            );
955            for (key, value, posting) in fields {
956                append_bytes(key.as_bytes(), &mut encoded)?;
957                append_bytes(value.as_bytes(), &mut encoded)?;
958                encode_posting(posting, &mut encoded)?;
959            }
960        }
961        Ok(encoded)
962    }
963
964    /// Decodes and validates one immutable query directory.
965    pub fn decode(encoded: &[u8]) -> TelemetryResult<Self> {
966        if encoded.get(..QUERY_INDEX_MAGIC.len()) != Some(QUERY_INDEX_MAGIC) {
967            return Err(TelemetryError::InvalidBlockEncoding(
968                "missing query index magic",
969            ));
970        }
971        let mut cursor = QUERY_INDEX_MAGIC.len();
972        let block_count = read_usize(encoded, &mut cursor)?;
973        ensure_count(block_count, encoded.len().saturating_sub(cursor))?;
974        let mut blocks = Vec::with_capacity(block_count);
975        for _ in 0..block_count {
976            let block_ordinal = read_u32(encoded, &mut cursor)?;
977            let topic_end = cursor
978                .checked_add(16)
979                .ok_or(TelemetryError::InvalidBlockEncoding("query topic overflow"))?;
980            let topic_id = TopicId::new(u128::from_le_bytes(
981                encoded
982                    .get(cursor..topic_end)
983                    .ok_or(TelemetryError::InvalidBlockEncoding(
984                        "truncated query topic",
985                    ))?
986                    .try_into()
987                    .map_err(|_| TelemetryError::InvalidBlockEncoding("invalid query topic"))?,
988            ));
989            cursor = topic_end;
990            let partition_end =
991                cursor
992                    .checked_add(4)
993                    .ok_or(TelemetryError::InvalidBlockEncoding(
994                        "query partition overflow",
995                    ))?;
996            let partition_id = LogicalPartitionId::new(u32::from_le_bytes(
997                encoded
998                    .get(cursor..partition_end)
999                    .ok_or(TelemetryError::InvalidBlockEncoding(
1000                        "truncated query partition",
1001                    ))?
1002                    .try_into()
1003                    .map_err(|_| TelemetryError::InvalidBlockEncoding("invalid query partition"))?,
1004            ));
1005            cursor = partition_end;
1006            let first_offset = LogicalOffset::new(read_varint(encoded, &mut cursor)?);
1007            let last_offset = LogicalOffset::new(read_varint(encoded, &mut cursor)?);
1008            let min_timestamp_unix_nanos = read_varint(encoded, &mut cursor)?;
1009            let max_timestamp_unix_nanos = read_varint(encoded, &mut cursor)?;
1010            let record_count = read_u32(encoded, &mut cursor)?;
1011            let trigram_end = cursor.checked_add(MESSAGE_TRIGRAM_FILTER_BYTES).ok_or(
1012                TelemetryError::InvalidBlockEncoding("message trigram filter overflow"),
1013            )?;
1014            let message_trigrams =
1015                MessageTrigramFilter::from_bytes(encoded.get(cursor..trigram_end).ok_or(
1016                    TelemetryError::InvalidBlockEncoding("truncated message trigram filter"),
1017                )?)?;
1018            cursor = trigram_end;
1019            let term_count = read_usize(encoded, &mut cursor)?;
1020            ensure_count(term_count, encoded.len().saturating_sub(cursor))?;
1021            let mut term_postings = HashMap::with_capacity(term_count);
1022            for _ in 0..term_count {
1023                let term = decode_text(read_bytes(encoded, &mut cursor)?)?;
1024                let posting = decode_posting(encoded, &mut cursor, record_count)?;
1025                if term_postings.insert(term, posting).is_some() {
1026                    return Err(TelemetryError::InvalidBlockEncoding(
1027                        "duplicate indexed term",
1028                    ));
1029                }
1030            }
1031            let field_count = read_usize(encoded, &mut cursor)?;
1032            ensure_count(field_count, encoded.len().saturating_sub(cursor))?;
1033            let mut field_postings = HashMap::<Arc<str>, HashMap<Arc<str>, PostingList>>::new();
1034            for _ in 0..field_count {
1035                let key = decode_text(read_bytes(encoded, &mut cursor)?)?;
1036                let value = decode_text(read_bytes(encoded, &mut cursor)?)?;
1037                let posting = decode_posting(encoded, &mut cursor, record_count)?;
1038                if field_postings
1039                    .entry(key)
1040                    .or_default()
1041                    .insert(value, posting)
1042                    .is_some()
1043                {
1044                    return Err(TelemetryError::InvalidBlockEncoding(
1045                        "duplicate indexed field",
1046                    ));
1047                }
1048            }
1049            blocks.push((
1050                QueryBlockMetadata {
1051                    block_ordinal,
1052                    topic_partition: TopicPartition::new(topic_id, partition_id),
1053                    first_offset,
1054                    last_offset,
1055                    min_timestamp_unix_nanos,
1056                    max_timestamp_unix_nanos,
1057                    record_count,
1058                },
1059                BlockQueryIndex {
1060                    record_count,
1061                    message_trigrams,
1062                    term_postings,
1063                    field_postings,
1064                },
1065            ));
1066        }
1067        if cursor != encoded.len() {
1068            return Err(TelemetryError::InvalidBlockEncoding(
1069                "trailing query index bytes",
1070            ));
1071        }
1072        Self::from_blocks(blocks)
1073    }
1074
1075    /// Encodes and wraps the query directory in one zstd frame.
1076    pub fn encode_compressed(&self, level: i32) -> TelemetryResult<Vec<u8>> {
1077        let uncompressed = self.encode()?;
1078        let compressed = zstd::bulk::compress(&uncompressed, level)
1079            .map_err(|error| TelemetryError::CompressionFailed(error.to_string()))?;
1080        let mut encoded =
1081            Vec::with_capacity(COMPRESSED_QUERY_INDEX_MAGIC.len() + 8 + compressed.len());
1082        encoded.extend_from_slice(COMPRESSED_QUERY_INDEX_MAGIC);
1083        encoded.extend_from_slice(
1084            &u64::try_from(uncompressed.len())
1085                .map_err(|_| TelemetryError::RecordTooLarge)?
1086                .to_le_bytes(),
1087        );
1088        encoded.extend_from_slice(&compressed);
1089        Ok(encoded)
1090    }
1091
1092    /// Decodes a zstd-wrapped immutable query directory.
1093    pub fn decode_compressed(encoded: &[u8]) -> TelemetryResult<Self> {
1094        if encoded.get(..COMPRESSED_QUERY_INDEX_MAGIC.len()) != Some(COMPRESSED_QUERY_INDEX_MAGIC) {
1095            return Err(TelemetryError::InvalidBlockEncoding(
1096                "missing compressed query index magic",
1097            ));
1098        }
1099        let length_end = COMPRESSED_QUERY_INDEX_MAGIC.len() + 8;
1100        let uncompressed_len = usize::try_from(u64::from_le_bytes(
1101            encoded
1102                .get(COMPRESSED_QUERY_INDEX_MAGIC.len()..length_end)
1103                .ok_or(TelemetryError::InvalidBlockEncoding(
1104                    "truncated query index length",
1105                ))?
1106                .try_into()
1107                .map_err(|_| TelemetryError::InvalidBlockEncoding("invalid query index length"))?,
1108        ))
1109        .map_err(|_| {
1110            TelemetryError::InvalidBlockEncoding("query index length does not fit usize")
1111        })?;
1112        let uncompressed = zstd::bulk::decompress(
1113            encoded
1114                .get(length_end..)
1115                .ok_or(TelemetryError::InvalidBlockEncoding(
1116                    "truncated compressed query index",
1117                ))?,
1118            uncompressed_len,
1119        )
1120        .map_err(|_| TelemetryError::InvalidBlockEncoding("invalid compressed query index"))?;
1121        Self::decode(&uncompressed)
1122    }
1123
1124    fn block(&self, block_ordinal: u32) -> Option<&QueryBlockMetadata> {
1125        self.blocks
1126            .binary_search_by_key(&block_ordinal, |metadata| metadata.block_ordinal)
1127            .ok()
1128            .and_then(|index| self.blocks.get(index))
1129    }
1130
1131    fn message_might_match(&self, block_ordinal: u32, required_slots: &[usize]) -> bool {
1132        let Ok(index) = self
1133            .blocks
1134            .binary_search_by_key(&block_ordinal, |metadata| metadata.block_ordinal)
1135        else {
1136            return false;
1137        };
1138        let start = index.saturating_mul(MESSAGE_TRIGRAM_FILTER_WORDS);
1139        required_slots.iter().all(|slot| {
1140            self.message_trigram_words[start + *slot / u64::BITS as usize]
1141                & (1u64 << (*slot % u64::BITS as usize))
1142                != 0
1143        })
1144    }
1145
1146    fn prepare_required_message_trigrams(&self, literals: &[&str]) -> Option<Vec<usize>> {
1147        let mut slots = required_message_trigram_slots(literals);
1148        if !self.message_trigram_union.might_contain_all(&slots) {
1149            return None;
1150        }
1151        slots.retain(|slot| {
1152            !self
1153                .message_trigram_intersection
1154                .might_contain_all(&[*slot])
1155        });
1156        Some(slots)
1157    }
1158}
1159
1160fn aggregate_message_trigrams(words: &[u64]) -> (MessageTrigramFilter, MessageTrigramFilter) {
1161    let mut union = MessageTrigramFilter::new();
1162    let mut intersection = MessageTrigramFilter {
1163        words: vec![u64::MAX; MESSAGE_TRIGRAM_FILTER_WORDS].into_boxed_slice(),
1164    };
1165    if words.is_empty() {
1166        intersection.words.fill(0);
1167        return (union, intersection);
1168    }
1169    for filter in words.chunks_exact(MESSAGE_TRIGRAM_FILTER_WORDS) {
1170        for ((union, intersection), observed) in union
1171            .words
1172            .iter_mut()
1173            .zip(intersection.words.iter_mut())
1174            .zip(filter.iter())
1175        {
1176            *union |= *observed;
1177            *intersection &= *observed;
1178        }
1179    }
1180    (union, intersection)
1181}
1182
1183fn block_overlaps(metadata: &QueryBlockMetadata, query: &LogQuery) -> bool {
1184    query
1185        .start_offset
1186        .is_none_or(|start| metadata.last_offset >= start)
1187        && query
1188            .end_offset
1189            .is_none_or(|end| metadata.first_offset < end)
1190        && query
1191            .start_timestamp_unix_nanos
1192            .is_none_or(|start| metadata.max_timestamp_unix_nanos >= start)
1193        && query
1194            .end_timestamp_unix_nanos
1195            .is_none_or(|end| metadata.min_timestamp_unix_nanos < end)
1196}
1197
1198fn posting_for_block(postings: &[BlockPosting], block_ordinal: u32) -> Option<&PostingList> {
1199    postings
1200        .binary_search_by_key(&block_ordinal, |posting| posting.block_ordinal)
1201        .ok()
1202        .map(|index| &postings[index].record_ordinals)
1203}
1204
1205fn intersect_block_ordinals(candidates: &mut Vec<u32>, postings: &[BlockPosting]) {
1206    let mut candidate_index = 0usize;
1207    let mut posting_index = 0usize;
1208    let mut write_index = 0usize;
1209    while candidate_index < candidates.len() && posting_index < postings.len() {
1210        match candidates[candidate_index].cmp(&postings[posting_index].block_ordinal) {
1211            std::cmp::Ordering::Less => candidate_index += 1,
1212            std::cmp::Ordering::Greater => posting_index += 1,
1213            std::cmp::Ordering::Equal => {
1214                candidates[write_index] = candidates[candidate_index];
1215                write_index += 1;
1216                candidate_index += 1;
1217                posting_index += 1;
1218            }
1219        }
1220    }
1221    candidates.truncate(write_index);
1222}
1223
1224fn intersect_u32(candidates: &mut Vec<u32>, postings: &[u32]) {
1225    if candidates.len().saturating_mul(8) < postings.len() {
1226        let mut posting_index = 0usize;
1227        let mut write_index = 0usize;
1228        for candidate_index in 0..candidates.len() {
1229            let candidate = candidates[candidate_index];
1230            posting_index +=
1231                postings[posting_index..].partition_point(|posting| *posting < candidate);
1232            let Some(posting) = postings.get(posting_index) else {
1233                break;
1234            };
1235            if *posting == candidate {
1236                candidates[write_index] = candidate;
1237                write_index += 1;
1238                posting_index += 1;
1239            }
1240        }
1241        candidates.truncate(write_index);
1242        return;
1243    }
1244    let mut candidate_index = 0usize;
1245    let mut posting_index = 0usize;
1246    let mut write_index = 0usize;
1247    while candidate_index < candidates.len() && posting_index < postings.len() {
1248        match candidates[candidate_index].cmp(&postings[posting_index]) {
1249            std::cmp::Ordering::Less => candidate_index += 1,
1250            std::cmp::Ordering::Greater => posting_index += 1,
1251            std::cmp::Ordering::Equal => {
1252                candidates[write_index] = candidates[candidate_index];
1253                write_index += 1;
1254                candidate_index += 1;
1255                posting_index += 1;
1256            }
1257        }
1258    }
1259    candidates.truncate(write_index);
1260}
1261
1262fn intersect_posting(candidates: &mut Vec<u32>, posting: &PostingList) {
1263    match posting {
1264        PostingList::Ordinals(postings) => intersect_u32(candidates, postings),
1265        PostingList::Runs { runs, .. } => {
1266            let mut candidate_index = 0usize;
1267            let mut run_index = 0usize;
1268            let mut write_index = 0usize;
1269            while candidate_index < candidates.len() && run_index < runs.len() {
1270                let candidate = candidates[candidate_index];
1271                let run = runs[run_index];
1272                let run_end = run.start + run.length;
1273                if candidate < run.start {
1274                    candidate_index += 1;
1275                } else if candidate >= run_end {
1276                    run_index += 1;
1277                } else {
1278                    candidates[write_index] = candidate;
1279                    write_index += 1;
1280                    candidate_index += 1;
1281                }
1282            }
1283            candidates.truncate(write_index);
1284        }
1285    }
1286}
1287
1288fn intersect_postings_limited(
1289    postings: &[&PostingList],
1290    newest_first: bool,
1291    limit: usize,
1292) -> Vec<u32> {
1293    let mut matches = Vec::with_capacity(limit);
1294    let mut observe = |ordinal| {
1295        if postings[1..]
1296            .iter()
1297            .all(|posting| posting.contains(ordinal))
1298        {
1299            matches.push(ordinal);
1300        }
1301        matches.len() == limit
1302    };
1303    match postings[0] {
1304        PostingList::Ordinals(ordinals) => {
1305            if newest_first {
1306                for ordinal in ordinals.iter().rev().copied() {
1307                    if observe(ordinal) {
1308                        break;
1309                    }
1310                }
1311            } else {
1312                for ordinal in ordinals.iter().copied() {
1313                    if observe(ordinal) {
1314                        break;
1315                    }
1316                }
1317            }
1318        }
1319        PostingList::Runs { runs, .. } => {
1320            if newest_first {
1321                'outer_newest: for run in runs.iter().rev() {
1322                    for ordinal in (run.start..run.start + run.length).rev() {
1323                        if observe(ordinal) {
1324                            break 'outer_newest;
1325                        }
1326                    }
1327                }
1328            } else {
1329                'outer_oldest: for run in runs {
1330                    for ordinal in run.start..run.start + run.length {
1331                        if observe(ordinal) {
1332                            break 'outer_oldest;
1333                        }
1334                    }
1335                }
1336            }
1337        }
1338    }
1339    matches
1340}
1341
1342fn posting_runs(posting: &[u32]) -> Vec<OrdinalRun> {
1343    let mut runs = Vec::<OrdinalRun>::new();
1344    for ordinal in posting.iter().copied() {
1345        if let Some(run) = runs.last_mut()
1346            && run.start.saturating_add(run.length) == ordinal
1347        {
1348            run.length = run.length.saturating_add(1);
1349        } else {
1350            runs.push(OrdinalRun {
1351                start: ordinal,
1352                length: 1,
1353            });
1354        }
1355    }
1356    runs
1357}
1358
1359fn encode_posting(posting: &PostingList, encoded: &mut Vec<u8>) -> TelemetryResult<()> {
1360    if let PostingList::Runs { runs, .. } = posting {
1361        return encode_run_posting(runs, encoded);
1362    }
1363    let PostingList::Ordinals(posting) = posting else {
1364        unreachable!("run postings return above");
1365    };
1366    let mut delta = Vec::new();
1367    delta.push(DELTA_POSTING);
1368    write_varint(
1369        u64::try_from(posting.len()).map_err(|_| TelemetryError::RecordTooLarge)?,
1370        &mut delta,
1371    );
1372    let mut previous = 0u32;
1373    for (index, ordinal) in posting.iter().copied().enumerate() {
1374        if index > 0 && ordinal <= previous {
1375            return Err(TelemetryError::InvalidBlockEncoding(
1376                "query posting is not ordered",
1377            ));
1378        }
1379        write_varint(u64::from(ordinal - previous), &mut delta);
1380        previous = ordinal;
1381    }
1382    encoded.extend_from_slice(&delta);
1383    Ok(())
1384}
1385
1386fn encode_run_posting(runs: &[OrdinalRun], encoded: &mut Vec<u8>) -> TelemetryResult<()> {
1387    if runs.is_empty() {
1388        return Err(TelemetryError::InvalidBlockEncoding("empty query posting"));
1389    }
1390    encoded.push(RUN_POSTING);
1391    write_varint(
1392        u64::try_from(runs.len()).map_err(|_| TelemetryError::RecordTooLarge)?,
1393        encoded,
1394    );
1395    let mut previous_end = 0u32;
1396    for run in runs {
1397        write_varint(u64::from(run.start - previous_end), encoded);
1398        write_varint(u64::from(run.length), encoded);
1399        previous_end = run.start.saturating_add(run.length);
1400    }
1401    Ok(())
1402}
1403
1404fn decode_posting(
1405    encoded: &[u8],
1406    cursor: &mut usize,
1407    record_count: u32,
1408) -> TelemetryResult<PostingList> {
1409    match read_byte(encoded, cursor)? {
1410        DELTA_POSTING => {
1411            let count = read_usize(encoded, cursor)?;
1412            ensure_count(count, encoded.len().saturating_sub(*cursor))?;
1413            let mut posting = Vec::with_capacity(count);
1414            let mut previous = 0u32;
1415            for index in 0..count {
1416                let delta = read_u32(encoded, cursor)?;
1417                let ordinal =
1418                    previous
1419                        .checked_add(delta)
1420                        .ok_or(TelemetryError::InvalidBlockEncoding(
1421                            "query posting delta overflow",
1422                        ))?;
1423                if ordinal >= record_count || (index > 0 && ordinal <= previous) {
1424                    return Err(TelemetryError::InvalidBlockEncoding(
1425                        "invalid query posting ordinal",
1426                    ));
1427                }
1428                posting.push(ordinal);
1429                previous = ordinal;
1430            }
1431            if posting.is_empty() {
1432                return Err(TelemetryError::InvalidBlockEncoding("empty query posting"));
1433            }
1434            Ok(PostingList::Ordinals(posting))
1435        }
1436        RUN_POSTING => {
1437            let run_count = read_usize(encoded, cursor)?;
1438            ensure_count(run_count, encoded.len().saturating_sub(*cursor))?;
1439            let mut runs = Vec::with_capacity(run_count);
1440            let mut cardinality = 0usize;
1441            let mut previous_end = 0u32;
1442            for _ in 0..run_count {
1443                let start = previous_end.checked_add(read_u32(encoded, cursor)?).ok_or(
1444                    TelemetryError::InvalidBlockEncoding("query posting run overflow"),
1445                )?;
1446                let length = read_u32(encoded, cursor)?;
1447                let end = start
1448                    .checked_add(length)
1449                    .ok_or(TelemetryError::InvalidBlockEncoding(
1450                        "query posting run overflow",
1451                    ))?;
1452                if length == 0 || end > record_count {
1453                    return Err(TelemetryError::InvalidBlockEncoding(
1454                        "invalid query posting run",
1455                    ));
1456                }
1457                cardinality = cardinality
1458                    .checked_add(usize::try_from(length).map_err(|_| {
1459                        TelemetryError::InvalidBlockEncoding(
1460                            "query posting cardinality does not fit usize",
1461                        )
1462                    })?)
1463                    .ok_or(TelemetryError::InvalidBlockEncoding(
1464                        "query posting cardinality overflow",
1465                    ))?;
1466                runs.push(OrdinalRun { start, length });
1467                previous_end = end;
1468            }
1469            if runs.is_empty() {
1470                return Err(TelemetryError::InvalidBlockEncoding("empty query posting"));
1471            }
1472            Ok(PostingList::Runs { runs, cardinality })
1473        }
1474        _ => Err(TelemetryError::InvalidBlockEncoding(
1475            "unknown query posting encoding",
1476        )),
1477    }
1478}
1479
1480fn normalize_term(term: &str) -> Cow<'_, str> {
1481    if term.chars().any(char::is_uppercase) {
1482        Cow::Owned(term.to_lowercase())
1483    } else {
1484        Cow::Borrowed(term)
1485    }
1486}
1487
1488fn append_bytes(bytes: &[u8], encoded: &mut Vec<u8>) -> TelemetryResult<()> {
1489    write_varint(
1490        u64::try_from(bytes.len()).map_err(|_| TelemetryError::RecordTooLarge)?,
1491        encoded,
1492    );
1493    encoded.extend_from_slice(bytes);
1494    Ok(())
1495}
1496
1497fn write_varint(mut value: u64, encoded: &mut Vec<u8>) {
1498    while value >= 0x80 {
1499        encoded.push((value as u8 & 0x7f) | 0x80);
1500        value >>= 7;
1501    }
1502    encoded.push(value as u8);
1503}
1504
1505fn read_varint(encoded: &[u8], cursor: &mut usize) -> TelemetryResult<u64> {
1506    let mut value = 0u64;
1507    let mut shift = 0u32;
1508    loop {
1509        let byte = read_byte(encoded, cursor)?;
1510        let payload = u64::from(byte & 0x7f);
1511        if shift > 63 || (shift == 63 && payload > 1) {
1512            return Err(TelemetryError::InvalidBlockEncoding(
1513                "query index varint overflow",
1514            ));
1515        }
1516        value |= payload << shift;
1517        if byte & 0x80 == 0 {
1518            return Ok(value);
1519        }
1520        shift = shift.saturating_add(7);
1521        if shift > 63 {
1522            return Err(TelemetryError::InvalidBlockEncoding(
1523                "query index varint too long",
1524            ));
1525        }
1526    }
1527}
1528
1529fn read_byte(encoded: &[u8], cursor: &mut usize) -> TelemetryResult<u8> {
1530    let byte = *encoded
1531        .get(*cursor)
1532        .ok_or(TelemetryError::InvalidBlockEncoding(
1533            "truncated query index",
1534        ))?;
1535    *cursor = cursor
1536        .checked_add(1)
1537        .ok_or(TelemetryError::InvalidBlockEncoding(
1538            "query index cursor overflow",
1539        ))?;
1540    Ok(byte)
1541}
1542
1543fn read_u32(encoded: &[u8], cursor: &mut usize) -> TelemetryResult<u32> {
1544    u32::try_from(read_varint(encoded, cursor)?)
1545        .map_err(|_| TelemetryError::InvalidBlockEncoding("query index value does not fit u32"))
1546}
1547
1548fn read_usize(encoded: &[u8], cursor: &mut usize) -> TelemetryResult<usize> {
1549    usize::try_from(read_varint(encoded, cursor)?)
1550        .map_err(|_| TelemetryError::InvalidBlockEncoding("query index value does not fit usize"))
1551}
1552
1553fn read_bytes<'a>(encoded: &'a [u8], cursor: &mut usize) -> TelemetryResult<&'a [u8]> {
1554    let length = read_usize(encoded, cursor)?;
1555    let end = cursor
1556        .checked_add(length)
1557        .ok_or(TelemetryError::InvalidBlockEncoding(
1558            "query index byte length overflow",
1559        ))?;
1560    let bytes = encoded
1561        .get(*cursor..end)
1562        .ok_or(TelemetryError::InvalidBlockEncoding(
1563            "truncated query index bytes",
1564        ))?;
1565    *cursor = end;
1566    Ok(bytes)
1567}
1568
1569fn decode_text(bytes: &[u8]) -> TelemetryResult<Arc<str>> {
1570    std::str::from_utf8(bytes)
1571        .map(Arc::<str>::from)
1572        .map_err(|_| TelemetryError::InvalidBlockEncoding("query index text is not UTF-8"))
1573}
1574
1575fn ensure_count(count: usize, remaining: usize) -> TelemetryResult<()> {
1576    if count <= remaining {
1577        Ok(())
1578    } else {
1579        Err(TelemetryError::InvalidBlockEncoding(
1580            "query index count exceeds remaining bytes",
1581        ))
1582    }
1583}
1584
1585#[cfg(test)]
1586mod tests {
1587    use shard_stream_core::{ShardId, TopicPartition};
1588
1589    use super::*;
1590    use crate::{
1591        CaseSensitivity, CompressionCohortId, DurableLog, LogPredicate, LogStripe, MetadataField,
1592        NumericComparison, StripeConfig, TextMatchKind, TextMatcher, decode_structural_block,
1593        encode_structural_records,
1594    };
1595
1596    fn partition() -> TopicPartition {
1597        TopicPartition::new(TopicId::new(9), LogicalPartitionId::new(3))
1598    }
1599
1600    fn records(start: u64, count: u64) -> Vec<DurableLog> {
1601        (start..start + count)
1602            .map(|offset| {
1603                let mut message = format!("common request_id={offset}");
1604                if offset % 10 == 0 {
1605                    message.push_str(" medium");
1606                }
1607                if offset % 100 == 0 {
1608                    message.push_str(" rare");
1609                }
1610                DurableLog::new(
1611                    ShardId::new(1),
1612                    partition(),
1613                    LogicalOffset::new(offset),
1614                    offset * 10,
1615                    message,
1616                    CompressionCohortId::new(1),
1617                )
1618                .with_field("service", if offset % 2 == 0 { "api" } else { "worker" })
1619            })
1620            .collect()
1621    }
1622
1623    fn compatibility_records(count: u64) -> Vec<DurableLog> {
1624        (0..count)
1625            .map(|offset| {
1626                let message = match offset % 4 {
1627                    0 => format!("INFO request {offset} completed"),
1628                    1 => format!("ERROR request {offset} cannot access storage"),
1629                    2 => format!("WARN request {offset} timed out after 250ms"),
1630                    _ => format!("DEBUG heartbeat node-{offset}"),
1631                };
1632                DurableLog::new(
1633                    ShardId::new(1),
1634                    partition(),
1635                    LogicalOffset::new(offset),
1636                    (offset * 37 % count) * 100 + offset,
1637                    message,
1638                    CompressionCohortId::new(1),
1639                )
1640                .with_field(
1641                    "service",
1642                    match offset % 3 {
1643                        0 => "api",
1644                        1 => "worker",
1645                        _ => "storage",
1646                    },
1647                )
1648                .with_field("env", if offset % 5 == 0 { "dev" } else { "prod" })
1649                .with_field(
1650                    "status",
1651                    if offset % 4 == 1 {
1652                        "503"
1653                    } else if offset % 4 == 2 {
1654                        "429"
1655                    } else {
1656                        "200"
1657                    },
1658                )
1659            })
1660            .collect()
1661    }
1662
1663    fn compatibility_index(records: &[DurableLog], block_records: usize) -> PersistentQueryIndex {
1664        PersistentQueryIndex::from_blocks(
1665            records
1666                .chunks(block_records)
1667                .enumerate()
1668                .map(|(ordinal, records)| {
1669                    indexed_block(u32::try_from(ordinal).expect("ordinal fits"), records)
1670                })
1671                .collect(),
1672        )
1673        .expect("compatibility index builds")
1674    }
1675
1676    fn cold_matches(
1677        index: &PersistentQueryIndex,
1678        records: &[DurableLog],
1679        block_records: usize,
1680        query: &LogQuery,
1681    ) -> Vec<DurableLog> {
1682        let candidates = index.candidate_hits(query).into_iter().map(|hit| {
1683            let index = usize::try_from(hit.block_ordinal).expect("block fits") * block_records
1684                + usize::try_from(hit.record_ordinal).expect("record fits");
1685            records[index].clone()
1686        });
1687        query.select(candidates)
1688    }
1689
1690    fn indexed_block(
1691        block_ordinal: u32,
1692        records: &[DurableLog],
1693    ) -> (QueryBlockMetadata, BlockQueryIndex) {
1694        let (min_timestamp_unix_nanos, max_timestamp_unix_nanos) =
1695            records
1696                .iter()
1697                .fold((u64::MAX, 0), |(minimum, maximum), record| {
1698                    (
1699                        minimum.min(record.timestamp_unix_nanos),
1700                        maximum.max(record.timestamp_unix_nanos),
1701                    )
1702                });
1703        (
1704            QueryBlockMetadata {
1705                block_ordinal,
1706                topic_partition: partition(),
1707                first_offset: records.first().expect("records exist").record_ref.offset,
1708                last_offset: records.last().expect("records exist").record_ref.offset,
1709                min_timestamp_unix_nanos,
1710                max_timestamp_unix_nanos,
1711                record_count: u32::try_from(records.len()).expect("record count fits"),
1712            },
1713            BlockQueryIndex::build(records).expect("index builds"),
1714        )
1715    }
1716
1717    #[test]
1718    fn persistent_index_round_trips_and_preserves_exact_and_results() {
1719        let first = records(0, 1_000);
1720        let second = records(1_000, 1_000);
1721        let index = PersistentQueryIndex::from_blocks(vec![
1722            indexed_block(0, &first),
1723            indexed_block(1, &second),
1724        ])
1725        .expect("directory builds");
1726        let encoded = index.encode().expect("index encodes");
1727        assert_eq!(
1728            PersistentQueryIndex::decode(&encoded).expect("index decodes"),
1729            index
1730        );
1731        let compressed = index.encode_compressed(1).expect("index compresses");
1732        let decoded =
1733            PersistentQueryIndex::decode_compressed(&compressed).expect("index decompresses");
1734        let hits = decoded.candidate_hits(
1735            &LogQuery::new(partition())
1736                .with_term("COMMON")
1737                .with_term("rare")
1738                .with_field("service", "api"),
1739        );
1740        assert_eq!(
1741            hits,
1742            (0..20)
1743                .map(|index| QueryHit {
1744                    block_ordinal: u32::from(index >= 10),
1745                    record_ordinal: u32::try_from((index % 10) * 100).expect("ordinal fits"),
1746                })
1747                .collect::<Vec<_>>()
1748        );
1749    }
1750
1751    #[test]
1752    fn newest_limit_and_block_ranges_prune_candidates() {
1753        let first = records(0, 100);
1754        let second = records(100, 100);
1755        let index = PersistentQueryIndex::from_blocks(vec![
1756            indexed_block(4, &first),
1757            indexed_block(9, &second),
1758        ])
1759        .expect("directory builds");
1760        assert_eq!(
1761            index.candidate_hits(
1762                &LogQuery::new(partition())
1763                    .with_term("common")
1764                    .newest_first()
1765                    .with_limit(3)
1766            ),
1767            vec![
1768                QueryHit {
1769                    block_ordinal: 9,
1770                    record_ordinal: 99,
1771                },
1772                QueryHit {
1773                    block_ordinal: 9,
1774                    record_ordinal: 98,
1775                },
1776                QueryHit {
1777                    block_ordinal: 9,
1778                    record_ordinal: 97,
1779                },
1780            ]
1781        );
1782        let ranged = index.candidate_hits(
1783            &LogQuery::new(partition())
1784                .with_offset_range(LogicalOffset::new(100), LogicalOffset::new(200)),
1785        );
1786        assert_eq!(ranged.len(), 100);
1787        assert!(ranged.iter().all(|hit| hit.block_ordinal == 9));
1788    }
1789
1790    #[test]
1791    fn hybrid_posting_prefers_runs_for_dense_ordinals() {
1792        let posting = (0..10_000).collect::<Vec<_>>();
1793        let posting = PostingList::from_ordinals(posting.clone()).expect("posting builds");
1794        let mut encoded = Vec::new();
1795        encode_posting(&posting, &mut encoded).expect("posting encodes");
1796        assert_eq!(encoded[0], RUN_POSTING);
1797        let mut cursor = 0;
1798        assert_eq!(
1799            decode_posting(&encoded, &mut cursor, 10_000)
1800                .expect("posting decodes")
1801                .to_vec(),
1802            (0..10_000).collect::<Vec<_>>()
1803        );
1804        assert_eq!(cursor, encoded.len());
1805    }
1806
1807    #[test]
1808    fn duplicate_metadata_fields_are_indexed_once() {
1809        let record = DurableLog {
1810            fields: vec![
1811                MetadataField::new("service", "api"),
1812                MetadataField::new("service", "api"),
1813            ]
1814            .into(),
1815            ..records(0, 1).pop().expect("record exists")
1816        };
1817        let index = BlockQueryIndex::build(&[record]).expect("index builds");
1818        assert_eq!(index.field_postings["service"]["api"].to_vec(), vec![0]);
1819    }
1820
1821    #[test]
1822    fn dense_postings_remain_run_encoded_in_resident_index() {
1823        let records = records(0, 10_000);
1824        let index = PersistentQueryIndex::from_blocks(vec![indexed_block(0, &records)])
1825            .expect("directory builds");
1826        let common = &index.term_postings[&partition()]["common"][0].record_ordinals;
1827        assert_eq!(common.cardinality(), records.len());
1828        assert!(common.storage_bytes() < common.cardinality().saturating_mul(size_of::<u32>()) / 2);
1829        assert_eq!(
1830            index
1831                .candidate_hits(
1832                    &LogQuery::new(partition())
1833                        .with_term("common")
1834                        .newest_first()
1835                        .with_limit(100)
1836                )
1837                .len(),
1838            100
1839        );
1840        let limited_intersection = index.candidate_hits(
1841            &LogQuery::new(partition())
1842                .with_term("common")
1843                .with_field("service", "api")
1844                .newest_first()
1845                .with_limit(3),
1846        );
1847        assert_eq!(
1848            limited_intersection
1849                .iter()
1850                .map(|hit| hit.record_ordinal)
1851                .collect::<Vec<_>>(),
1852            vec![9_998, 9_996, 9_994]
1853        );
1854    }
1855
1856    #[test]
1857    fn hot_and_sealed_lookups_share_full_boolean_compatibility() {
1858        let records = compatibility_records(60);
1859        let index = compatibility_index(&records, 10);
1860        let decoded_blocks = records
1861            .chunks(10)
1862            .map(|records| {
1863                decode_structural_block(
1864                    &encode_structural_records(records).expect("structural block encodes"),
1865                )
1866                .expect("structural block decodes")
1867            })
1868            .collect::<Vec<_>>();
1869        let mut stripe =
1870            LogStripe::new(ShardId::new(1), StripeConfig::default()).expect("stripe opens");
1871        for record in records.iter().cloned() {
1872            stripe.apply_durable(record).expect("record indexes");
1873        }
1874
1875        let message_regex =
1876            LogPredicate::message_regex("cannot|timed out", CaseSensitivity::Insensitive)
1877                .expect("regex compiles");
1878        let service_regex =
1879            LogPredicate::field_regex("service", "^(api|storage)$", CaseSensitivity::Sensitive)
1880                .expect("regex compiles");
1881        let queries = vec![
1882            LogQuery::new(partition())
1883                .where_predicate(LogPredicate::and(vec![
1884                    LogPredicate::or(vec![
1885                        LogPredicate::term("error"),
1886                        LogPredicate::field_numeric(
1887                            "status",
1888                            NumericComparison::GreaterThanOrEqual,
1889                            500,
1890                        ),
1891                    ]),
1892                    LogPredicate::field_exists("service"),
1893                    LogPredicate::negate(LogPredicate::field_equals("env", "dev")),
1894                ]))
1895                .newest_first()
1896                .with_limit(11),
1897            LogQuery::new(partition())
1898                .where_predicate(LogPredicate::and(vec![
1899                    message_regex,
1900                    service_regex,
1901                    LogPredicate::field_in("env", ["prod", "staging"]),
1902                ]))
1903                .with_offset_range(LogicalOffset::new(5), LogicalOffset::new(55)),
1904            LogQuery::new(partition())
1905                .where_predicate(LogPredicate::or(vec![
1906                    LogPredicate::message_contains("heartbeat"),
1907                    LogPredicate::field_numeric("status", NumericComparison::GreaterThan, 400),
1908                ]))
1909                .with_timestamp_range(500, 5_500)
1910                .sort_by_timestamp()
1911                .newest_first()
1912                .with_limit(17),
1913            LogQuery::new(partition()).where_predicate(LogPredicate::or(vec![
1914                LogPredicate::message(TextMatcher::new(
1915                    "INFO request 12 completed",
1916                    TextMatchKind::Exact,
1917                    CaseSensitivity::Sensitive,
1918                )),
1919                LogPredicate::message(TextMatcher::new(
1920                    "debug heartbeat",
1921                    TextMatchKind::Prefix,
1922                    CaseSensitivity::Insensitive,
1923                )),
1924                LogPredicate::message(TextMatcher::new(
1925                    "250ms",
1926                    TextMatchKind::Suffix,
1927                    CaseSensitivity::Sensitive,
1928                )),
1929            ])),
1930            LogQuery::new(partition()).where_predicate(LogPredicate::and(vec![
1931                LogPredicate::field(
1932                    "service",
1933                    TextMatcher::new("TOR", TextMatchKind::Contains, CaseSensitivity::Insensitive),
1934                ),
1935                LogPredicate::field_numeric("status", NumericComparison::Equal, 429),
1936                LogPredicate::field_numeric("status", NumericComparison::NotEqual, 503),
1937                LogPredicate::field_numeric("status", NumericComparison::LessThanOrEqual, 429),
1938            ])),
1939            LogQuery::new(partition()).where_predicate(LogPredicate::and(vec![
1940                LogPredicate::field_numeric("status", NumericComparison::LessThan, 500),
1941                LogPredicate::field_numeric("status", NumericComparison::GreaterThan, 199),
1942            ])),
1943            LogQuery::new(partition()).where_predicate(LogPredicate::MatchNone),
1944        ];
1945
1946        for query in queries {
1947            let hot = stripe
1948                .query(&query)
1949                .into_iter()
1950                .map(|matched| matched.record.record_ref.offset)
1951                .collect::<Vec<_>>();
1952            let cold = cold_matches(&index, &records, 10, &query)
1953                .into_iter()
1954                .map(|record| record.record_ref.offset)
1955                .collect::<Vec<_>>();
1956            assert_eq!(hot, cold);
1957
1958            let decoded_candidates = index.candidate_hits(&query).into_iter().map(|hit| {
1959                decoded_blocks[usize::try_from(hit.block_ordinal).expect("block fits")]
1960                    [usize::try_from(hit.record_ordinal).expect("record fits")]
1961                .clone()
1962            });
1963            let decoded = query
1964                .select(decoded_candidates)
1965                .into_iter()
1966                .map(|record| record.offset)
1967                .collect::<Vec<_>>();
1968            assert_eq!(hot, decoded);
1969        }
1970    }
1971
1972    #[test]
1973    fn timestamp_cursor_pages_are_stable_across_hot_and_sealed_tiers() {
1974        let records = compatibility_records(48);
1975        let index = compatibility_index(&records, 8);
1976        let mut stripe =
1977            LogStripe::new(ShardId::new(1), StripeConfig::default()).expect("stripe opens");
1978        for record in records.iter().cloned() {
1979            stripe.apply_durable(record).expect("record indexes");
1980        }
1981
1982        let first_query = LogQuery::new(partition())
1983            .where_predicate(LogPredicate::field_exists("service"))
1984            .sort_by_timestamp()
1985            .newest_first()
1986            .with_limit(7);
1987        let hot_first = stripe.query(&first_query);
1988        let cold_first = cold_matches(&index, &records, 8, &first_query);
1989        assert_eq!(
1990            hot_first
1991                .iter()
1992                .map(|matched| matched.record.record_ref.offset)
1993                .collect::<Vec<_>>(),
1994            cold_first
1995                .iter()
1996                .map(|record| record.record_ref.offset)
1997                .collect::<Vec<_>>()
1998        );
1999
2000        let cursor = first_query.cursor_for(&hot_first.last().expect("first page exists").record);
2001        let second_query = first_query.clone().after(cursor);
2002        let hot_second = stripe.query(&second_query);
2003        let cold_second = cold_matches(&index, &records, 8, &second_query);
2004        assert_eq!(
2005            hot_second
2006                .iter()
2007                .map(|matched| matched.record.record_ref.offset)
2008                .collect::<Vec<_>>(),
2009            cold_second
2010                .iter()
2011                .map(|record| record.record_ref.offset)
2012                .collect::<Vec<_>>()
2013        );
2014        assert!(hot_first.iter().all(|first| {
2015            hot_second
2016                .iter()
2017                .all(|second| first.record.record_ref != second.record.record_ref)
2018        }));
2019    }
2020
2021    #[test]
2022    fn residual_queries_do_not_apply_the_limit_before_exact_filtering() {
2023        let records = compatibility_records(40);
2024        let index = compatibility_index(&records, 10);
2025        let query = LogQuery::new(partition())
2026            .where_predicate(LogPredicate::or(vec![
2027                LogPredicate::message_contains("heartbeat"),
2028                LogPredicate::field_numeric("status", NumericComparison::GreaterThanOrEqual, 500),
2029            ]))
2030            .newest_first()
2031            .with_limit(2);
2032        let candidates = index.candidate_hits(&query);
2033        assert_eq!(candidates.len(), records.len());
2034        assert_eq!(cold_matches(&index, &records, 10, &query).len(), 2);
2035    }
2036
2037    #[test]
2038    fn residual_queries_stream_sealed_blocks_until_the_page_is_complete() {
2039        let records = compatibility_records(60);
2040        let index = compatibility_index(&records, 10);
2041        let query = LogQuery::new(partition())
2042            .where_predicate(LogPredicate::message_contains("heartbeat"))
2043            .newest_first()
2044            .with_limit(4);
2045
2046        let mut streamed = Vec::new();
2047        let mut visited_blocks = 0usize;
2048        for block_ordinal in index.candidate_blocks(&query) {
2049            visited_blocks += 1;
2050            let candidates = index
2051                .candidate_hits_in_block(&query, block_ordinal)
2052                .into_iter()
2053                .map(|hit| {
2054                    records[usize::try_from(hit.block_ordinal).expect("block fits") * 10
2055                        + usize::try_from(hit.record_ordinal).expect("record fits")]
2056                    .clone()
2057                });
2058            streamed.extend(candidates.filter(|record| query.matches(record)));
2059            if streamed.len() >= query.limit.expect("query has a limit") {
2060                break;
2061            }
2062        }
2063
2064        assert!(visited_blocks < index.blocks().len());
2065        assert_eq!(
2066            query
2067                .select(streamed)
2068                .into_iter()
2069                .map(|record| record.record_ref.offset)
2070                .collect::<Vec<_>>(),
2071            cold_matches(&index, &records, 10, &query)
2072                .into_iter()
2073                .map(|record| record.record_ref.offset)
2074                .collect::<Vec<_>>()
2075        );
2076    }
2077
2078    #[test]
2079    fn message_trigrams_reject_missing_literal_blocks_without_false_negatives() {
2080        let mut records = compatibility_records(20);
2081        records[7].message = "KELVIN alarm from 東京 worker".into();
2082        let index = compatibility_index(&records, 10);
2083
2084        let unicode_query = LogQuery::new(partition())
2085            .where_predicate(LogPredicate::message_contains("kelvin alarm"));
2086        assert_eq!(index.candidate_blocks(&unicode_query), vec![0]);
2087        assert_eq!(
2088            cold_matches(&index, &records, 10, &unicode_query)
2089                .into_iter()
2090                .map(|record| record.record_ref.offset)
2091                .collect::<Vec<_>>(),
2092            vec![LogicalOffset::new(7)]
2093        );
2094
2095        let missing_query = LogQuery::new(partition()).where_predicate(
2096            LogPredicate::message_contains("impossible-substring-9f82c4"),
2097        );
2098        assert!(index.candidate_blocks(&missing_query).is_empty());
2099        assert!(index.candidate_hits(&missing_query).is_empty());
2100        assert!(index.candidate_hits_in_block(&missing_query, 0).is_empty());
2101    }
2102
2103    #[test]
2104    fn every_literal_mode_and_case_policy_retains_unicode_matches() {
2105        let messages = [
2106            "İSTANBUL 東京 suffix",
2107            "Straße/Δelta END",
2108            "ASCII prefix and suffix",
2109        ];
2110        let records = messages
2111            .iter()
2112            .enumerate()
2113            .map(|(offset, message)| {
2114                DurableLog::new(
2115                    ShardId::new(1),
2116                    partition(),
2117                    LogicalOffset::new(u64::try_from(offset).expect("offset fits")),
2118                    u64::try_from(offset).expect("timestamp fits"),
2119                    *message,
2120                    CompressionCohortId::new(1),
2121                )
2122            })
2123            .collect::<Vec<_>>();
2124        let index = compatibility_index(&records, 1);
2125        let queries = [
2126            TextMatcher::new(
2127                "İSTANBUL 東京 suffix",
2128                TextMatchKind::Exact,
2129                CaseSensitivity::Sensitive,
2130            ),
2131            TextMatcher::new(
2132                "i\u{307}stanbul",
2133                TextMatchKind::Prefix,
2134                CaseSensitivity::Insensitive,
2135            ),
2136            TextMatcher::new("東京", TextMatchKind::Contains, CaseSensitivity::Sensitive),
2137            TextMatcher::new("end", TextMatchKind::Suffix, CaseSensitivity::Insensitive),
2138            TextMatcher::new(
2139                "ASCII prefix",
2140                TextMatchKind::Prefix,
2141                CaseSensitivity::Sensitive,
2142            ),
2143            TextMatcher::new("Δ", TextMatchKind::Contains, CaseSensitivity::Sensitive),
2144        ]
2145        .map(|matcher| LogQuery::new(partition()).where_predicate(LogPredicate::message(matcher)));
2146
2147        for query in queries {
2148            let candidate_blocks = index.candidate_blocks(&query);
2149            for (block_ordinal, record) in records.iter().enumerate() {
2150                if query.matches(record) {
2151                    assert!(
2152                        candidate_blocks
2153                            .contains(&u32::try_from(block_ordinal).expect("block fits")),
2154                        "true literal match was pruned: {query:?}"
2155                    );
2156                }
2157            }
2158        }
2159    }
2160
2161    #[test]
2162    fn message_trigram_pruning_only_uses_literals_required_by_boolean_logic() {
2163        let records = compatibility_records(20);
2164        let index = compatibility_index(&records, 10);
2165        let missing = LogPredicate::message_contains("impossible-substring-9f82c4");
2166
2167        let conjunction = LogQuery::new(partition()).where_predicate(LogPredicate::and(vec![
2168            LogPredicate::term("request"),
2169            missing.clone(),
2170        ]));
2171        assert!(index.candidate_blocks(&conjunction).is_empty());
2172
2173        let disjunction = LogQuery::new(partition()).where_predicate(LogPredicate::or(vec![
2174            LogPredicate::term("request"),
2175            missing.clone(),
2176        ]));
2177        assert_eq!(index.candidate_blocks(&disjunction), vec![0, 1]);
2178
2179        let negation = LogQuery::new(partition()).where_predicate(LogPredicate::negate(missing));
2180        assert_eq!(index.candidate_blocks(&negation), vec![0, 1]);
2181    }
2182
2183    #[test]
2184    fn trigram_hash_collisions_can_only_create_extra_candidates() {
2185        let mut by_slot = vec![None::<[u8; 3]>; MESSAGE_TRIGRAM_FILTER_BITS];
2186        let mut collision = None;
2187        let lowercase_stable = (b'!'..=b'~')
2188            .filter(|byte| !byte.is_ascii_uppercase())
2189            .collect::<Vec<_>>();
2190        'search: for &first in &lowercase_stable {
2191            for &second in &lowercase_stable {
2192                for &third in &lowercase_stable {
2193                    let trigram = [first, second, third];
2194                    let slot = message_trigram_slot(trigram);
2195                    if let Some(previous) = by_slot[slot]
2196                        && previous != trigram
2197                    {
2198                        collision = Some((previous, trigram));
2199                        break 'search;
2200                    }
2201                    by_slot[slot] = Some(trigram);
2202                }
2203            }
2204        }
2205        let (stored, queried) = collision.expect("the bounded hash has a printable collision");
2206        let stored = String::from_utf8(stored.to_vec()).expect("printable bytes are UTF-8");
2207        let queried = String::from_utf8(queried.to_vec()).expect("printable bytes are UTF-8");
2208        let record = DurableLog::new(
2209            ShardId::new(1),
2210            partition(),
2211            LogicalOffset::new(0),
2212            0,
2213            stored,
2214            CompressionCohortId::new(1),
2215        );
2216        let index = compatibility_index(std::slice::from_ref(&record), 1);
2217        let query =
2218            LogQuery::new(partition()).where_predicate(LogPredicate::message_contains(queried));
2219
2220        assert_eq!(index.candidate_blocks(&query), vec![0]);
2221        assert!(cold_matches(&index, &[record], 1, &query).is_empty());
2222    }
2223
2224    #[test]
2225    fn message_trigram_memory_is_fixed_per_block() {
2226        let records = compatibility_records(30);
2227        let index = compatibility_index(&records, 10);
2228        assert_eq!(
2229            index.message_trigram_filter_bytes(),
2230            3 * MESSAGE_TRIGRAM_FILTER_BYTES
2231        );
2232    }
2233}