Skip to main content

shard_telemetry/
query.rs

1use std::cmp::Ordering;
2
3use crate::{
4    CaseSensitivity, LogPredicate, LogQuery, MetadataField, NumericComparison, QueryCursor,
5    QueryOrder, QuerySort, StructuralRecordView, TextMatchKind, TextMatcher, analyze_message,
6};
7
8pub(crate) struct RequiredIndexConstraints<'a> {
9    pub(crate) terms: Vec<&'a str>,
10    pub(crate) fields: Vec<(&'a str, &'a str)>,
11    pub(crate) message_literals: Vec<&'a str>,
12    pub(crate) impossible: bool,
13}
14
15impl LogQuery {
16    /// Returns whether a normalized structural record satisfies every lookup
17    /// range, legacy exact constraint, Boolean predicate, and page cursor.
18    #[must_use]
19    pub fn matches<R: StructuralRecordView>(&self, record: &R) -> bool {
20        self.offset_matches(record.structural_offset())
21            && self.timestamp_matches(record.structural_timestamp_unix_nanos())
22            && self.cursor_matches(record)
23            && self.legacy_terms_match(record)
24            && self.legacy_fields_match(record)
25            && predicate_matches(&self.predicate, record)
26    }
27
28    /// Compares two matching records in the query's deterministic result order.
29    #[must_use]
30    pub fn compare<R: StructuralRecordView>(&self, left: &R, right: &R) -> Ordering {
31        let ordering = match self.sort {
32            QuerySort::Offset => left.structural_offset().cmp(&right.structural_offset()),
33            QuerySort::Timestamp => (
34                left.structural_timestamp_unix_nanos(),
35                left.structural_offset(),
36            )
37                .cmp(&(
38                    right.structural_timestamp_unix_nanos(),
39                    right.structural_offset(),
40                )),
41        };
42        if self.order == QueryOrder::NewestFirst {
43            ordering.reverse()
44        } else {
45            ordering
46        }
47    }
48
49    /// Creates the stable continuation point represented by one result.
50    #[must_use]
51    pub fn cursor_for<R: StructuralRecordView>(&self, record: &R) -> QueryCursor {
52        QueryCursor::new(
53            record.structural_timestamp_unix_nanos(),
54            record.structural_offset(),
55        )
56    }
57
58    /// Applies exact residual filtering, deterministic ordering, and the result
59    /// limit to decoded candidate records from a sealed-block lookup.
60    #[must_use]
61    pub fn select<R: StructuralRecordView>(&self, records: impl IntoIterator<Item = R>) -> Vec<R> {
62        let mut selected = records
63            .into_iter()
64            .filter(|record| self.matches(record))
65            .collect::<Vec<_>>();
66        selected.sort_unstable_by(|left, right| self.compare(left, right));
67        if let Some(limit) = self.limit {
68            selected.truncate(limit);
69        }
70        selected
71    }
72
73    /// Returns whether sealed candidates require record decoding before the
74    /// query can be limited safely.
75    ///
76    /// Callers serving sealed blocks should stream these queries block by
77    /// block instead of materializing the complete candidate set.
78    #[must_use]
79    pub fn requires_post_decode(&self) -> bool {
80        self.start_offset.is_some()
81            || self.end_offset.is_some()
82            || self.start_timestamp_unix_nanos.is_some()
83            || self.end_timestamp_unix_nanos.is_some()
84            || self.after.is_some()
85            || self.sort == QuerySort::Timestamp
86            || !predicate_is_index_only_conjunction(&self.predicate)
87    }
88
89    pub(crate) fn required_index_constraints(&self) -> RequiredIndexConstraints<'_> {
90        let mut constraints = RequiredIndexConstraints {
91            terms: self.terms.iter().map(AsRef::as_ref).collect(),
92            fields: self
93                .exact_fields
94                .iter()
95                .map(|field| (field.key.as_ref(), field.value.as_ref()))
96                .collect(),
97            message_literals: Vec::new(),
98            impossible: false,
99        };
100        collect_required_constraints(&self.predicate, &mut constraints);
101        constraints
102    }
103
104    pub(crate) fn can_apply_index_limit(&self) -> bool {
105        self.start_offset.is_none()
106            && self.end_offset.is_none()
107            && self.start_timestamp_unix_nanos.is_none()
108            && self.end_timestamp_unix_nanos.is_none()
109            && self.after.is_none()
110            && self.sort == QuerySort::Offset
111            && predicate_is_index_only_conjunction(&self.predicate)
112    }
113
114    pub(crate) fn needs_record_filter(&self) -> bool {
115        self.start_timestamp_unix_nanos.is_some()
116            || self.end_timestamp_unix_nanos.is_some()
117            || self.after.is_some()
118            || self.sort == QuerySort::Timestamp
119            || !predicate_is_index_only_conjunction(&self.predicate)
120    }
121
122    pub(crate) fn has_residual_predicate(&self) -> bool {
123        !predicate_is_index_only_conjunction(&self.predicate)
124    }
125
126    pub(crate) fn message_candidate_matches(&self, message: &str) -> Option<bool> {
127        if !self
128            .terms
129            .iter()
130            .all(|expected| message_has_term(message, expected))
131        {
132            return Some(false);
133        }
134        message_only_predicate_matches(&self.predicate, message)
135    }
136
137    pub(crate) fn matches_index_candidate<R: StructuralRecordView>(&self, record: &R) -> bool {
138        self.offset_matches(record.structural_offset())
139            && self.timestamp_matches(record.structural_timestamp_unix_nanos())
140            && self.cursor_matches(record)
141            && predicate_matches(&self.predicate, record)
142    }
143
144    pub(crate) fn has_invalid_range(&self) -> bool {
145        self.start_offset
146            .zip(self.end_offset)
147            .is_some_and(|(start, end)| start >= end)
148            || self
149                .start_timestamp_unix_nanos
150                .zip(self.end_timestamp_unix_nanos)
151                .is_some_and(|(start, end)| start >= end)
152    }
153
154    fn offset_matches(&self, offset: shard_stream_core::LogicalOffset) -> bool {
155        self.start_offset.is_none_or(|start| offset >= start)
156            && self.end_offset.is_none_or(|end| offset < end)
157    }
158
159    fn timestamp_matches(&self, timestamp_unix_nanos: u64) -> bool {
160        self.start_timestamp_unix_nanos
161            .is_none_or(|start| timestamp_unix_nanos >= start)
162            && self
163                .end_timestamp_unix_nanos
164                .is_none_or(|end| timestamp_unix_nanos < end)
165    }
166
167    fn cursor_matches<R: StructuralRecordView>(&self, record: &R) -> bool {
168        let Some(cursor) = self.after else {
169            return true;
170        };
171        let ordering = match self.sort {
172            QuerySort::Offset => record.structural_offset().cmp(&cursor.offset),
173            QuerySort::Timestamp => (
174                record.structural_timestamp_unix_nanos(),
175                record.structural_offset(),
176            )
177                .cmp(&(cursor.timestamp_unix_nanos, cursor.offset)),
178        };
179        if self.order == QueryOrder::NewestFirst {
180            ordering == Ordering::Less
181        } else {
182            ordering == Ordering::Greater
183        }
184    }
185
186    fn legacy_terms_match<R: StructuralRecordView>(&self, record: &R) -> bool {
187        self.terms
188            .iter()
189            .all(|expected| message_has_term(record.structural_message(), expected))
190    }
191
192    fn legacy_fields_match<R: StructuralRecordView>(&self, record: &R) -> bool {
193        self.exact_fields
194            .iter()
195            .all(|expected| field_equals(record, expected))
196    }
197}
198
199fn collect_required_constraints<'a>(
200    predicate: &'a LogPredicate,
201    constraints: &mut RequiredIndexConstraints<'a>,
202) {
203    match predicate {
204        LogPredicate::MatchAll => {}
205        LogPredicate::MatchNone => constraints.impossible = true,
206        LogPredicate::Term(term) => constraints.terms.push(term),
207        LogPredicate::MessageToken { value, .. } if clickhouse_token_is_index_safe(value) => {
208            constraints.terms.push(value);
209        }
210        LogPredicate::Field { key, matcher }
211            if matcher.kind == TextMatchKind::Exact
212                && matcher.case_sensitivity == CaseSensitivity::Sensitive =>
213        {
214            constraints.fields.push((key, &matcher.value));
215        }
216        LogPredicate::And(predicates) => {
217            for predicate in predicates {
218                collect_required_constraints(predicate, constraints);
219            }
220        }
221        LogPredicate::Message(matcher) => {
222            constraints.message_literals.push(matcher.value.as_ref());
223        }
224        LogPredicate::MessageToken { .. }
225        | LogPredicate::MessageRegex(_)
226        | LogPredicate::FieldExists(_)
227        | LogPredicate::Field { .. }
228        | LogPredicate::FieldIn { .. }
229        | LogPredicate::FieldRegex { .. }
230        | LogPredicate::FieldNumeric { .. }
231        | LogPredicate::Or(_)
232        | LogPredicate::Not(_) => {}
233    }
234}
235
236fn predicate_is_index_only_conjunction(predicate: &LogPredicate) -> bool {
237    match predicate {
238        LogPredicate::MatchAll
239        | LogPredicate::MatchNone
240        | LogPredicate::Term(_)
241        | LogPredicate::Field {
242            matcher:
243                TextMatcher {
244                    kind: TextMatchKind::Exact,
245                    case_sensitivity: CaseSensitivity::Sensitive,
246                    ..
247                },
248            ..
249        } => true,
250        LogPredicate::And(predicates) => predicates.iter().all(predicate_is_index_only_conjunction),
251        LogPredicate::MessageToken { .. }
252        | LogPredicate::Message(_)
253        | LogPredicate::MessageRegex(_)
254        | LogPredicate::FieldExists(_)
255        | LogPredicate::Field { .. }
256        | LogPredicate::FieldIn { .. }
257        | LogPredicate::FieldRegex { .. }
258        | LogPredicate::FieldNumeric { .. }
259        | LogPredicate::Or(_)
260        | LogPredicate::Not(_) => false,
261    }
262}
263
264fn predicate_matches<R: StructuralRecordView>(predicate: &LogPredicate, record: &R) -> bool {
265    match predicate {
266        LogPredicate::MatchAll => true,
267        LogPredicate::MatchNone => false,
268        LogPredicate::Term(term) => message_has_term(record.structural_message(), term),
269        LogPredicate::MessageToken {
270            value,
271            case_sensitivity,
272        } => message_has_clickhouse_token(record.structural_message(), value, *case_sensitivity),
273        LogPredicate::Message(matcher) => text_matches(record.structural_message(), matcher),
274        LogPredicate::MessageRegex(regex) => regex.is_match(record.structural_message()),
275        LogPredicate::FieldExists(key) => {
276            fields(record).any(|(observed, _)| observed == key.as_ref())
277        }
278        LogPredicate::Field { key, matcher } => fields(record).any(|(observed_key, value)| {
279            observed_key == key.as_ref() && text_matches(value, matcher)
280        }),
281        LogPredicate::FieldIn { key, values } => fields(record).any(|(observed_key, value)| {
282            observed_key == key.as_ref() && values.iter().any(|expected| value == expected.as_ref())
283        }),
284        LogPredicate::FieldRegex { key, regex } => fields(record)
285            .any(|(observed_key, value)| observed_key == key.as_ref() && regex.is_match(value)),
286        LogPredicate::FieldNumeric {
287            key,
288            comparison,
289            value,
290        } => fields(record).any(|(observed_key, observed)| {
291            observed_key == key.as_ref()
292                && observed
293                    .parse::<i128>()
294                    .is_ok_and(|observed| compare_numeric(observed, *comparison, *value))
295        }),
296        LogPredicate::And(predicates) => predicates
297            .iter()
298            .all(|predicate| predicate_matches(predicate, record)),
299        LogPredicate::Or(predicates) => predicates
300            .iter()
301            .any(|predicate| predicate_matches(predicate, record)),
302        LogPredicate::Not(predicate) => !predicate_matches(predicate, record),
303    }
304}
305
306fn message_only_predicate_matches(predicate: &LogPredicate, message: &str) -> Option<bool> {
307    match predicate {
308        LogPredicate::MatchAll => Some(true),
309        LogPredicate::MatchNone => Some(false),
310        LogPredicate::Term(term) => Some(message_has_term(message, term)),
311        LogPredicate::MessageToken {
312            value,
313            case_sensitivity,
314        } => Some(message_has_clickhouse_token(
315            message,
316            value,
317            *case_sensitivity,
318        )),
319        LogPredicate::Message(matcher) => Some(text_matches(message, matcher)),
320        LogPredicate::MessageRegex(regex) => Some(regex.is_match(message)),
321        LogPredicate::And(predicates) => {
322            let mut matched = true;
323            for predicate in predicates {
324                matched &= message_only_predicate_matches(predicate, message)?;
325            }
326            Some(matched)
327        }
328        LogPredicate::Or(predicates) => {
329            let mut matched = false;
330            for predicate in predicates {
331                matched |= message_only_predicate_matches(predicate, message)?;
332            }
333            Some(matched)
334        }
335        LogPredicate::Not(predicate) => {
336            message_only_predicate_matches(predicate, message).map(|value| !value)
337        }
338        LogPredicate::FieldExists(_)
339        | LogPredicate::Field { .. }
340        | LogPredicate::FieldIn { .. }
341        | LogPredicate::FieldRegex { .. }
342        | LogPredicate::FieldNumeric { .. } => None,
343    }
344}
345
346fn fields<R: StructuralRecordView>(record: &R) -> impl Iterator<Item = (&str, &str)> {
347    (0..record.structural_field_count()).filter_map(|index| record.structural_field(index))
348}
349
350fn field_equals<R: StructuralRecordView>(record: &R, expected: &MetadataField) -> bool {
351    fields(record)
352        .any(|(key, value)| key == expected.key.as_ref() && value == expected.value.as_ref())
353}
354
355pub(crate) fn message_has_term(message: &str, expected: &str) -> bool {
356    let mut matched = false;
357    let _ = analyze_message(message, &[], |term| {
358        matched |= text_equal(term, expected, CaseSensitivity::Insensitive);
359    });
360    matched
361}
362
363pub(crate) fn message_has_clickhouse_token(
364    message: &str,
365    expected: &str,
366    case_sensitivity: CaseSensitivity,
367) -> bool {
368    let expected = expected.as_bytes();
369    if expected.is_empty() || expected.iter().copied().any(clickhouse_token_separator) {
370        return false;
371    }
372    let message = message.as_bytes();
373    if expected.len() > message.len() {
374        return false;
375    }
376    message
377        .windows(expected.len())
378        .enumerate()
379        .any(|(start, candidate)| {
380            let bytes_match = match case_sensitivity {
381                CaseSensitivity::Sensitive => candidate == expected,
382                CaseSensitivity::Insensitive => candidate.eq_ignore_ascii_case(expected),
383            };
384            bytes_match
385                && (start == 0 || clickhouse_token_separator(message[start - 1]))
386                && (start + expected.len() == message.len()
387                    || clickhouse_token_separator(message[start + expected.len()]))
388        })
389}
390
391fn clickhouse_token_is_index_safe(value: &str) -> bool {
392    !value.is_empty() && value.bytes().all(|byte| byte.is_ascii_alphanumeric())
393}
394
395const fn clickhouse_token_separator(byte: u8) -> bool {
396    byte.is_ascii() && !(byte.is_ascii_alphanumeric() || byte == b'_')
397}
398
399fn text_matches(observed: &str, matcher: &TextMatcher) -> bool {
400    match matcher.kind {
401        TextMatchKind::Exact => text_equal(observed, &matcher.value, matcher.case_sensitivity),
402        TextMatchKind::Contains => {
403            text_contains(observed, &matcher.value, matcher.case_sensitivity)
404        }
405        TextMatchKind::Prefix => text_prefix(observed, &matcher.value, matcher.case_sensitivity),
406        TextMatchKind::Suffix => text_suffix(observed, &matcher.value, matcher.case_sensitivity),
407    }
408}
409
410fn text_equal(left: &str, right: &str, case_sensitivity: CaseSensitivity) -> bool {
411    match case_sensitivity {
412        CaseSensitivity::Sensitive => left == right,
413        CaseSensitivity::Insensitive if left.is_ascii() && right.is_ascii() => {
414            left.eq_ignore_ascii_case(right)
415        }
416        CaseSensitivity::Insensitive => left.to_lowercase() == right.to_lowercase(),
417    }
418}
419
420fn text_contains(haystack: &str, needle: &str, case_sensitivity: CaseSensitivity) -> bool {
421    if needle.is_empty() {
422        return true;
423    }
424    match case_sensitivity {
425        CaseSensitivity::Sensitive => haystack.contains(needle),
426        CaseSensitivity::Insensitive if haystack.is_ascii() && needle.is_ascii() => haystack
427            .as_bytes()
428            .windows(needle.len())
429            .any(|window| window.eq_ignore_ascii_case(needle.as_bytes())),
430        CaseSensitivity::Insensitive => haystack.to_lowercase().contains(&needle.to_lowercase()),
431    }
432}
433
434fn text_prefix(observed: &str, prefix: &str, case_sensitivity: CaseSensitivity) -> bool {
435    match case_sensitivity {
436        CaseSensitivity::Sensitive => observed.starts_with(prefix),
437        CaseSensitivity::Insensitive if observed.is_ascii() && prefix.is_ascii() => observed
438            .get(..prefix.len())
439            .is_some_and(|candidate| candidate.eq_ignore_ascii_case(prefix)),
440        CaseSensitivity::Insensitive => observed.to_lowercase().starts_with(&prefix.to_lowercase()),
441    }
442}
443
444fn text_suffix(observed: &str, suffix: &str, case_sensitivity: CaseSensitivity) -> bool {
445    match case_sensitivity {
446        CaseSensitivity::Sensitive => observed.ends_with(suffix),
447        CaseSensitivity::Insensitive if observed.is_ascii() && suffix.is_ascii() => observed
448            .len()
449            .checked_sub(suffix.len())
450            .and_then(|start| observed.get(start..))
451            .is_some_and(|candidate| candidate.eq_ignore_ascii_case(suffix)),
452        CaseSensitivity::Insensitive => observed.to_lowercase().ends_with(&suffix.to_lowercase()),
453    }
454}
455
456const fn compare_numeric(observed: i128, comparison: NumericComparison, expected: i128) -> bool {
457    match comparison {
458        NumericComparison::Equal => observed == expected,
459        NumericComparison::NotEqual => observed != expected,
460        NumericComparison::LessThan => observed < expected,
461        NumericComparison::LessThanOrEqual => observed <= expected,
462        NumericComparison::GreaterThan => observed > expected,
463        NumericComparison::GreaterThanOrEqual => observed >= expected,
464    }
465}
466
467#[cfg(test)]
468mod tests {
469    use shard_stream_core::{LogicalOffset, LogicalPartitionId, ShardId, TopicId, TopicPartition};
470
471    use super::*;
472    use crate::{CompressionCohortId, DurableLog, LogRegex};
473
474    fn record(message: &str) -> DurableLog {
475        DurableLog::new(
476            ShardId::new(1),
477            TopicPartition::new(TopicId::new(1), LogicalPartitionId::new(2)),
478            LogicalOffset::new(7),
479            99,
480            message,
481            CompressionCohortId::new(1),
482        )
483        .with_field("service", "Paiements")
484        .with_field("status", "503")
485    }
486
487    #[test]
488    fn literal_regex_numeric_and_boolean_predicates_are_exact() {
489        let record = record("ÉCHEC checkout timed out");
490        let predicate = LogPredicate::and(vec![
491            LogPredicate::message_contains("échec checkout"),
492            LogPredicate::message_regex("timed\\s+out$", CaseSensitivity::Insensitive)
493                .expect("regex compiles"),
494            LogPredicate::field(
495                "service",
496                TextMatcher::new("paie", TextMatchKind::Prefix, CaseSensitivity::Insensitive),
497            ),
498            LogPredicate::field_numeric("status", NumericComparison::GreaterThanOrEqual, 500),
499            LogPredicate::negate(LogPredicate::field_equals("service", "worker")),
500        ]);
501        assert!(predicate_matches(&predicate, &record));
502        assert!(!predicate_matches(
503            &LogPredicate::message_contains("success"),
504            &record
505        ));
506        assert!(predicate_matches(
507            &LogPredicate::field_numeric("status", NumericComparison::Equal, 503),
508            &record
509        ));
510        assert!(predicate_matches(
511            &LogPredicate::field_numeric("status", NumericComparison::NotEqual, 200),
512            &record
513        ));
514    }
515
516    #[test]
517    fn invalid_regular_expressions_are_rejected_at_query_construction() {
518        let error =
519            LogRegex::new("(", CaseSensitivity::Sensitive).expect_err("invalid regex is rejected");
520        assert!(matches!(error, crate::TelemetryError::InvalidQuery(_)));
521    }
522
523    #[test]
524    fn empty_literal_contains_matches_without_panicking() {
525        assert!(text_contains("anything", "", CaseSensitivity::Insensitive));
526    }
527
528    #[test]
529    fn clickhouse_tokens_preserve_case_and_ascii_boundaries() {
530        assert!(message_has_clickhouse_token(
531            "prefix Cannot suffix",
532            "Cannot",
533            CaseSensitivity::Sensitive
534        ));
535        assert!(!message_has_clickhouse_token(
536            "prefix Cannot suffix",
537            "cannot",
538            CaseSensitivity::Sensitive
539        ));
540        assert!(message_has_clickhouse_token(
541            "prefix Cannot suffix",
542            "cannot",
543            CaseSensitivity::Insensitive
544        ));
545        assert!(!message_has_clickhouse_token(
546            "prefix_cannot suffix",
547            "cannot",
548            CaseSensitivity::Sensitive
549        ));
550        assert!(!message_has_clickhouse_token(
551            "prefix écannot suffix",
552            "cannot",
553            CaseSensitivity::Sensitive
554        ));
555    }
556
557    #[test]
558    fn clickhouse_token_uses_the_case_folded_index_only_as_a_candidate_filter() {
559        let query = LogQuery::new(record("unused").record_ref.topic_partition).where_predicate(
560            LogPredicate::message_token("Cannot", CaseSensitivity::Sensitive),
561        );
562        let constraints = query.required_index_constraints();
563        assert_eq!(constraints.terms, ["Cannot"]);
564        assert!(query.requires_post_decode());
565    }
566}