TiLT: A Time-Centric Approach for Stream Query Optimization and Parallelization

Stream processing engines run continuous queries such as moving averages over stock prices or QRS detection in an ECG, but they describe every query as a graph of operators over events, which hides the time structure that an optimizer needs, so they cannot fuse operators past a window or a join and cannot parallelize without the user partitioning the data — TiLT describes a query instead as functions over time itself, a temporal object with a value at every instant, which makes fusion a textual substitution, makes parallel partition boundaries derivable from the query, and compiles to code that runs eight real analytics applications 6 to 326 times faster than Microsoft Trill.

The argument in one glance

Problem

One machine can run a streaming query hundreds of times faster than a cluster, if the engine is good enough

Streaming analytics runs continuous queries over unbounded time-ordered events: trend signals on stock ticks, fraud rules on card transactions, QRS detection on ECG waveforms. Scale-out engines such as Spark and Flink reach 0.14 and 0.59 million events per second on the Yahoo benchmark on a 32-core machine, while scale-up engines reach 34 to 296 million. But every scale-up engine has to solve three problems at once: optimize for cache locality, parallelize across cores, and keep runtime overhead low.
What people did

Interpreted engines with rich languages, or compiled engines with narrow ones

Trill and StreamBox interpret a dataflow graph of temporal operators, offering expressive SQL-like languages with windows and joins. LightSaber and Grizzly compile queries to native code and parallelize windowed aggregation automatically, reaching much higher throughput on aggregation benchmarks.
Why it fell short

Graph-level optimization stops at pipeline breakers; parallelism needs partitions; compilers only do aggregation

Fusion in current engines cannot cross a soft pipeline breaker, an operator such as a windowed sum or a join that must partially materialize its output, and the paper's eight applications each contain two to six of them. Predicate pushdown fails whenever the filter depends on a join. Parallelization relies on user-partitioned streams, or on tricks specific to windowed aggregation that do not tell you where to cut a stream that has two sliding windows and a join. Interpreters pay data-transfer and managed-language overhead; the compiled engines do not support joins at all.
This paper's idea

Describe the query as functions over time, then let a compiler do the rest

TiLT is an intermediate representation in which a stream is a temporal object, a value defined at every instant that equals the active event's payload or null, and a query is a sequence of temporal expressions, each defining an output temporal object as a pure function of inputs over a time domain, with reduction functions for aggregation. Because every operator is a pure function of time, fusion is substitution of one expression into another, even across windows and joins; the data each output instant depends on can be traced back to an input interval, so any query can be cut into independent chunks and run on synchronization-free threads; and an LLVM backend compiles the result to loops over snapshot buffers that advance only when an input changes. On eight real applications TiLT is 6.29 to 326.30 times faster than Trill, 20.49 times on average, and it beats LightSaber and Grizzly on their own benchmark by 1.5 and 3.8 times.

Why this problem is worth solving

A hospital monitors a patient’s ECG at a kilohertz, and a Pan-Tompkins detector must find every QRS complex within a fraction of a second. A bearing sensor in a factory emits 40,000 samples a second, and a vibration monitor computes kurtosis, root mean square and crest factor over 100-millisecond windows to predict failure. A trading desk computes 10-second and 20-second moving averages of every stock and fires when the short one crosses the long one. These are

continuous queries

A query that runs indefinitely over an unbounded, time-ordered sequence of events, producing output as new events arrive.

, and their common feature is that the time dimension is the computation: windows, offsets, overlaps, resampling.

stream processing engine

A system that executes continuous queries over event streams; scale-out engines spread work over a cluster, scale-up engines maximize one machine.

that runs such a query on one machine can be a hundred to a thousand times more cost-effective than a cluster, as the paper’s Table 1 shows: Trill at 34 million events per second and LightSaber at 296 million against Flink at 0.59 million on the same 32 cores. The trouble is that no single engine gives both the language needed to express the eight applications above and the performance of the best compiled engines. The paper’s diagnosis is that the missing ingredient is not engineering effort but the representation: current engines cannot see enough of the query’s time semantics to optimize and parallelize it.

What people did before, and where it broke

Interpreted scale-up engines: Trill, StreamBox, BriskStream. A query is a directed acyclic graph of temporal operators, each a hand-written implementation that processes events or micro-batches and passes results through queues. Where it broke. One to two orders of magnitude of overhead from inter-operator data transfer, managed-language costs and fixed micro-batching. Optimizations are graph rewrites such as predicate pushdown, which needs a filter that depends only on the source; in the stock-trend query the filter depends on the join, so it cannot move. Fusion stops at

