# MATCH WITHIN Implementation Summary
## Overview
This document describes the implementation of the `MATCH ... WITHIN` clause, including validation, constraint building, and code refactoring.
## Feature Description
The MATCH command supports a `WITHIN` clause that specifies a time constraint for pattern matching:
```hamelin
MATCH pattern1 pattern2 WITHIN 5m
```
The WITHIN clause constrains the total duration from the start of the first pattern to the end of the last pattern. The interval must be positive - negative intervals like `WITHIN -5m` are rejected at compile time.
## Key Design Decisions
### Dual-Path Validation
The Hamelin compiler supports two compilation paths (old AST and typed AST), and both require negative interval validation:
**Old AST Path** - SQL Structure Analysis:
```rust
fn contains_negative_interval(sql: &SQLExpression) -> bool {
match sql {
SQLExpression::UnaryOperatorApply(UnaryOperatorApply { operator, .. }) => {
*operator == Operator::Minus
}
_ => false,
}
}
```
- Analyzes translated SQL structure for unary minus operators
- Simple and effective for catching negative interval literals like `-5m`
- Cannot detect complex expressions that evaluate to negative (e.g., `5m - 10m`), but this is acceptable
**Typed AST Path** - Semantic AST Analysis:
```rust
fn is_negative_interval_expression(expr: &Expression) -> bool {
match &expr.kind {
ExpressionKind::UnaryPrefixOperator(UnaryPrefixOperator {
operator: UnaryPrefixOp::Minus,
operand,
}) => {
match &operand.kind {
ExpressionKind::IntervalLiteral(_) => true,
_ => false,
}
}
_ => false,
}
}
```
- Uses the embedded AST structure within typed expressions
- More precise semantic analysis distinguishing between unary minus (`-5m`) and binary minus (`5m - 1m`)
- Leverages richer type information available in the typed AST path
### SORT and Timestamp Column Validation
**Important**: SORT validation for MATCH with WITHIN is NOT performed during AST type-checking. It is handled by the incremental refresh analysis in `incremental.rs`.
**Rationale for Separation**:
- SORT validation is an **incremental refresh constraint**, not a general MATCH constraint
- The AST allows any SORT expressions with WITHIN for maximum flexibility
- Incremental refresh analysis validates that SORT uses the `timestamp` column specifically
- This separation of concerns prevents bleeding incremental logic into the AST layer
**Incremental Refresh Validation** (`hamelin_lib/src/incremental.rs`):
```rust
// In MATCH handler within compute_replace_range_forward_pass
if let Some(within) = &typed_match_command.within {
check_expression_for_non_deterministic(within)?;
// If WITHIN is used, validate that SORT uses the 'timestamp' column
if !typed_match_command.sort.is_empty() {
let has_timestamp_sort = typed_match_command.sort.iter().any(|sort_expr| {
matches!(&sort_expr.expression.ast.kind,
ExpressionKind::ColumnReference(col_ref)
if col_ref.column_name.name == "timestamp")
});
if !has_timestamp_sort {
return Err(IncrementalAnalysisError::CommandNotSupported(...));
}
}
}
```
This means:
- MATCH with WITHIN and any SORT compiles successfully
- Incremental refresh will fail if SORT doesn't use 'timestamp' column
- Non-incremental execution works with any SORT expression
## Code Organization
### Helper Functions for Constraint Building
The original implementation had ~90 lines of duplicated code for building WITHIN constraints. This was refactored into three helper functions:
```rust
fn create_timestamp_column_ref(pattern_name: &str) -> SQLExpression
fn create_function_call_on_timestamp(func_name: &str, pattern_name: &str) -> SQLExpression
fn create_within_constraint(left_expr: SQLExpression, right_expr: SQLExpression, within_expr: SQLExpression) -> SQLExpression
```
**Benefits**:
- Eliminates duplicate code between single and multiple pattern cases
- Changes to constraint logic only need to be made in one place
- Improves readability by separating low-level SQL construction from high-level logic
### Constraint Semantics
**Single Pattern**:
```sql
last(pattern.timestamp) - first(pattern.timestamp) <= interval
```
**Multiple Patterns**:
```sql
last(last_pattern.timestamp) - first(first_pattern.timestamp) <= interval
```
This ensures the total duration from the very first event to the very last event in the match sequence is within the specified interval. All events in the pattern must fall within this time span.
## Implementation Locations
- **Typed AST Validation**: `hamelin_lib/src/tree/typed_ast/command.rs` - `TypedMatchCommand::is_negative_interval_expression` and negative interval check
- **Typed AST Type Checking**: `hamelin_lib/src/tree/typed_ast/command.rs` - Uses `from_ast_with_expected_type` with `IntervalMatcher::default()`
- **Old AST Validation**: `hamelin_lib/src/ast/command/match_cmd.rs` - `contains_negative_interval` and `validate_within_constraints` functions
- **Constraint Building**: `hamelin_lib/src/ast/command/match_cmd.rs` - Helper functions `create_timestamp_column_ref`, `create_function_call_on_timestamp`, `create_within_constraint`
- **SORT Validation (Incremental)**: `hamelin_lib/src/incremental.rs` - Column name validation in MATCH handler within `compute_replace_range_forward_pass`
- **Non-deterministic Check**: `hamelin_lib/src/incremental.rs` - `check_sort_for_non_deterministic` helper function
## Testing Coverage
**Typed AST Path Tests** (`hamelin_lib/src/tree/tests/pipelines.rs`):
- `match_single_pattern_negative_within` - Rejects `-5m` with single pattern
- `match_multiple_patterns_negative_within` - Rejects `-5m` with multiple patterns
- `match_single_pattern_within_valid` - Accepts WITHIN without explicit SORT
- `match_single_pattern_within_sort_timestamp` - Accepts WITHIN with SORT BY timestamp
- `match_multiple_patterns_within_valid` - Accepts WITHIN with multiple patterns
**Typed AST Tests** (`hamelin_lib/src/tree/tests/match_tests.rs`):
- `with_within_clause_single_pattern` - Single pattern with WITHIN
- `with_within_clause_multiple_patterns` - Multiple patterns with WITHIN
**Incremental Refresh Tests** (`hamelin_lib/src/incremental/tests/time_ranges.rs`):
- `match_passthrough` - Verifies MATCH works with incremental refresh and passes through time ranges unchanged
**Note**: SORT validation tests were removed from AST-level tests since validation now happens in `incremental.rs` during incremental refresh analysis, not during type-checking.
## Limitations and Future Considerations
### Current Limitations
1. **Negative Interval Detection**: Only detects literal negative intervals (e.g., `-5m`), not complex expressions that evaluate to negative (e.g., `5m - 10m`)
2. **Column Name Requirement (Incremental Only)**: For incremental refresh, SORT with WITHIN must use the column named exactly `timestamp` - alternative timestamp columns are not supported
3. **Non-deterministic Function Check**: SORT expressions are checked for non-deterministic functions (e.g., `now()`, `today()`) during incremental refresh analysis
### Future Extensions
The validation approach could be extended to:
- Validate complex expressions that evaluate to negative intervals (requires constant folding/evaluation)
- Support calendar intervals with appropriate semantics
- Allow configurable timestamp column names (would require changes to helper functions)
## Performance
The validation approach has minimal performance impact:
- Only executes when WITHIN clause is present
- Uses simple pattern matching on AST/SQL structures
- No expensive evaluation or complex type inference required
## Summary
The MATCH WITHIN implementation provides:
1. **Robust validation** across both compilation paths
2. **Clean, maintainable code** through helper function refactoring
3. **Clear error messages** guiding users to correct usage
4. **Semantic consistency** between SORT and WITHIN constraints
5. **Comprehensive test coverage** ensuring correctness
The approach balances correctness, maintainability, and performance while adhering to Hamelin's architectural principles.