When Data Has Order: A Complete Architecture Guide to the LTSeq Ordered Sequence Algebra Engine

Summary: traditional data engines treat data as unordered sets. LTSeq goes the other way and makes ordered sequences first-class. Built on a Rust kernel with DataFusion and Arrow, it provides a sequence algebra system with native support for window functions, sequential grouping, and streaming pattern matching. This article walks through the architecture.

---

1. Introduction: why does order matter?

Relational algebra assumes data is an unordered set. That works for OLTP, but the moment you step into time-series analysis, funnel analysis, or session segmentation, you spend your time wrestling with order:

-- DuckDB/SQL: Session segmentation requires three layers of nested window functions
SELECT *, SUM(is_boundary) OVER (PARTITION BY userid ORDER BY eventtime) AS session_id
FROM (
  SELECT *, CASE WHEN eventtime - LAG(eventtime) OVER (PARTITION BY userid ORDER BY eventtime) > 1800
             THEN 1 ELSE 0 END AS is_boundary
  FROM events
)

The cognitive load here is significant: you need to understand nested window function semantics, and manually handle partition boundaries and NULL cases. In LTSeq, the same logic requires just:

events.sort("userid", "eventtime") \
      .group_ordered(lambda r: (r.userid, r.eventtime - r.eventtime.shift(1) > 1800))

One line, and the intent is the logic. That's what ordered sequence algebra buys: order stops being a second-class citizen and becomes the core semantic of the language.

2. Technology stack and design philosophy

LTSeq's technology choices reflect a clear engineering philosophy:

Layer	Technology	Rationale
Compute Kernel	Rust	Zero-cost abstractions, memory safety, C-level performance
Query Engine	DataFusion	Mature SQL planner and optimizer, Parquet predicate pushdown
Columnar Storage	Apache Arrow	Zero-copy cross-language data exchange, SIMD-friendly layout
Parallel Engine	Rayon	Work-stealing thread pool for direct Parquet parallel reads
Python Bindings	PyO3	Zero-overhead Rust-Python bridge
Async Runtime	Tokio	Multi-threaded async I/O, globally shared

The guiding rule is to use existing engines without being bound to them. By default LTSeq runs on DataFusion's execution path and benefits from its query optimizer. Where DataFusion falls short, on streaming sequential scans and parallel pattern matching, LTSeq bypasses it entirely and operates directly on Parquet and Arrow.

3. Three-layer architecture

+------------------------------------------------------------------+
|  Python API Layer                                                 |
|  LTSeq = IOMixin + TransformMixin + JoinMixin                     |
|        + AggregationMixin + SetOpsMixin + AdvancedOpsMixin         |
|                                                                    |
|  Derived Structures: LinkedTable | NestedTable | PartitionedTable  |
+------------------------------------------------------------------+
|  Expression System                                                 |
|  Python Lambda -> SchemaProxy Capture -> Dict Serialization        |
|  -> Rust Deserialization -> Optimization Pass -> DataFusion Expr   |
+------------------------------------------------------------------+
|  Rust Kernel                                                       |
|  LTSeqTable (PyO3)                                                 |
|  +-- ops/ (30+ operation implementations)                          |
|  +-- transpiler/ (expression transpilation + optimization)         |
|  +-- engine.rs (Tokio runtime + SessionContext factories)          |
|  +-- cursor.rs (streaming iterator)                                |
|                                                                    |
|  Dual Execution Paths:                                             |
|  [DataFusion Path] PyExpr -> Expr -> LogicalPlan -> Arrow          |
|  [Direct Path]     Parquet -> Rayon parallel -> fused eval -> Arrow|
+------------------------------------------------------------------+

3.1 Rust kernel: LTSeqTable and the PyO3 constraint

The core data structure LTSeqTable is defined at src/lib.rs:35:

#[pyclass]
pub struct LTSeqTable {
    session: Arc<SessionContext>,       // DataFusion session, shared across tables
    dataframe: Option<Arc<DataFrame>>,  // Lazy DataFrame
    schema: Option<Arc<ArrowSchema>>,   // Cached Arrow schema
    sort_exprs: Vec<String>,            // Current sort keys
    source_parquet_path: Option<String>, // Original Parquet path (for optimization)
}

PyO3's single #[pymethods] constraint drives much of the architecture. Rust allows only one #[pymethods] block per struct, so 30+ Python-facing methods all live in a single impl block. LTSeq handles that with delegation:

// src/lib.rs -- all methods are 1-3 line forwarding stubs
fn search_first(&self, expr_dict: &Bound<'_, PyDict>) -> PyResult<LTSeqTable> {
    crate::ops::basic::search_first_impl(self, expr_dict)
}

fn asof_join(&self, other: &LTSeqTable, ...) -> PyResult<LTSeqTable> {
    crate::ops::asof_join::asof_join_impl(self, other, ...)
}

The actual implementations are distributed across 18 modules under src/ops/, organized by functionality: basic, derive, window, join, aggregation, grouping, set_ops, pattern_match, linear_scan, parallel_scan, and more. That keeps concerns separated while satisfying PyO3's compilation constraint.

3.2 Runtime engine: dual SessionContext strategy

src/engine.rs provides two SessionContext factories, one per kind of data flow:

// Parallel context: for aggregation, JOIN, and other parallelizable operations
pub fn create_session_context() -> Arc<SessionContext> {
    SessionConfig::new()
        .with_target_partitions(*NUM_CPUS)  // Multi-partition parallelism
        .with_repartition_joins(true)
        .with_repartition_aggregations(true)
    // Parquet predicate pushdown
    config.options_mut().execution.parquet.pushdown_filters = true;
    config.options_mut().execution.parquet.reorder_filters = true;
}

// Sequential context: for window functions, sorting, and other order-preserving operations
pub fn create_sequential_session() -> Arc<SessionContext> {
    SessionConfig::new()
        .with_target_partitions(1)          // Single partition preserves order
        .with_repartition_joins(false)
        .with_repartition_aggregations(false)
}

Why target_partitions=1? Because DataFusion in multi-partition mode inserts SortPreservingMergeExec and CoalescePartitionsExec nodes to merge partition outputs. For streaming processing of pre-sorted data, these extra nodes add overhead with zero benefit. Single-partition mode lets execute_stream() return ordered batches directly from the partition.

3.3 Python API layer: mixin composition

The LTSeq class distributes its API across 6 mixins via multiple inheritance, each corresponding to a functional domain:

class LTSeq(IOMixin, TransformMixin, JoinMixin,
             AggregationMixin, SetOpsMixin, AdvancedOpsMixin):
    def __init__(self):
        self._inner = ltseq_core.LTSeqTable()  # Rust object
        self._schema: Dict[str, str] = {}       # Python-side schema
        self._sort_keys: Optional[List] = None  # Sort state tracking

Every operation is immutable: it returns a new LTSeq instance and never modifies the original.

def filter(self, predicate):
    expr_dict = self._capture_expr(predicate)
    result = LTSeq()
    result._inner = self._inner.filter(expr_dict)
    result._schema = self._schema.copy()
    result._sort_keys = self._sort_keys  # filter preserves sort order
    return result

Sort state propagates as follows: filter and derive preserve sort keys unchanged (these operations don't affect row order), while union and distinct set _sort_keys to None (order is destroyed).

3.4 Derived data structures: lazy evaluation

LTSeq has four derived structures, all employing lazy evaluation:

Class	Creation	Lazy Strategy
LinkedTable	t.link(other, on=..., as_="alias")	JOIN is only executed when linked columns are accessed
NestedTable	t.group_ordered(cond)	count() takes a fast Rust path, avoiding materialization
_LazyFirstLTSeq	nested.first()	count() doesn't build per-row arrays
Cursor	LTSeq.scan()	Streaming batch iteration via Arrow IPC

LinkedTable's lazy strategy is worth a closer look. During filter(), it checks whether the predicate only involves source table columns:

def filter(self, predicate):
    try:
        _lambda_to_expr(predicate, self._source._schema)
        # Predicate only involves source table -> no JOIN materialization
        filtered_source = self._source.filter(predicate)
        return LinkedTable(filtered_source, self._target, ...)
    except AttributeError:
        # Predicate involves linked columns -> must materialize
        return self._materialize().filter(predicate)

4. Data flow: from Python lambda to Arrow output

A complete execution flow (using filter as example):

User code: t.filter(lambda r: r.age > 18)
  |
  +-- [Python] SchemaProxy capture
  |   r.age -> ColumnExpr("age")
  |   > 18  -> BinOpExpr("Gt", ColumnExpr("age"), LiteralExpr(18))
  |
  +-- [Python] .serialize()
  |   {"type":"BinOp","op":"Gt","left":{"type":"Column","name":"age"},
  |    "right":{"type":"Literal","value":18,"dtype":"Int64"}}
  |
  +-- [Rust] dict_to_py_expr() -> PyExpr enum
  |
  +-- [Rust] optimize_expr() -> constant folding + boolean simplification
  |
  +-- [Rust] pyexpr_to_datafusion() -> DataFusion Expr
  |   col("age").gt(lit(18))
  |
  +-- [DataFusion] df.filter(expr) -> new lazy DataFrame
  |
  +-- [Rust] LTSeqTable::from_df_with_schema() -> new LTSeqTable

One subtle but critical detail: DataFusion's col() function lowercases column names (src/transpiler/mod.rs:47). LTSeq uses Column::new_unqualified(name) to preserve case-sensitive column names:

fn parse_column_expr(name: &str, schema: &ArrowSchema) -> Result<Expr, String> {
    // col() function lowercases, breaking names like "IsOfficial"
    Ok(Expr::Column(Column::new_unqualified(name)))
}

5. Summary: core architectural trade-offs

LTSeq's architecture embodies several explicit engineering trade-offs:

1. Use DataFusion by default for query optimization, and bypass it for sequence operations.
2. Lazy first. LinkedTable, NestedTable, and the DataFrame itself are all lazy, materializing only when needed.
3. Immutable operations. Every operation returns a new instance, which simplifies concurrency semantics and debugging.
4. Metadata propagation. Sort state (_sort_keys) propagates precisely through the operation chain, and window functions rely on it to avoid redundant sorting.
5. Dual execution paths. The system picks between DataFusion for general work and direct Parquet scanning for specialized work, based on the operation and data source.

Next article: the expression system, and the pipeline that turns Python lambdas into Rust-executable code.