soft pipeline breakers
An operator, such as a windowed aggregation or a temporal join, that must partially materialize its output before the next operator can proceed, blocking naive fusion.
, of which each real application has two to six.
Compiled engines: SABER, LightSaber, Grizzly, Scabbard. Generate native code from the query and parallelize windowed aggregation by splitting into tumbling partials and reducing them. Where it broke. They target aggregation only; none supports a temporal join, so they cannot express the eight applications. Their code generators are template expanders, which the paper, citing prior work, calls hard to maintain and extend.
Partition-based parallelism. Run the same query on each key of a partitioned stream, one stock per thread. Where it broke. Parallelism is capped by the number of keys, and a single healthcare or manufacturing stream can run at 1 to 40 kilohertz on one key.
The gap. No representation let an engine fuse across pipeline breakers, derive partition boundaries for arbitrary queries including joins, and generate efficient code, all at once.

Where TiLT sits

The TiLT compilation pipeline

User query

Written with familiar temporal operators: Select, Where, Window-Sum, Join, Shift, Chop, custom aggregates.
↓ →
Lower to TiLT IR new

Each operator becomes a temporal expression over an infinite time domain; the input stream becomes a temporal object.
↓ →
Boundary resolution new

Follow each output's temporal lineage back to the input to learn which input interval an output interval depends on; rewrite the time domain as a symbolic (Ts, Te].
↓ →
Optimization new

Fuse successive expressions on the same time domain by substitution, including across windows and joins, until the query is one expression.
↓ →
Code generation new

Lower to LLVM IR: snapshot buffers for temporal objects, four-lambda templates for reductions, change-driven loops for expressions, wrapped in a function of (Ts, Te).
↓ →
Parallel execution new

Partition the input snapshot buffer at resolved boundaries and run independent worker threads with no synchronization.

Everything after the user query is new. TiLT is written in C++ on LLVM's JIT and is open source.

The idea

Streams as functions of time. The

event-centric model

The conventional view of a stream as a sequence of discrete events, each with a payload and a validity interval, and of operators as transformations over events.

is natural, since streams really are sequences of events, but an operator defined over events does not say how it manipulates time. TiLT’s

time-centric model

TiLT's view: a stream is a single value that evolves over an infinite timeline, and an operator is a pure function from input values to output values at each instant.

instead defines a

temporal object

A stream represented as a value defined at every point in time: the payload of the event active at that instant, or the null value phi if none is active.

, written with a tilde, whose value at time T is the payload of the event whose validity interval contains T, or φ if none does. Any arithmetic on φ yields φ. Indexing with an interval, such as stock[t−10 : t], yields a derived temporal object that is φ outside the interval.

Reductions and expressions. A

reduction function

An operation that collapses a temporal object over an interval to one scalar, such as sum, product, min or max, or a user-defined accumulator.

⊕(f, win) folds all non-φ values of a temporal object. A

temporal expression

A definition of an output temporal object as a function of input temporal objects and constants over a time domain with a start, an end and a precision.

writes O[t] = Fn(I1, …, In, C1, …, Cm) over a time domain TDom(Ts, Te, p), meaning O takes that value at every multiple of p in (Ts, Te]. With these three constructs the four classic operators become near-identical one-liners: Select is m[t] + 1; Where is a conditional returning φ; Join is a conditional on both inputs being non-φ; a 10-second window sum with 5-second stride is ⊕(+, m[t′−10 : t′]) over a domain of precision 5. The uniformity is the point: what looked like four different operator semantics is one shape.

Boundary resolution makes parallelism derivable. Because each expression is a pure function of its inputs at, or in an interval around, the same instant, the value of an output at time T has a

temporal lineage

The set of input time intervals that an output value at a given instant depends on, found by following expression definitions back to the source stream.

. In the stock-trend query, filter[T] depends on stock over (T−20, T]. So the outputs over any interval (Ts, Te] depend only on inputs over (Ts−20, Te]. TiLT rewrites the time domain symbolically to TDom(Ts, Te, 1) and later uses this to cut the input stream into chunks that overlap by 20 seconds, each processed by an independent thread with no locks, no atomics and no shared state.

Fusion becomes substitution. Two successive expressions over the same time domain fuse by replacing each occurrence of the first’s output in the second with the first’s body. Nothing distinguishes a windowed sum or a join from a select in this rule, so the whole stock-trend query, two sums, two averages, a join and a filter, collapses into one expression that reads stock twice, computes both averages, their difference, and the sign test, and returns a value or φ. Current engines cannot express this fused form because the graph is too coarse and because the intervals produced by a join are only known at runtime; TiLT’s expressions encode the time transformations explicitly.

Compilation without redundancy. A temporal object literally defined at every instant would be absurd to materialize, so TiLT stores only changes in a

snapshot buffer

