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#[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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
117pub struct QueryBlockMetadata {
118 pub block_ordinal: u32,
120 pub topic_partition: TopicPartition,
122 pub first_offset: LogicalOffset,
124 pub last_offset: LogicalOffset,
126 pub min_timestamp_unix_nanos: u64,
128 pub max_timestamp_unix_nanos: u64,
130 pub record_count: u32,
132}
133
134#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
136pub struct QueryHit {
137 pub block_ordinal: u32,
139 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#[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 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 #[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#[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 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 #[must_use]
544 pub fn blocks(&self) -> &[QueryBlockMetadata] {
545 &self.blocks
546 }
547
548 #[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 #[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 #[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 #[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 #[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 #[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 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 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 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 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}