An ordered array of (timestamp, value) pairs recording each point at which a temporal object's value changed.

. Reductions follow a four-lambda template, init, accumulate, result and an optional de-accumulate, which supports subtract-on-evict for invertible sliding windows. Each temporal expression becomes a loop over (Ts, Te]; instead of stepping the counter by the precision, the compiler emits an expression that jumps to the next timestamp at which any input’s enclosing snapshot changes, using the invariant that a pure function’s output cannot change while its inputs are constant. The loop is wrapped in a function of (Ts, Te), so the same code runs any chunk.

Tracing the stock-trend query through TiLT

From four operators to one parallel loop

The paper's running example: two moving averages of a stock price over 10 and 20 seconds, joined by subtraction, filtered for positive difference. phi is the null value. Times in seconds.

Step 1 of 6

The query as operators

Window(10,1).Sum and Window(20,1).Sum on the stock stream; Select divides each by its window size; Join subtracts; Where keeps positive values. Both sums and the join are soft pipeline breakers, so a conventional optimizer can fuse the selects into the join and nothing else.

ops: Sum10, Sum20, Select/10, Select/20, Join(-), Where(>0) | breakers: 3

Why it works

Purity exposes dependency. Because each expression is a side-effect-free function of its inputs at nearby instants, the exact input interval feeding any output interval can be computed at compile time. That is what turns an arbitrary query, joins included, into independent chunks.
A uniform representation makes one rewrite rule universal. Since a window sum, a join and a select are all temporal expressions, the substitution rule that fuses selects also fuses through pipeline breakers. The engine no longer needs a catalogue of special cases.
Time is explicit, so the optimizer is not guessing. Event-centric operators hide how intervals are transformed; the join’s output intervals appear only at runtime. TiLT’s expressions state the transformation on the time domain, so the compiler knows it.
Change-driven loops remove the cost of fine granularity. Defining values at every instant is free at compile time and would be ruinous at run time; skipping to the next input change restores the efficiency of event processing while keeping the semantics of time.
Compiled code beats hand-written operators. Even without fusion, TiLT’s generated code runs the example query 2.61 times faster than Trill’s optimized version, because the interpreter’s queues and managed-language overhead are gone; fusion then raises it to 8.55 times.
No shared state means near-linear scaling. Grizzly’s atomic state updates and LightSaber’s parallel aggregation trees are the scalability limits the paper measures; TiLT’s threads share nothing.

What it costs

Redundant work at chunk boundaries. Each chunk recomputes the lineage-depth prefix of its neighbour. For long windows relative to the chunk size, or deep lineage, the duplicated fraction grows.
Memory-bound at high thread counts. Scaling is near-linear to 4 threads on the 12-core machine and 8 on the 32-core, then flattens as the query becomes memory-bound.
Overlapping events need heavier snapshots. When a stream has overlapping validity intervals, a snapshot must hold a list or map of values, which the paper treats as an implementation detail rather than a measured case.
Only fusion is explored. The paper implements one optimization and explicitly leaves others to future work; the claim is that the IR enables them, not that they exist yet.
Compute-only measurements. Throughput excludes disk and network, with the whole dataset preloaded in memory; end-to-end systems with ingestion will see lower numbers.
Compilation is on the critical path for new queries. LLVM JIT compilation happens per query; the paper does not report compile latency.

The evaluation

All measurements on AWS m5.8xlarge (32 cores with hyper-threading, 2.5 GHz, 128 GB) and m5zn.3xlarge (12 cores, 4.5 GHz) for scalability, on 160 million events, averaged over five runs with under 2 percent deviation. Baselines: Trill (C#, interpreted, expressive), StreamBox (C++, interpreted, pipeline-parallel), and the compiled aggregation engines LightSaber and Grizzly.

Throughput comparison, 16 worker threads unless noted

Property	Trill	StreamBox	Grizzly	LightSaber
Select and Where, per-event operators	similar	similar	similar	similar
Window-Sum	1x
Temporal Join			unsupported	unsupported
Yahoo Streaming Benchmark, peak, 32-core	worst scaling; partitioned only	scales to 8 threads	limited by atomics
Eight real applications versus Trill	1x	cannot express all eight	no join	no join
Latency-bounded throughput, batch 10 to 1 M events		—	—	—
Fusion ablation, stock-trend query, one thread		—	—	—

From Figures 7 to 10 and Table 1 of the paper. The eight applications are trend trading, relative strength index, normalization, signal imputation, resampling, Pan-Tompkins QRS detection, vibration analysis and fraud detection, on NYSE, MIMIC-III, bearing vibration and Kaggle credit-card data plus synthetic 1 kHz signals.Underlined values explain themselves when clicked.

In an actual implementation

Why a temporal object needs phi

Between events a stream has no value, and an operator applied to nothing must produce nothing. TiLT makes this a first-class value, φ, with the rule that any arithmetic involving φ yields φ. That rule does surprising work. A Where operator is written as a conditional that returns φ when the predicate fails, so filtering is just producing null at those instants. A Join is a conditional that returns φ unless both inputs are non-φ, so the strictly overlapping intervals of two streams fall out of the null-propagation rule with no interval arithmetic at all. And a reduction sums only the non-φ values in its window. Because every operator is expressed through the same null semantics, the substitution rule that fuses expressions never has to reason about intervals; φ carries the time structure through the fused code.

Where this stops working

TiLT’s parallelism recomputes the lineage prefix at every chunk boundary, so queries whose outputs depend on very long histories relative to the chunk size waste proportionally more work, and a query with unbounded lineage would not partition at all. The paper measures compute-only throughput with data preloaded, so ingestion and I/O costs are absent, and it reports fusion as the only optimization implemented, with others deferred. Scaling flattens once the query is memory-bound, at 4 to 8 threads on the tested machines. Streams with overlapping event intervals require list-valued snapshots, which the paper mentions but does not evaluate. Finally, the largest single number, 326 times on resampling, reflects an inefficient Chop implementation in Trill as much as TiLT’s strengths; the 20.49 times average and the 1.5 to 3.8 times over compiled aggregation engines are the more representative figures.

Background

The same shift that made relational compilers fast

Relational databases went through this transition a decade earlier. Iterator-model engines interpreted a tree of operators, passing one tuple at a time through virtual calls, until compiled query engines showed that generating a single tight loop per pipeline could be an order of magnitude faster. The obstacle there was also representation: operators had to be reformulated so a code generator could fuse them until a pipeline breaker, the point at which a hash table or sort must materialize. TiLT’s contribution is to observe that in streaming the pipeline breakers are the time operators, windows and joins, and that if you define the query over time rather than over events, those breakers dissolve into ordinary expressions and the fusion continues. The snapshot buffer and change-driven loop are then the streaming analogue of the tight loop over columns.

If you remember only three things

1. Scale-up stream engines can be hundreds of times more cost-effective than clusters, but each one gives up something: interpreted engines like Trill have rich languages and high overhead, and cannot fuse past windowed sums or joins; compiled engines like LightSaber and Grizzly are fast on aggregation but cannot express joins; and parallelism depends on user partitions or aggregation-specific tricks. The paper blames the event-centric query representation, which hides the time semantics an optimizer needs.
2. TiLT represents a stream as a temporal object, a value at every instant that is the active event's payload or null, and a query as temporal expressions, pure functions of inputs over a time domain, with reduction functions for aggregation. Purity lets boundary resolution trace any output interval back to the input interval it depends on, so any query, joins included, is cut into independent chunks for synchronization-free threads; uniformity lets fusion be plain substitution through every pipeline breaker; and an LLVM backend compiles the fused expression to a change-driven loop over snapshot buffers.
3. On eight real applications TiLT is 6.29 to 326.30 times faster than Trill, 20.49 times on average; on the Yahoo benchmark it reaches 450 million events per second on 32 cores, 1.5 times LightSaber and 3.8 times Grizzly; it is 13.87 times faster than Trill on temporal join, which the compiled engines cannot run at all. The ablation attributes 2.61 times to compilation alone and the rest to fusion. Costs are recomputed chunk prefixes, memory-bound scaling beyond 8 threads, compute-only measurements, and a single implemented optimization.

Check yourself

Check your understanding

1. What is the difference between the event-centric and time-centric models of a streaming query?
2. Why can TiLT fuse a windowed sum, a join and a filter into one expression when Trill cannot?
3. Predict what happens to TiLT's parallel efficiency if the stock-trend query used 900-second moving averages instead of 10 and 20 seconds, with the same 1,000-second chunks.
4. What is a snapshot buffer, and why does the generated loop not step through every second?
5. Which result best separates the benefit of compilation from the benefit of the time-centric representation?

Sources

The paper is “TiLT: A Time-Centric Approach for Stream Query Optimization and Parallelization” by Anand Jayarajan, Wei Zhao, Yudi Sun and Gennady Pekhimenko, University of Toronto and Vector Institute, published at ASPLOS 2023, Volume 2, DOI 10.1145/3575693.3575704. This explainer was written from the full text of the arXiv preprint (2301.12030, version 1, January 2023), including its artifact appendix. Numbers are taken from Tables 1 and 2 and Figures 1 to 10. TiLT is open source at github.com/ampersand-projects/tilt, and the benchmark suite with Trill and TiLT implementations of all eight applications is archived on Zenodo (record 7493145).