arXiv:2606.14069v1 [cs.DB] 12 Jun 2026
Vivace: Exact Temporal OLAP over Interval Histories via Independent Serverless Execution Woohyeok Park
Taeyoon Kim
Department of Data Science Hanyang University Seoul, Republic of Korea [email protected]
Department of Data Science Hanyang University Seoul, Republic of Korea [email protected]
Abstract—Temporal online analytical processing (OLAP) analyzes past states of data whose values change over time. Such histories are naturally stored as interval histories, in which each row records the period during which a value remained valid. Because temporal analyses typically arrive in infrequent, intermittent bursts, serverless execution that launches functions only at query time offers a cost advantage over always-on clusters. Splitting a computation that a single process performs as a whole across independent serverless functions, however, breaks correctness in two ways. A function may not receive the rows that determine the state of its time range, and naively summing partial results yields incorrect answers for durationweighted and cumulative-threshold queries. Existing SQL engines and serverless analytics do not address both problems together. This paper presents Vivace, a serverless system for exact temporal OLAP over interval histories. Vivace resolves the two problems in separate stages. Before any query arrives, a prequery layout step partitions the interval history, replicating boundary-crossing intervals so each function computes its range completely from a single file. At query time, a merge step combines partial results under operator-specific rules. Associative aggregates merge intermediate values, and ranking re-orders candidates within each time range. We prove that this partitioned execution matches single-process computation up to canonical form. Evaluated on AWS Lambda with real-world datasets, Vivace reduces latency and monetary cost by up to 82% and 84%, respectively, against an equivalent SQL baseline that queries the history directly, demonstrating robust generality and efficiency.
I. I NTRODUCTION Temporal online analytical processing (OLAP) analyzes past states over the history of data that changes over time, supporting tasks such as post-incident investigation, quarterly market comparison, and regulatory audits over prices, inventory, and equipment configurations. The accumulated changes are commonly stored as an interval history [1], which records each period of an unchanged value as a single [From, To) row and thus preserves a long history at far lower storage cost than per-time-point snapshots. Because temporal analyses typically exhibit intermittent access patterns [2]–[4], an always-on cluster incurs high idle costs, whereas the serverless execution, which launches only at query time, offers a compelling cost advantage for sporadic workloads [2], [5]–[8]. The benefit of serverless execution is maximized when functions execute independently without sharing state. However, splitting a monolithic temporal computation across independent functions breaks correctness. Naively partitioning interval
Hyunjoon Kim
Kyungyong Lee†
Department of Data Science Department of Data Science Hanyang University Hanyang University Seoul, Republic of Korea Seoul, Republic of Korea [email protected] [email protected]
data by time range loses information for rows crossing boundaries, preventing functions from reconstructing the true state. Furthermore, simply summing partial results from multiple parallel function executions breaks duration-weighted averages and cumulative counts. Sharing state between functions can compensate, but the added latency and data-movement costs offset the serverless advantage [9]. Therefore, exact independent execution requires two conditions. Input completeness requires each function to receive every row affecting its time range, and Operator-correct merge requires partial results to be combined using semantics-aware aggregation rules. However, existing approaches satisfy at most one of the two. Object-storage SQL engines such as Athena [10] and BigLake [11] can read interval histories, but users must handwrite the overlap detection and boundary clipping logic in every query. Serverless analytics engines such as Lambada [2] and Starling [5] provide cost-efficient function execution over object storage, but they target only general relational data and offer neither specialized temporal representation nor merge techniques that interval overlap, duration weighting, and pertime-point counting require. Timeline Index [12] and ParTime [13] compute temporal analytics efficiently in-memory, which is costly for large, rarely-accessed histories. This paper proposes Vivace, a serverless temporal OLAP system that satisfies both requirements while keeping every function execution independent. Vivace resolves each requirement in a separate stage. During the pre-query phase, a layout step divides the interval history at fixed time boundaries, splitting every interval that spans a boundary, so that each partition file holds the complete state of its own time range. Each function therefore reads a single file and obtains every row its range needs (input completeness). At query time, each function evaluates the operator over its own range and emits a compact partial result. A reducer then merges these partial results under operator-specific rules and applies the final computation only once (operator-correct merge). Neither stage shares state between functions, and we prove as a theorem that the merged result equals the single-process result up to canonical form, which is a property we call exactness. To the best of our knowledge, Vivace is the first system to characterize the conditions under which temporal OLAP over interval histories decomposes exactly across independent
Scan
1
4
16 64 256 1K
Queries Per Hour
(a) Serverless cost model.
40 20 0
Exchange
34.0 15.6
State moved (MB)
1000 100 10 1
Always-on Always-on (S3) Latency (s)
Monthly Cost (USD)
FaaS (S3) QaaS (S3)
d nt ple nde Cou epe Ind
Sweep 11.32
10 5 0.44
0
ed
pl Cou
nt
nde
epe
Ind
(b) Coupled vs. Independent execution.
Fig. 1: Motivating characteristics of serverless temporal OLAP. serverless functions. While the underlying techniques are standard, no prior work establishes when the combination preserves single-process semantics. We implemented Vivace on public-cloud FaaS and evaluated it on real datasets with diverse interval characteristics [14]–[16]. Every operator reproduced the single-process ground truth exactly. For a SQL baseline of identical semantics, Vivace eliminated the input-preparation cost that grows with history depth, reducing latency and cost. Contributions. The contributions of this paper are as follows. • Problem formulation. We formalize input completeness and operator-correct merge, the conditions under which independent functions compute temporal OLAP over an interval history, each from its own input alone (§IV, §IV-A). •
System design. Vivace pre-partitions the interval history by time so that each function computes its range from a single file, and merges partial results under operatormatched rules. It supports predicate windows, durationweighted aggregation, counts over time, and cross-entity comparison (§III–§IV-C).
•
Exactness proof. For every supported analysis, we prove that partitioned parallel execution equals single-process computation up to canonical form (§V-C).
•
Empirical evaluation. On three datasets with different change rates, Vivace reduces latency by up to 82% and cost by up to 84% against a SQL baseline, and the same operator families answer every query of an independent SCD Type 2 benchmark without new primitives (§VI). II. P ITFALLS OF S ERVERLESS T EMPORAL OLAP
Operational data such as airline ticket prices, e-commerce inventory, and equipment configurations change continuously, and their histories accumulate. Since snapshotting every measurement time grows the row count as entities × time points, the common practice is to record a new row only when a value changes. Lakehouse engines such as Iceberg and Delta Lake expose change histories through their table formats, storing them in object storage over long periods [17], [18]. A. Temporal OLAP over Slowly Changing Dimensions We call a history stored around its change points an interval history, where each value change closes the previous interval and opens a new one, so each row holds one entity’s value together with the interval during which it persisted. For example, if a product’s price became $10 on March 18 and
held until May 3, the entire period is one row. This corresponds to slowly changing dimension (SCD) Type 2 in data warehouse modeling [1]. We denote a row as (K, V, [From, To)), where K is the primary key and V its value during the interval, and call a set of such rows the valid-from/to source relation. Temporal OLAP extends traditional OLAP, which aggregates measures over dimensions for decision support [19], [20], to interval-valued queries over historical time ranges. For example, answering “during which intervals in the second quarter was the price at most $10?” requires examining the change points within the requested range. Temporal database research has established sequenced semantics, which folds pertime-point query results into [From, To) rows, and coalescing, which merges adjacent rows with identical payloads into maximal intervals, as the standard for result comparison [21], [22]. These analyses involve overlap detection, boundaryaligned clipping, duration-weighted aggregation, and per-timepoint counting, whose cost grows as the history accumulates. B. Serverless Analytics For histories that accumulate over long periods but are read only occasionally, an always-on cluster continuously pays for data loading, index and cache maintenance, and idle resources. The Function-as-a-Service (FaaS) approach instead launches functions only at query time, reads only the required data in parallel, and bills only actual execution [2], [5], [8]. As Fig. 1a shows, FaaS and Query-as-a-Service (QaaS) costs scale with query count while always-on costs do not, so the gap widens sharply when analysis is infrequent.1 C. Execution Models for Interval-History Analytics Existing systems compute exact interval-history analytics through the built-in distributed state exchange of managed services [10], [11], through explicit intermediate state exchanged via shared storage in FaaS engines [2], [5], or through userwritten overlap/clipping SQL. All of these incur additional data movement or coordination at query time, and none supports the independent execution, in which each worker reads the single file of its time range, computes its result without exchanging temporal state among workers, and ships only compact partials to the reducer. The difficulty of independent execution surfaces in queries that compare multiple entities on the same time axis, such as finding the lowest-priced entity at each time point in a 10K-entity cohort. Fig. 1b decomposes the latency of this query into Scan (locating intervals visible in the window), Exchange (moving intermediate state through shared storage), and Sweep (comparing intervals within each time bucket), along with the intermediate state crossing the mapper–reducer boundary (12month 10K cohort, identical input and Lambda configuration). The Coupled plan follows existing FaaS engines [2], [5], where workers re-write the visible intervals into time-range buckets in shared storage, and the reducer reads each bucket 1 Based on a query reading a 1 GiB compressed interval history. FaaS cost is measured; QaaS and always-on paths use us-west-2 public prices (June 2026), with the instance sized by the measured memory footprint.
A
$10
01
March
Layout Step
Source Relation
$20 31 01
A, $10, [Mar 18, May 3) March File
30 01
April No Row Data
April File
May
31
A, $20, [May 3, Jun 1)
May File
Reducer Merge
(R1)
April Worker $10: [Apr 1, May 3) = 32d
Input
Completeness
(R2) Weighted Average
Operator-Correct Merge
Naive Average
May Worker $20: [May 3, Jun 1) = 29d
(10 × 32 + 20 × 29) / (32 + 29) = 14.75 :A (10 + 20) / (2) = 15.00
Q: What is the average price of product A during [Apr 1, Jun 1)?
Fig. 2: Naive serverless fan-out breaks at two points.
Key Value From A 5 03-01 A 7 03-20 B 2 03-01 C 4 03-01
To 03-20 04-15 04-03 04-01
Mapper Step
Read Partitions
Mapper 1 -Read Mar Mapper 2 -Read Apr 5 A Mapper 3 -ReadBMay 2 4 C Mapper ? - Read ? File
Split layout A 5
7
Time Partitions March File
9
B 2
1
C 4
1
6 5
March April
May
Local-Execution
Clip to Query
Windowend start
Construct Segment Stream
9 5
April File
A, 5, [03-01, 03-20) A, 7, [03-20, 04-15) B, 2, [03-01, 04-03) C, 4, [03-01, 04-01)
A, 7, [03-20, 04-15) A, 9, [04-15, 05-30) B, 1, [04-03, 05-01) C, 1, [04-01, 04-10) C, 5, [04-10, 05-30)
Carrier Output
6
W C∆
SO1 ... SO4, AO1 ... AO4
A
Evaluate Operator
Reducer Step
Carrier Merge
to rank entities per time point. Intervals crossing bucket boundaries are replicated, inflating the reducer input to more than twice the source intervals. This state movement and replica reprocessing dominate total latency. The Independent plan instead materializes the same time division as a pre-query layout. Because each worker’s file already holds its intervals clipped to its range, the worker ranks entities within its own input and ships only a compact output to a reducer. For the same query, intermediate state movement thus drops by 25× and total latency falls below half. Even for cross-entity queries, closing temporal state inside the mappers reduces both the shared-storage exchange and the reducer-side reprocessing. D. Requirements for Partitioned Temporal OLAP Consider the fan-out structure [7] of Fig. 2. The query window is divided into time ranges, one mapper handles each range, and a reducer collects the partial results. Product A costs $10 during [Mar 18, May 3) and $20 during [May 3, Jun 1). With each row stored in the file of the month containing its start time, the $10 row lands in March, the $20 row in May, and April holds nothing. Computing “the average price of A during [Apr 1, Jun 1)” exactly imposes two requirements. •
Input completeness (R1): Each mapper must receive every row that determines the state of its range. Here the [Mar 18, May 3) → $10 row sits in the March file yet determines the April price, so the April mapper misses it unless it also reads March.
•
Operator-correct merge (R2): Partial results must be combined by rules matching the operator’s semantics. The correct average over [Apr 1, Jun 1) weights by duration, (10 × 32 + 20 × 29)/(32 + 29) = 14.75, whereas averaging the per-mapper averages gives (10 + 20)/2 = 15.00. The same problem arises for count thresholds and ranking.
Finally, a fan-out result may fragment intervals at mapper boundaries, so comparison with the single-process result requires a canonical form that merges adjacent identical ranges.
Fan-Out
Reducer Reducer Mapper1 Mapper2 Mapper3 Mapper4
May
D Cstep
Finalize Carrier Merge Merged
Rule Carrier
Complete Carrier Output
Fig. 3: Vivace system overview.
independence minimizes query-time data movement and preserves serverless cost advantages. To satisfy R1 and R2 while preserving this independence, Vivace divides query processing into three steps (Fig. 3). Before any query, the layout step restructures the source relation so that every mapper’s input is complete, satisfying R1. At query time, each mapper evaluates its range and emits a partial result; the reducer merges these partials under operator-specific rules, satisfying R2. a) Layout: Vivace transforms the source relation into a time-partitioned layout once, before any query arrives. An interval crossing partition boundaries is split and stored in every file it spans. For example, in a monthly layout, the [Mar 18, May 3) → $10 row enters the March, April, and May files. Each range between two layout boundaries is a time chunk, and by default the planner assigns one chunk to one mapper, whose input thus holds the complete state of its range. b) Mapper: A mapper splits its range at every point where a value changes, producing a time-ordered segment stream. No value changes within a segment, so the persegment evaluator performs predicate evaluation, duration accumulation, count-delta derivation, or ranking comparison. The results reach the reducer as a Carrier, an intermediate format fixed per operator family. c) Reducer: Because naive summation violates R2 for some operators, each Carrier holds a combinable partial result and a finalize rule applied once after merging. For durationweighted averages, the weighted sums and durations are added across mappers, and the division is performed only at finalize. Chunk-fragmented results are then coalesced into canonical form for comparison with the single-process result. IV. DATA M ODEL AND O PERATORS
III. V IVACE OVERVIEW Vivace adopts independent execution where each mapper reads only the single file of its time range and ships results to the reducer, with no communication between mappers. This
Vivace handles the history of the values entities hold over time. Arranging the rows (K, V, [From, To)) of one entity in time order yields a timeline of when the entity held which value. We write this entire timeline as the interval history H,
the set of possible entities as K, and the values as V. The value entity K holds at time τ is written stateH (K, τ ), and since rows of the same entity never overlap in time, this value is unique at each time point. Over this data we define the layout, mapper, and reducer as a formal model. Storing this history directly as rows yields the valid-from/to source relation S. We assume each row holds the full state of its entity rather than a subset of columns, and call such rows full-state rows. A source that records only the changed columns is first reconstructed into full-state rows. A single row thus reveals every attribute of the entity at that time, so multiple predicates and aggregates can be evaluated over it. Given a query window W = [ts , te ), we write I(H, W) for the rows that overlap the window, clipped to its boundaries. After clipping, rows of the same entity still do not overlap, and each row’s V remains constant within its interval. All operators in this paper operate over this I(H, W). A. Segment Stream The rows a mapper receives from its partition file cannot be used directly for computation over time ranges. Multiple entities mix at the same time points, and the query window may cut through the middle of a time chunk. The mapper therefore cuts its range wherever a value changes and treats the span between two adjacent cuts as one segment. Definition 1 (Segment stream): Let P = [a, b) be the time range a mapper is responsible for, W = [ts , te ) the query window, and (K, V, [F, T )) a mapper input row. A row that overlaps both P and W is clipped as (K, V, [F ′ , T ′ )), F ′ = max{F, a, ts }, T ′ = min{T, b, te }. (1) The stream of clipped rows with F ′ < T ′ , sorted in ascending order of start time, is called the segment stream S(P, W). Segments of the same key do not overlap in time and V is constant within one segment, so every operator family takes this stream as a common input and processes it in time order. 1) Closed Segment Partition: When multiple mappers share the window, their results combine to equal the whole only if each mapper fully reproduces the state of its assigned range and keys from its own input. Each mapper piece, the unit dividing the window, is thus closed within its own input, and we call this condition the closed segment partition. Suppose the query window W is divided into nonoverlapping mapper pieces, where each piece (j, s) handles time chunk Pj and key subset Ks , and the pieces cover every time and key of W. Definition 2 (Closed segment partition): A mapper piece division {(j, s)} forms a closed segment partition if the local segment stream Sj,s of each piece equals the restriction of the global segment stream I(H, W) to that piece. If Ks = K, the partition is a time-only partition. Formally, for every K ∈ Ks and τ ∈ Pj , stateSj, s(K, τ ) = stateH (K, τ ).
(2)
2) Building the Segment Stream: A segment stream is built in one of two ways. The first projects a single interval relation directly into a segment stream. Since the same row carries the full state of all attributes, multiple predicates, aggregates, and boolean compositions are evaluated over the same segments. The second aligns the entities of a cohort C = {K1 , . . . , Km }, the entity set a query designates for comparison, onto common ranges. Every time point where any entity’s value changes becomes a segment boundary, so the entire cohort holds constant values within each segment and the evaluator can compare them together. B. Time-Partitioned Layout The time-partitioned layout is the mappers’ input, the source relation cut before queries arrive. It is built over predetermined time boundaries b0 < b1 < · · · < bM , and each range between adjacent boundaries [bℓ , bℓ+1 ) is a time chunk. The chunk width ∆chunk = bℓ+1 − bℓ is fixed at build time. Definition 3 (Time-partitioned layout): A layout over time boundaries b0 < b1 < · · · < bM places a partition file Πℓ for each time chunk [bℓ , bℓ+1 ), where Πℓ = (K, V, [max(F, bℓ ), min(T, bℓ+1 ))) | (3) (K, V, [F, T )) ∈ S, F < bℓ+1 , T > bℓ . Every row in Πℓ has its time interval contained in [bℓ , bℓ+1 ). Under this definition, a boundary-crossing source row is clipped and enters every partition file it spans, so the closed segment partition of §IV-A holds automatically once a mapper receives only its own partition file. In SQL/file baselines that scan the source relation directly, the mapper itself locates the rows overlapping its chunk to meet the same condition. We call this layout interval-clipped partitioning (ICP). Each partition file directly holds the (K, V, [From, To)) rows clipped to its time chunk, so a mapper reads it as the input of its range without further transformation. 1) Time-Chunk Granularity and Layout Size: The time chunk size ∆chunk jointly determines the storage volume and the mapper input size. ICP clips boundary-crossing intervals into every chunk they span, so as chunks shrink, one source interval is replicated across more chunks and the stored rows grow. We measure this inflation by the row amplification Arow and byte amplification Abyte relative to the source, and select the chunk width to keep both within budget. a) Lifetime and chunk width: A source interval of length ℓ crosses the boundaries of chunks of width w (= ∆chunk ) about ℓ/w times and is therefore clipped into about 1 + ℓ/w rows. Averaging over all intervals gives Arow (w) ≈ 1 +
ℓ̄ w
(4)
where ℓ̄ is the mean interval lifetime. Amplification thus tracks the ratio of mean lifetime to chunk width. With short lifetimes, amplification stays small even under frequent changes. With long lifetimes, the same interval is clipped into many chunks even under rare changes, inflating storage.
TABLE I: Operator families and mapper outputs. Family
Segment input
Per-segment computation
Mapper output
Final result
SO1 predicate window SO2 duration aggregate SO3 boolean composition SO4 count timeline AO1 pairwise compare AO2 count-better-than AO3 winner / top-k
same-base same-base same-base same-base aligned pair aligned cohort aligned cohort
φ(V ) x(V ) · (T − F ) φa ∧ φb , ∨, ∧¬ endpoint delta ±1 Vlef t ≺ Vright |{j : Vj ≺ Vref }| ranking per segment
interval window W duration partial D interval window W C∆ → Cstep aligned A (boolean) aligned A (count) aligned A (ranked)
per-key intervals where φ holds duration-weighted aggregate by group intersection, union, difference intervals group count timeline; threshold windows comparison timeline between two entities count timeline over better candidates winner or top-k timeline
b) Storage-safe time width: Let wsaf e be the smallest chunk width keeping amplification within the budgets ϵR , ϵB . wsafe = min{w : Arow (w) ≤ 1 + ϵR ∧ Abyte (w) ≤ 1 + ϵB }. (5) Chunks finer than wsaf e exceed the budget, so wsaf e is the lower bound on the chunk width, and the mapper input size is fitted by dividing primary keys rather than shrinking chunks. C. Operator Families Implementing each complex temporal query separately would require re-fitting the mapper input and the merge rules for every query type. Vivace instead defines a small set of basic operators and expresses more complex analyses as their compositions. As long as the basic operators guarantee fan-out execution and exact merging, queries composed from them inherit the same guarantee. Each operator reads a segment stream and produces an interval result or a timeline, and Table I summarizes the segment input, mapper output, and final result of each family. Predicate windows (SO1 and SO3), duration-weighted summaries (SO2), and count timelines (SO4) are same-base operators, whose results depend only on the V of a single row (§IV-C1). Aligned cohort timelines (AO1–AO3) are alignedcohort operators, which compare multiple entities of a cohort within the same segment (§IV-C2). The input is restricted to a single interval relation, or its join with time-invariant dimensional attributes. Analyses beyond this scope are not supported, because their results do not close over the mapper-local segment stream alone. An N -way temporal join requires inputs from multiple relations [23], a dynamic comparison cohort changes during execution, a sequential pattern needs ordering state across segment boundaries, and a sliding-window query needs overlap across partitions [24], [25] or prefix/suffix state [26]. 1) Same-Base Operators: a) Predicate window (SO1): For a predicate φ : V → {0, 1}, SO1 is defined as SO1 (I, φ) = {(K, V, [F, T )) ∈ I | φ(V ) = 1}.
(6)
The result is the full-state intervals where the condition holds. b) Duration-weighted aggregation (SO2): Given a function G(V ) that determines the aggregation group from a row’s value V and an expression x(V ) that extracts the quantity to aggregate, the duration-weighted average of group g is P i:G(Vi )=g x(Vi )∆i P TWAg = , ∆i = Ti − Fi . (7) i:G(Vi )=g ∆i
The mapper outputs the duration partial before the final ratio, P P x i ∆i , ∆i , n, min xi , max xi , (8) Dg = which carries the weighted sum, the total duration, the segment count, and the extremes of x for group g. The ratio is computed once after the Dg of all mappers are collected. c) Boolean composition (SO3): Predicates φa , φb are evaluated over the same full-state row, reducing computation to a boolean expression on one row without interval intersection. SO3I = {r ∈ I | φa (r.V ) ∧ φb (r.V )},
(9)
SO3U = {r ∈ I | φa (r.V ) ∨ φb (r.V )},
(10)
SO3D = {r ∈ I | φa (r.V ) ∧ ¬φb (r.V )}.
(11)
d) Count timeline and threshold (SO4): The number of entities in group g for which the predicate holds at time t is
Ng (t) = {(K, V, [F, T )) ∈ I | G(V ) = g, φ(V ), F ≤ t < T }
(12) The count timeline is the set of maximal intervals (g, [F, T ), Ng (F )) over which Ng (t) is constant. The threshold result keeps only the intervals with Ng (t) > c∗ . The mapper emits per-group +1/ − 1 deltas ∆g as C∆ at each endpoint of the intervals where the predicate holds, and the reducer builds the full count step timeline Cstep by cumulative summation in time order. 2) Aligned-Cohort Operators: Comparing multiple entities at the same time points requires their segment boundaries to coincide. To this end, all interval endpoints of the cohort C, the entity set the query designates, become common boundaries, and clipping each entity’s history at these boundaries yields the aligned segment stream. Within one aligned segment, every entity of C holds a constant value, so per-segment comparison is possible. Aligned-cohort operators apply their evaluators over this stream. Definition 4 (Cohort-closed input): The input of a mapper piece is cohort-closed with respect to cohort C if it contains the interval rows of every entity needed to reproduce the aligned segment stream of C within the piece’s time chunk. a) Pairwise compare (AO1): Under comparator ≺, the comparison result of two entities ha , hb is Cmp(ha , hb , x, ≺) = {[F, T ) | xa (t) ≺ xb (t) ∀t ∈ [F, T )}. (13)
Algorithm 1 Fan-out execution of query Q over window W
Serverless
Function
User Query DURATION_AVG(Price) BY Region FROM '2026-01-01'
TO '2026-02-01';
[Plan Stage] Coordinator Control Plane Final Output
Mapper 01 Mapper 02
Task
Queue
DURATION_AVG_Price: $4.17
Mapper
Stage Mapper N
Object Storage Job Partition Carrier Result
Reducer 01 Reducer 02
Reducer K
Commit
Registry
Reducer
Stage
Fig. 4: Vivace implementation overview.
b) Count-better-than (AO2): For a reference entity hr and candidates {hj }, the number of candidates better than the reference at time t is CB(t) = |{j | xj (t) ≺ xr (t)}|.
(14)
c) Winner and top-k (AO3): In each aligned segment, the active values within the cohort are ordered by a deterministic comparator and ranks 1, . . . , k are output. The winner timeline is the case k = 1. 3) Composition: Operators compose within and across families. For example, a predicate window or a boolean result feeds a count timeline, and a threshold is then applied. Thresholds and ranking are final computations applied once after all mapper results gather at the reducer. A composition that restricts one window to the key set identified by another predicate is handled by the key-domain finalizer, which applies the restriction once after both windows are complete. V. S ERVERLESS E XECUTION AND C ORRECTNESS In serverless fan-out execution, each mapper evaluates the segment stream of one range of the query window and emits partial results as Carriers, which the reducer combines into the final result. Matching the single-process result requires input completeness (R1) and operator-correct merge (R2). We call this equality exactness and prove that it holds. Vivace executes a query in the three stages of Algorithm 1 (Fig. 4) and is available as open source.2 For each query Q, the plan fixes, by operator family, the segment evaluator mQ , the merge rule MQ , the finalize map finQ , and the canonicalizer canonQ . Carriers are written to object storage and completions to the commit registry. The reducer starts only after every mapper task has committed. Commits are idempotent, so a re-executed mapper’s result is reflected only once. A. Query Planning and Mapper Execution a) Plan validation: The planner converts a logical request into the tasks of Algorithm 1, but first validates the execution conditions required by the merge laws of Table III. It rejects as non-executable: operators outside the supported 2 https://github.com/ddps-lab/vivace
Input: query Q over window W; ICP partition files Πj per time chunk Pj Output: canonicalized result of Q 1: for each time chunk Pj overlapping W do ▷ Plan stage 2: divide Pj into mapper pieces (j, s), s = 1, . . . , qj 3: register one mapper task per piece in the task queue 4: end for 5: for all tasks (j, s) in parallel do ▷ Mapper stage 6: read mapper input Xj,s from partition file Πj ; clip to Pj ∩W 7: build the segment stream Sj,s j,s 8: write Carrier CQ ← mQ (Sj,s ); commit task (j, s) 9: end for 10: wait until every task has committed ▷ completion barrier j,s 11: C̄Q ← MQ ({CQ }) ▷ Reducer stage: merge law 12: return canonQ (finQ (C̄Q )) ▷ finalize once
scope, inputs without full-state payloads, plans missing the completion barrier, and ranked queries without a fixed candidate shard placement or a deterministic tie-breaking rule. b) Bounded mapper pieces: When one chunk is large relative to the mapper memory, shrinking the chunk width would inflate storage through boundary clipping, so the width is kept and the chunk’s primary keys are divided by hash into shards. For same-base queries, the mapper input Xj,s of Algorithm 1 is the rows of its chunk whose key hashes to s. Same-base operators are independent per key, so the closed segment partition is preserved as long as the shards are disjoint and cover all keys. Aligned-cohort queries divide the query’s candidate set into disjoint shards instead of hash shards. Count-better-than replicates the reference history into each shard and sums the partial counts, and winner/top-k has the reducer re-rank the per-shard top-k to restore the global ranks. Without a separate physical layout, an aligned mapper reads only its own cohort keys from the same hash-sharded partition files, satisfying cohort-closed correctness without gathering the entire cohort into one mapper. The shard count qj is the smallest value for which each shard’s estimated compressed bytes fit within the calibrated ceiling Bf it , and the estimate comes from a per-PK byte histogram, reflecting key skew. Bf it is the largest compressed piece size that a mapper completes without Out of Memory (OOM). Since the mapper decompresses and processes its piece in memory, Bf it is far smaller than the memory capacity. c) Carriers: The mapper emits its partial results as Carriers, intermediate results whose output schema, merge method, finalization point, and canonicalization method are fixed by the plan. The reducer reads only Carriers, never mapper internal state, and applies the merge rule the plan records for each Carrier type. Table II summarizes the five Carrier types the runtime uses. B. Merge Laws The reducer combines the mappers’ Carriers to restore the original interval sets or the full count timeline. A merge must not start from an incomplete Carrier set, and the completion barrier of Algorithm 1 guarantees this.
TABLE II: Carrier types used by the runtime. Main users are the operator families defined in §IV-C. Carrier
Shape
W interval window (K, P F, T, [payload]) P D duration partial (G, i xi ∆i , i ∆i , n, mini xi , maxi xi ) C∆ count delta (G, Time, δ) Cstep step timeline (G, F, T, count) A aligned timeline boolean/additive/ranked aligned intervals
Invariant
Main users
key/time sorted; non-overlapping per key additive partial by group deltas collapsed by group/time chunk-clipped or globally complete count function coalesced output timeline
SO1, SO3; threshold windows SO2 SO4 endpoint merge SO4 full timeline; threshold input AO1–AO3
Definition 5 (Complete carrier): When the set of mapper pieces {(j, s)} of query Q forms the closed segment partition of §IV-A covering the entire query window, the carrier combined over it is called complete.
re-expresses as the deltas +c@F and −c@T . Summing the deltas of all mappers by group and time gives X ∆g (t) = ∆j,s (16) g (t), j,s
j,s C̄Q = MQ {CQ }
(15)
Table III summarizes how each Carrier is combined and which conditions are required. All rules presuppose a closed segment partition, a complete carrier set before finalization, a plan-fixed deterministic finalizer, and canonical output comparison, so the table lists only the rule-specific conditions. A superscript (j, s) marks one mapper piece’s carrier, a bar marks the combined carrier, and canon is the canonical coalescing of §V-C. a) Interval union and duration partial (L1, L2): L1 and L2 are immediate over a closed segment partition. For L1, each mapper’s keep/drop result covers disjoint time pieces, so union followed by coalescing restores the single-process result. Aligned boolean compare applies the same structure over the aligned Carrier A. For L2, the weighted sum, duration, and count are additive and min/max are associative, so combining mapper partials yields the global partial, and only the ratio is computed once after merging. b) Count timeline and threshold barrier (L3, L4): The SO4 count timeline (§IV-C) tracks the number of entities satisfying the predicate over time, and applies a threshold c∗ on top of it. Unlike L1 and L2, this merge is not immediate. For example, if two mappers counting one time point over key shards obtain 40 and 60, the sum is 100. Yet if the threshold c∗ = 80 is applied per mapper first, neither passes and the time point drops out of the result. The threshold must therefore be applied after all mapper counts are summed. The following proposition shows that this structure is exact. Proposition 1 (Count timeline merge and threshold barrier): SO4 is exact if the endpoint deltas of all mappers are summed by group and time, the full step timeline is built by cumulative summation, and the threshold is then applied. Proof: Let the local count Ngj,s (t) be the value mapper piece (j, s) obtains by evaluating Eq. (12) over its local segment stream. By Definition 2, the local stream of each piece equals the restriction of the global stream to its time chunk Pj and key shard s. Since P the shards are disjoint and their union covers the full key set, s Ngj,s (t) = Ng (t) for every t ∈ Pj , and the L3 endpoint addition performs this summation. A mapper emits its local count as C∆ endpoint deltas, or as chunk-clipped step segments (g, [F, T ), c) that the reducer
and cumulative summation in time order restores the full count step timeline. The threshold is the final computation evaluated over the full count timeline. c) Aligned count merge (L5): L5 applies the count timeline merge to the candidate shards of an aligned cohort. Corollary 1 (Aligned count merge): Count-better-than (AO2) is expressed as the count payload of the aligned Carrier A, and merging by the same endpoint-addition scheme is exact under a fixed cohort, disjoint candidate shards, and a replicated reference history. Proof: Count-better-than is an aligned count timeline without a group key. If the reference history accompanies every candidate shard and the shards are disjoint, the cumulative sum of the endpoint-addition merge equals the aligned count of a single process over the same cohort. d) Ranked aligned merge (L6): In aligned winner/topk, each candidate belongs to exactly one shard. Within one aligned segment, an entity in the global top-k is also in its own shard’s top-k, because if its shard held k or more better candidates, its global rank would also fall outside k. Re-sorting the per-shard top-k Carriers with the same comparator and tiebreaking key therefore yields the global ranked result. e) Key-domain finalizer (L7): The key-domain finalizer restricts a same-base interval window result W to the key set defined by a separate predicate ψ. Letting Eψ = πK (SO1 (I, ψ)) be the set of keys satisfying ψ, Gate(W, ψ) = W ⋉K Eψ = {r ∈ W | r.K ∈ Eψ }.
(17)
The mapper emits both W and Wψ = SO1 (I, ψ) as interval window carriers, and the reducer completes both by L1 and applies the semi-restriction W ⋉K πK (Wψ ) once. This finalizer is exact over complete carriers. Proposition 2 (Key-domain finalizer exactness): If the interval window carriers W and Wψ are each completed by L1 over a closed segment partition, and W mono and Wψmono denote the two results a single process computes from the same input, then W ⋉K πK (Wψ ), applied after all pieces have arrived, equals W mono ⋉K πK (Wψmono ) in canonical form. Proof: Let MW denote the L1 merge of interval window carriers. Then MW ({W j,s }) = W mono and MW ({Wψj,s }) = Wψmono . Key projection preserves union, so over a closed parS tition j,s πK (Wψj,s ) = πK (Wψmono ). Since Eψ is computed
TABLE III: Merge rules and required conditions. Rule
Carrier
Merge step
L1 interval union
W , boolean A
L2 additive duration partial
D
L3 count delta endpoint addition
C∆ /Cstep
L4 threshold after full count
Cstep → W
L5 aligned additive count merge
additive A
L6 ranked aligned merge
ranked A
L7 key-domain finalizer
tuple (W, Wψ )
W̄ = canon j,s ; same-base boolean uses L1 after per-row evaluation L D̄g = j,s Dgj,s with ⊕ componentwise (+, +, +, min, max); ratio once at finalize P P N̄g (t) = τ ≤t j,s ∆j,s g (τ ); canonical coalesce W̄ = canon {(g, [F, T )) | N̄g (t) > c∗ ∀t ∈ [F, T )} P CB(t) = j,s CBj,s (t) by endpoint addition; canonical coalesce collect shard top-k candidates; re-align; recompute global top-k merge both by L1; canon W̄ ⋉K πK (W̄ψ )
Rule-specific condition U
W j,s
from the complete Wψ , the membership evidence of a key may come from any time chunk or shard. The semi-restriction is therefore applied once after both carriers are complete. The semi-join keeps or drops all intervals of a key K as a whole and introduces no new time boundaries, so it commutes with canon. We thus obtain canon(W mono ⋉K πK (Wψmono )). f) Finalization: After the merge, the reducer applies the query’s final computation once. Definition 6 (Finalizer): Each query Q has a finalize map finQ , determined by its operator family, that sends a complete carrier or carrier tuple to the final result. finQ is a deterministic function of the complete carrier state alone, such as the pergroup ratio for SO2, the threshold for SO4, the ranking selection for winner/top-k, and the key-domain semi-restriction. When finQ is the identity, the merged carrier is promoted to the result manifest immediately. C. Exactness Theorem We now prove that the execution of Algorithm 1 produces the same result as a single process. a) Canonical equality: Two semantically identical results may divide their intervals differently. A fan-out execution may split one interval into two rows at a chunk boundary, whereas a single process emits the same range as one maximal interval. Row-by-row comparison therefore requires first arranging both results into the same canonical form. Definition 7 (Canonical output form): For results carrying intervals, canonQ sorts the rows by their output identifier and time, then merges adjacent rows with Ti = Fi+1 that match on the comparison criterion into maximal intervals. The criterion differs by output family. A general interval window compares the key and V . A result that discards V , such as SO3-U, compares only the key. A count timeline compares the group and the count. An aligned timeline compares the aligned result, and a ranked timeline compares the rank together with the selected entity or value. With the comparison criteria fixed, the maximal interval decomposition is unique, so canonQ is idempotent and un-
same-base predicates evaluate one full-state row; aligned boolean input is cohort-closed complete duration partials before final ratio complete clipped endpoint coverage per group complete count timeline before threshold fixed cohort; disjoint candidate shards; replicated reference history complete disjoint candidate shards; total order including tie key both carriers complete; same base key domain
affected by input order or chunk fragmentation. Result equivalence is judged by canonQ (Resultfanout ) = canonQ (Resultmono ).
(18)
For floating-point outputs such as duration-weighted aggregates, the group set, total duration, min, and max are compared exactly, and the TWA within a fixed tolerance. The following theorem formalizes this equivalence. Theorem 1 (Closed-partition decomposition exactness): Suppose each row holds the full state of its key, each mapper receives every interval row that determines the active state within its chunk, and for aligned queries the mapper inputs satisfy the cohort-closed condition of §IV-C. Suppose further that the operator family of query Q satisfies the merge rules and execution conditions of Table III. Then the fan-out result, obtained by merging the mappers’ local evaluation results and applying the finalize map finQ and the canonicalizer canonQ , equals the canonQ of the single-process result. Proof: A mapper piece is a time chunk, optionally paired with a key shard. By Definition 2, each piece’s local segment stream Sj,s equals the restriction of the global segment stream to that piece, so the clipped global stream is the disjoint union ] S= Sj,s . (19) j,s
In the aligned families, cohort-closed inputs supply each mapper the needed entity histories, so the same decomposition holds over aligned segments. j,s Let each mapper output be CQ = mQ (Sj,s ). Over a closed j,s segment partition, MQ ({CQ }) is the complete carrier C̄Q of Definition 5, and under the conditions of Table III it equals the single process’s intermediate result before finalization. Specifically, L1 covers SO1/SO3 and pairwise compare (AO1), L2 addresses SO2; Proposition 1 targets SO4; Corollary 1 handles count-better-than (AO2); L6 covers winner/top-k (AO3); and L7 is paired with Proposition 2. Since finQ depends only on the complete carrier or carrier tuple, applying it and then canonQ to both sides yields the same result. canonQ finQ (C̄Q ) = canonQ (Q(H, W)) (20)
VI. E VALUATION We empirically evaluate the Vivace implementation to address the following research questions. RQ1: Exactness. Does the fan-out execution result exactly match the result computed by a single process? RQ2: Layout efficiency. Does the ICP layout remove the mapper input preparation cost at only a small storage cost? RQ3: Layout portability. Can the layout be fitted on datasets with different interval characteristics without recalibrating mapper memory? RQ4: End-to-end efficiency. Does Vivace execute at lower monetary cost and latency than a SQL engine baseline? RQ5: Operator generality. Do the same operator families produce exact results on a dataset with a different schema? A. Experimental Setup a) Environment: All experiments, including the baseline engines and the S3 buckets for source relations and ICP layouts, run in AWS us-west-2. Vivace executes on Lambda with 5 GB mapper functions, and comparisons within a figure use the same tier. Carriers are exchanged through S3, with SQS as the task queue and DynamoDB as the commit registry. b) Dataset: The primary dataset is the AWS spot market history of SpotLake [14], a public dataset that has recorded the price, savings ratio, interruption frequency, and Spot Placement Score of spot instances for several years under the composite key of region × availability zone (AZ) × instance type. A new row at every value change forms one [From, To) interval, making the dataset an interval history. Analyses [27]–[30] performed over this dataset, such as price-condition interval search, per-region duration-weighted averages, and instance type comparison, correspond directly to Vivace’s operator families, so the operator results are the final analyses researchers want, without separate dimension joins. The dataset is also read intermittently, rarely in ordinary operation with bursts at failure investigations or research experiments, the access pattern where the serverless cost advantage is most pronounced. Its public availability facilitates reproduction. Evaluation centers on the 12-month window from March 2025 to March 2026 (Table IV). c) Additional datasets: The evaluation adds two datasets whose interval characteristics differ from SpotLake. CAISO LMP [15] is a public time series recording the hourly locational marginal price of the California ISO day-ahead market per pricing node (12-month evaluation window). Values refresh hourly, so interval lifetimes are short, while the key count and per-chunk data volume are similar to SpotLake. Wikipedia revision history [16] records the revision size of English Wikipedia per page (3-month evaluation window). Most pages change little, so interval lifetimes are very long and the key count reaches tens of millions. The three datasets differ widely in mean interval lifetime and per-chunk data volume (Table IV), and we use this spread to verify that the layout sizing applies regardless of dataset characteristics. MobilityDB-TPCDS, an SCD Type 2 benchmark, is used separately to assess operator generality.
TABLE IV: Evaluation datasets and interval characteristics. Dataset
Primary key
#keys
Avg lifetime
SpotLake AWS CAISO LMP Wikipedia revision
region×AZ×type pricing node page
41,356 67,892 41.5 M
2.7 h 1.3 h ∼67 d
d) Time-chunk and mapper configuration: The source Parquet files are split by month, matching SpotLake’s monthly ingestion cycle, and these monthly boundaries serve directly as time-chunk boundaries. The monthly ICP partition files average 56.2 MiB with a maximum of 61.6 MiB, and in the default configuration each mapper reads one monthly chunk. e) Baselines and execution paths: The final end-to-end comparison focuses on two paths. Athena SCD2 directly reads the natural valid-from/to source relation that users keep in the object store, and Vivace ICP reads the interval-clipped partition files, Vivace’s intended layout. Both paths’ files are generated from the same source history and validated with the same query semantics and single-process oracle. On SpotLake, Athena ICP and Vivace SCD2 are measured as an ablation to isolate the layout effect from the runtime effect. Latency is recorded as the end-to-end time, the sum of the submit round trip and the terminal-status wait time. Vivace cost sums function execution, object store I/O, and queue and commit registry requests, and Athena cost applies 5 USD/TiB to scanned bytes with a 10 MiB minimum, both computed from runtime billable units and official unit prices. Log storage, intermediate objects, and post-execution artifact reads are excluded and recorded separately. f) Query suite: Table V summarizes the query suite, with the concrete analysis questions and predicates on SpotLake, the primary dataset. The ten queries each use one core operator of §IV-C, Q1–Q6 covering the same-base operators SO1– SO4 and Q7–Q10 the aligned-cohort operators AO1–AO3. On CAISO and Wikipedia, the same ten queries are retained, with the predicates and group keys adapted to each domain, such as LMP/MCC or revision-size conditions. For each target window, every system-query combination discards one warm-up run and takes the median of five repeats, reporting the mean of these medians over the ten queries. On SpotLake, the suite additionally runs over 1-, 3-, 6-, and 12month windows to observe scaling with window length. B. Exactness Validation (RQ1) To address RQ1, we compare the Vivace fan-out result with the single-process reference result in the canonical form of §V-C for every operator family. The canonical-form criterion differs by operator family. Interval window results (SO1, SO3-I/U/D) are compared at the row level after coalescing. SO2 aggregates compare the weighted sum, duration, min, and max exactly, with only the TWA ratio allowed a 10−9 tolerance. SO4 count timelines are canonicalized by group and count, with the threshold applied over the complete timeline, and aligned cohort operators are compared after canonicalizing the aligned payload.
TABLE V: Evaluation query suite and analysis examples. Query Operator Analysis question
Predicate or composition
Q1 Q2
SO1 SO2
When is spot capacity cheap? What is each region’s price exposure over the window?
SO1(SpotPrice < 0.05). SO2(SpotPrice by Region).
Q3 Q4
SO3-I SO3-U
When is capacity both cheap and stable? When is capacity cheap or stable?
Q5 Q6 Q7 Q8 Q9 Q10
SO3-D SO4 AO1 AO2 AO3 AO3
When is capacity cheap but below the stability threshold? When does a region have enough cheap capacity? When is one AZ cheaper than another? How many candidates beat a reference AZ? Which candidate is cheapest at each time? Which candidates are the top-k cheapest over time?
Latency (s)
SCD2 source
Cheap-capacity intervals per entity. Region-level duration-weighted average price. SO3-I(SpotPrice < 0.05, SPS ≥ 3). Cheap-and-stable intervals. SO3-U(SpotPrice < 0.05, SPS ≥ 3). Intervals satisfying at least one operational condition. SO3-D(SpotPrice < 0.05, SPS ≥ 3). Cheap intervals that still carry stability risk. SO4(SpotPrice < 0.05, Region, count > 100). Regional market-depth intervals. AO1(a1.2xlarge, aps1-az3 ≺ aps1-az2). Intervals where the left AZ is cheaper. AO2(a1.2xlarge, min SpotPrice vs reference). Time-varying cheaper-candidate count. AO3(a1.2xlarge, min SpotPrice, k = 1). Cheapest-candidate timeline. AO3(a1.2xlarge, min SpotPrice, k = 3). Ranked cheapest-candidate timeline.
Vivace ICP
0.5 0.0
Result semantics
2025 2025 2025 2025 2025 2026 2026 03 05 07 09 11 01 03
One-month query window
Fig. 5: SCD2 vs. ICP input preparation cost.
The canonical forms matched for every query and window combination of Table V. The Athena baseline also produced the same results under the identical canonical-form criterion. In the time-chunk sweep, the remote final Parquet results of five chunk factors (×1/4, ×1/2, ×1, ×2, ×4) were read directly and compared with the monthly factor ×1 after per-carrier canonicalization. All measured queries matched. Notably, the raw output of SO1 varied from 12.12M to 12.26M rows across factors, yet after coalescing every factor agreed on the same 144,054 canonical intervals. These results confirm that exactness holds regardless of chunk division, and the subsequent performance comparisons rest on this premise. C. Layout Effectiveness (RQ2) For RQ2, the input preparation cost and storage amplification of the ICP layout are measured against the SCD2 source. a) Input preparation cost: Fig. 5 compares the mapper latency of SCD2 and ICP while fixing a one-month query window and shifting the target month later. As the target month moves later, the number of prior monthly files SCD2 must read together grows. The SO1 predicate window is the most basic operator and therefore exposes the mapper input preparation cost of the two input forms most directly. SCD2 must locate the rows overlapping the query window in source files stored by From month. Both layouts show similar latency at first, where each reads a single file, but as prior files accumulate, SCD2 latency grows in proportion while ICP remains nearly flat. At the last window, SCD2 is about 2.25× slower than ICP. b) Storage amplification: ICP clips boundary-crossing intervals into the files on both sides, so the row count and the total storage grow relative to the source relation. On the
12-month AWS dataset, the valid-from/to SCD2 source is 672.4 MiB and the monthly ICP layout is 674.8 MiB. ICP provides mapper-local input at +0.3% storage over the SCD2 source. The row count grows from boundary clipping, but the marginal storage difference is primarily attributed to Parquet’s columnar compression. The From and To columns of clipped rows in ICP concentrate on the same time-chunk boundaries, raising the compression efficiency of dictionary and run-length encoding. As a result, the storage growth from added rows is offset by the compression gain in the timestamp columns. These results confirm an asymmetry between the two layouts. ICP’s storage increase is a one-time fixed cost, whereas SCD2’s overlap lookup cost recurs at every query and grows in proportion to the history depth. D. Layout Portability (RQ3) The layout predetermines the per-mapper fan-out, and fitting each mapper’s input within its memory tier is Vivace’s responsibility, different from query-time SCD2 scans, where this burden falls on the user. For RQ3, we test whether a single sizing model fits all three datasets, whose change rates and volumes differ widely, onto the same 5 GB mapper tier. a) Calibrated mapper piece ceiling: The mapper piece ceiling Bf it is calibrated only once, on SpotLake AWS. Materializing layouts at several byte targets and executing without shards, we take the largest target at which the six supported same-base queries finish exactly on a 5 GB mapper without OOM or escalation to a larger memory tier. At larger targets the union/coalesce chunk exceeds the ceiling, but splitting the same chunk into two key shards brings it back within the ceiling. Aligned-cohort queries use cohort-closed placement, so Bf it is defined on the same-base class. The resulting Bf it = 64 MiB is applied to every dataset. b) Sizing outcomes: Sizing sets the chunk width at or above wsaf e to bound storage and then divides primary keys by hash until each mapper piece fits within Bf it . For SpotLake and CAISO, one chunk already fits within Bf it , so one mapper processes it without shards (q = 1). For Wikipedia, revisions span the entire measurement window, so wsaf e equals the whole window. The chunk width therefore cannot be reduced, and a single chunk reaches 989 MiB, about 15× Bf it . The model keeps this chunk as a single interval file clustered into primary-key buckets, and query-time logical sharding assigns
163 110
100
51
30
0 SpotLake CAISO
Vivace ICP
Cost (mUSD)
Latency (s)
Athena SCD2
75
50
76 31
Wiki
12
35
25 17
6
0 SpotLake CAISO
(a) Latency
Wiki
(b) Cost
Fig. 6: End-to-end latency and cost over the ten-query suite.
Mean latency (s)
Athena ICP Athena SCD2
20 16 12 8 4 0
0
Vivace ICP Vivace SCD2
1
2
3
Vivace ICP cold
4
Mean cost/query (milli-USD)
5
Fig. 7: SpotLake cost and latency across query windows each mapper only the bucket ranges its query needs, keeping the piece it reads within the memory tier. The six same-base queries ran over this query-time bucket sharding, and the four aligned-cohort queries over separate cohort-closed placement. All ten produced results identical to the single process on 5 GB mappers without OOM. c) Optimality: This sizing satisfies the mapper memory constraint while avoiding fragmentation, and minimizing latency or cost is left as a separate problem. These results validate that the once-calibrated model generalizes, fitting all three datasets to the same mapper tier without recalibration. E. End-to-End Cost and Latency (RQ4) To address RQ4, Vivace is compared with SQL engine baselines in end-to-end cost and latency. Fig. 6 presents the per-dataset comparison, where Athena reads the natural SCD2 source and Vivace reads the ICP layout. Vivace lowers the aggregate latency and cost of the ten queries on all three datasets. The gap is largest on SpotLake, where the history is deepest, at 5.44× in latency and 6.23× in cost. CAISO and Wikipedia follow at 2.17× and 2.44× in latency, with 30% and 83% lower cost. These gains incur almost no storage overhead, with a Vivace-to-Athena storage ratio of 0.91–1.03. a) SpotLake deep dive: On SpotLake we examine scaling by widening the query suite over 1-, 3-, 6-, and 12-month windows. Fig. 7 presents the per-query average cost in milliUSD (mUSD) on the x-axis and the latency on the y-axis for five execution paths, with each path’s leftmost point at the 1-month window. Paths closer to the origin execute at lower cost and latency. BigQuery, measured under the same SQL contract, is excluded because its logical-scan-bytes billing
makes the per-query cost far higher than Athena’s. Notably, Athena ICP exceeds Athena SCD2 in both latency and cost. Athena does not assign mappers per file, so ICP only adds scan volume without its partition-local benefit. Vivace ICP’s latency grows only from 2.10 s to 2.98 s as the window widens from 1 to 12 months. The mapper count grows with the window, but parallel execution keeps the latency growth sublinear. The curve stays closer to the origin than Athena SCD2 throughout. In contrast, Vivace SCD2’s overlap lookup of prior monthly files grows with window length, and at 12 months it is 63% slower and about 1.8× more expensive than ICP. Under forced cold starts, Vivace ICP reaches 7.77 s and 2.63 mUSD at 12 months, still 2.34× faster than Athena SCD2 at 53% of the cost. Since cold starts are the common condition under intermittent access, this advantage is of practical significance. b) Always-on baselines: We compare against two always-on baselines, each with a distinct advantage: ClickHouse [31] for fast columnar scans, and MobilityDB [32] for native interval semantics that simplify query writing. Both hold the 12-month SpotLake history on an r7i.xlarge (4 vCPU, 32 GiB) instance, the specification recommended by the official ClickHouse documentation. ClickHouse’s infrastructure cost is fixed at about 201 USD per month regardless of the query count. The break-even frequency at which its per-query cost equals Vivace ICP is about 250 queries per hour at the 12-month window and about 1,700 per hour at the 1-month window, and below those rates serverless is cheaper. MobilityDB’s native temporal types and aggregates such as twAvg simplify query writing, but execution is slower, with a 12-month 10-query average of 7.86 s, about 2.6× Vivace ICP (2.98 s). Against either advantage, Vivace delivers practical latency while keeping a pay-per-query cost that scales only with execution frequency. F. Operator Generality (RQ5) For RQ5, we evaluate operator families on an independent SCD Type 2 benchmark with an entirely different schema. a) MobilityDB benchmark: MobilityDB-TPCDS [33] is a public temporal warehouse workload that provides the historical dimension tables of the TPC-DS [34] benchmark in three implementations: SCD Type 2, temporal data warehouse, and MobilityDB temporal types. This evaluation uses its scd_item table (SF100). Each row is an SCD Type 2 record holding the [From, To) interval during which attributes of one item, such as brand, class, and price, persisted, a schema entirely different from SpotLake. The six temporal algebra queries of this benchmark (benchmark notation Q1–Q6, hereafter MQ1–MQ6) are all expressed as compositions of Vivace operator families, requiring no new operator (Table VI). Correctness was judged by an independent oracle built from the original scd_item without Vivace primitives. For all six queries, the fan-out results matched this oracle and the single-process reference in canonical form, and MQ1–MQ4 and MQ6 also matched native MobilityDB. MQ5 computes a temporal difference followed by a keydomain restriction. It finds the parts of a brand’s intervals
TABLE VI: MobilityDB-TPCDS MQ1–MQ6 as compositions of Vivace operators, each discharged by a merge law. Query Vivace operator composition MQ1 MQ2 MQ3 MQ4 MQ5 MQ6
predicate window (SO1) → coalesce projection → coalesce same-base boolean and (SO3-I) → coalesce same-base boolean or (SO3-U) → coalesce difference (SO3-D) + key-domain finalizer count timeline (SO4) → threshold
Carrier
Law
W W W W (W, Wψ ) Cstep
L1 L1 L1 L1 L7 L3, L4
where the price is at or below a threshold, restricted to items whose price ever exceeded it. With brand intervals B and threshold-exceeding intervals Pi per item, the core S computation is B \ i Pi plus an item-level existence condition. Implementing this difference directly with interval set operations is error-prone at two steps: collecting and subtracting the multiple Pi , and clipping the result back inside B. The benchmark’s three official SQL implementations indeed T diverge at S exactly these points. Q5_MobDB subtracts i Pi instead of i Pi , retaining intervals that should be removed whenever two or more Pi exist, and Q5_TDW and Q5_SCD do not clip the result to B, so their results extend outside it. These errors affect 19 of the 94 target items at SF100. In Vivace, owing to the full-state same-base intervals, this difference reduces to a single boolean over one interval. Evaluating “the brand condition holds and price ≤ threshold” on each interval suffices, and since the intervals are already clipped into closed segments, neither error point arises. The item-level existence condition is applied once by the keydomain semi-join (§V-B L7) after both windows are complete. As a result, against the same oracle, only Vivace was correct on all 94 items (94/94), while Q5_MobDB reached 93 and Q5_TDW and Q5_SCD reached 75. These results validate that Vivace’s operator families express temporal algebra over SCD Type 2 schemas in general, not over a specific dataset, without new primitives. VII. R ELATED W ORK a) Temporal databases and analytics: Sequenced semantics defines the meaning of a temporal query through the per-time-point interpretation of the relation, and coalescing arranges interval results with differing boundaries into a comparable canonical form [21], [22], [35]–[37]. Access methods for time-evolving data are surveyed in [38], and parallel temporal aggregation has been studied on sharednothing architectures [39]. Timeline Index [12], ParTime [13], and temporal ranking [40] accelerate temporal aggregation, joins, and aggregate top-k over query intervals efficiently, but all assume an in-memory engine. MobilityDB [32] extends PostgreSQL with native temporal types and operators, but requires an always-on database server. b) Interval histories and versioned tables: SCD Type 2 [1] stores entity versions with their start and end times, and TPC-DS [34] and MobilityDB-TPCDS [33] provide historical dimensions as benchmarks. Lakehouse features such as Iceberg time travel and Delta CDF likewise yield valid-from/to
TABLE VII: Comparison with prior systems. Always-on temporal covers Timeline Index, ParTime, and MobilityDB. Always-on Athena/ Lambada/ temporal ClickHouse BigLake Starling Ours Temporal operators on interval histories Queries data on object storage Pay-per-query execution Exact partitioned execution w/o state exchange (R1, R2)
✓
–
–
–
✓
– –
✓ –
✓ ✓
✓ ✓
✓ ✓
–
–
–
–
✓
rows from table versions and row-level changes [17], [18], [41], [42]. However, exact query-window analytics over these histories remains unaddressed. c) Object-store SQL and serverless analytics: Athena [10] and BigLake [11] query object storage with SQL, but users must hand-write the interval overlap and clipping logic. Columnar engines such as ClickHouse [31] also scan object storage directly but require an always-on cluster. Lambada [2], Starling [5], and Cackle [6] provide serverless fan-out execution but target general relational queries, lacking the temporal handling that interval histories require. d) Mergeable and incremental computation: MapReduce combiners, Spark RDDs, the Dataflow model, and incremental view maintenance [43]–[49] established the principle of combining local summaries or deltas later. Vivace applies this principle to temporal operators over intervals: associative aggregates such as duration and count merge their partials directly, while non-associative operations such as ranking record the comparator and shard placement in the plan to reproduce the exact result. Table VII contrasts Vivace with prior systems. VIII. C ONCLUSION AND F UTURE W ORK This paper presented Vivace, a system that executes temporal OLAP over interval histories across independent serverless functions. By cutting the source relation into a time-partitioned layout before queries, each function obtains its complete input from a single file, and the reducer merges the per-function Carriers by operator-specific rules. We proved as a theorem that under these two requirements the result is exactly that of single-process execution. Against a SQL baseline on three real datasets with different interval characteristics, this design removed the input preparation cost that grows with history depth, reducing latency by up to 82% and cost by up to 84%. Vivace currently covers queries over a single interval relation or its join with time-invariant dimensional attributes. Temporal joins across relations, dynamically constructed cohorts, and sequential or sliding-window patterns lie outside this scope, and the planner rejects such requests. Future work includes defining a multi-relation co-partitioned closure to support restricted temporal joins, introducing boundary-state carriers to cover some sliding-window patterns, and selecting the chunk size and layout automatically for a given workload.
ACKNOWLEDGMENT We used Anthropic’s Claude Code and OpenAI’s Codex to assist with the system implementation of this work. All AIgenerated code was reviewed and verified by the authors. R EFERENCES [1] R. Kimball and M. Ross, The Data Warehouse Toolkit: The Definitive Guide to Dimensional Modeling, 3rd ed. Hoboken, NJ, USA: Wiley, 2013. [Online]. Available: https://www.kimballgroup.com/data-warehou se-business-intelligence-resources/books/data-warehouse-dw-toolkit/ [2] I. Müller, R. Marroquı́n, and G. Alonso, “Lambada: Interactive data analytics on cold data using serverless cloud infrastructure,” in Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. New York, NY, USA: Association for Computing Machinery, 2020, pp. 115–130. [3] T. Bodner, D. Ritter, M. Boissier, and T. Rabl, “Skyrise: Exploiting serverless cloud infrastructure for elastic data processing,” DatenbankSpektrum, vol. 25, no. 1, pp. 29–38, 2025. [Online]. Available: https://doi.org/10.1007/s13222-025-00496-7 [4] H. Bian, T. Sha, and A. Ailamaki, “Using cloud functions as accelerator for elastic data analytics,” Proc. ACM Manag. Data, vol. 1, no. 2, Jun. 2023. [Online]. Available: https://doi.org/10.1145/3589306 [5] M. Perron, R. Castro Fernandez, D. J. DeWitt, and S. Madden, “Starling: A scalable query engine on cloud functions,” in Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. New York, NY, USA: Association for Computing Machinery, 2020, pp. 131– 141. [6] M. Perron, R. Castro Fernandez, D. DeWitt, M. Cafarella, and S. Madden, “Cackle: Analytical workload cost and performance stability with elastic pools,” Proceedings of the ACM on Management of Data, vol. 1, no. 4, pp. 233:1–233:25, 2023. [7] E. Jonas, Q. Pu, S. Venkataraman, I. Stoica, and B. Recht, “Occupy the cloud: Distributed computing for the 99%,” in Proceedings of the 2017 Symposium on Cloud Computing, ser. SoCC ’17. New York, NY, USA: ACM, 2017, pp. 445–451. [Online]. Available: http://doi.acm.org/10.1145/3127479.3128601 [8] C. Lee, Z. Zhu, T. Yang, Y. Huo, Y. Su, P. He, and M. R. Lyu, “Spes: Towards optimizing performance-resource trade-off for serverless functions,” in 2024 IEEE 40th International Conference on Data Engineering (ICDE). Los Alamitos, CA, USA: IEEE Computer Society, May 2024, pp. 165–178. [Online]. Available: https://doi.ieeecomputersociety.org/10.1109/ICDE60146.2024.00020 [9] T. Zhang, D. Xie, F. Li, and R. Stutsman, “Narrowing the gap between serverless and its state with storage functions,” in Proceedings of the ACM Symposium on Cloud Computing, ser. SoCC ’19. New York, NY, USA: Association for Computing Machinery, 2019, p. 1–12. [Online]. Available: https://doi.org/10.1145/3357223.3362723 [10] Amazon Web Services, “Amazon Athena Documentation,” https://docs .aws.amazon.com/athena/, accessed: 2026-05-19. [11] J. Levandoski, G. Casto, M. Deng, R. Desai, P. Edara, T. Hottelier, A. Hormati, A. Johnson, J. Johnson, D. Kurzyniec, S. McVeety, P. Ramanathan, G. Saxena, V. Shanmugam, and Y. Volobuev, “BigLake: BigQuery’s evolution toward a multi-cloud lakehouse,” in Companion of the 2024 International Conference on Management of Data, 2024, pp. 334–346. [12] M. Kaufmann, A. A. Manjili, P. Vagenas, P. M. Fischer, D. Kossmann, F. Färber, and N. May, “Timeline index: A unified data structure for processing queries on temporal data in SAP HANA,” in Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, 2013, pp. 1173–1184. [13] M. Pilman, M. Kaufmann, F. Köhl, D. Kossmann, and D. Profeta, “ParTime: Parallel temporal aggregation,” in Proceedings of the 2016 ACM SIGMOD International Conference on Management of Data, 2016, pp. 999–1010. [14] S. Lee, J. Hwang, and K. Lee, “Spotlake: Diverse spot instance dataset archive service,” in 2022 IEEE International Symposium on Workload Characterization (IISWC). Los Alamitos, CA, USA: IEEE Computer Society, nov 2022, pp. 242–255. [Online]. Available: https://doi.ieeecomputersociety.org/10.1109/IISWC55918.2022.00029 [15] California ISO, “Open Access Same-time Information System (OASIS),” https://oasis.caiso.com/mrioasis/logon.do, 2026, accessed 2026-06-10.
[16] Wikimedia Foundation, “Analytics Datasets: MediaWiki History,” https: //dumps.wikimedia.org/other/mediawiki history/readme.html, 2026, english Wikipedia snapshot: https://dumps.wikimedia.org/other/mediaw iki history/2026-05/enwiki/. Accessed 2026-06-10. [17] Apache Iceberg, “Apache Iceberg Spark Queries: Time Travel Queries,” https://iceberg.apache.org/docs/1.10.0/spark-queries/, Apache Iceberg 1.10.0 documentation. Accessed: 2026-05-19. [18] Delta Lake, “Change Data Feed,” https://docs.delta.io/delta-change-dat a-feed/, Delta Lake documentation. Accessed: 2026-05-19. [19] T. B. Pedersen and C. S. Jensen, “Multidimensional database technology,” IEEE Computer, vol. 34, no. 12, pp. 40–46, 2001. [20] P. Vassiliadis and T. Sellis, “A survey of logical models for OLAP databases,” ACM SIGMOD Record, vol. 28, no. 4, pp. 64–69, 1999. [21] C. S. Jensen, M. D. Soo, and R. T. Snodgrass, “Unification of temporal data models,” in Proceedings of the Ninth International Conference on Data Engineering. IEEE Computer Society Press, 1993, pp. 262–271. [22] A. Dignös, M. H. Böhlen, J. Gamper, and C. S. Jensen, “Extending the kernel of a relational DBMS with comprehensive support for sequenced temporal queries,” ACM Transactions on Database Systems, vol. 41, no. 4, 2016. [23] A. Dignös, M. H. Böhlen, and J. Gamper, “Overlap interval partition join,” in Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, 2014, pp. 1459–1470. [24] E. Soroush, M. Balazinska, and D. Wang, “Arraystore: a storage manager for complex parallel array processing,” in Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, ser. SIGMOD ’11. New York, NY, USA: Association for Computing Machinery, 2011, p. 253–264. [Online]. Available: https://doi.org/10.1145/1989323.1989351 [25] B. Moon, I. Lopez, and V. Immanuel, “Scalable algorithms for large temporal aggregation,” in Proceedings of 16th International Conference on Data Engineering (Cat. No.00CB37073), 2000, pp. 145–154. [26] J. Martinez and G. Raschia, “Revisiting optimal window aggregation in data streams: The prefix-sum approach,” in Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, ser. CIKM ’24. New York, NY, USA: Association for Computing Machinery, 2024, p. 1660–1669. [Online]. Available: https://doi.org/10.1145/3627673.3679573 [27] K. Kim, S. Park, J. Hwang, H. Lee, S. Kang, and K. Lee, “Public spot instance dataset archive service,” in Companion Proceedings of the ACM Web Conference 2023, ser. WWW ’23 Companion. New York, NY, USA: Association for Computing Machinery, 2023, p. 69–72. [Online]. Available: https://doi.org/10.1145/3543873.3587314 [28] S. Cheon, K. Kim, K. Kim, M. Song, and K. Lee, “Multi-node spot instances availability score collection system,” in Proceedings of the 34th International Symposium on High-Performance Parallel and Distributed Computing, ser. HPDC ’25. New York, NY, USA: Association for Computing Machinery, 2025, pp. 33:1–33:2. [29] T. Kim, K. Kim, K. Kim, H. Kim, S. Jeong, M. Song, and K. Lee, “Spotvista: Availability-aware recommendation system for reliable and cost-efficient multi-node spot instances,” 2026. [Online]. Available: https://arxiv.org/abs/2604.24548 [30] T. Kim, K. Kim, E. Molina-Giménez, P. Garcı́a-López, and K. Lee, “Kubepacs: Kubernetes cluster using performant, highly available, and cost efficient spot instances,” 2026. [Online]. Available: https://arxiv.org/abs/2604.24027 [31] R. Schulze, T. Schreiber, I. Yatsishin, R. Dahimene, and A. Milovidov, “ClickHouse - lightning fast analytics for everyone,” Proceedings of the VLDB Endowment, vol. 17, no. 12, pp. 3731–3744, 2024. [32] E. Zimányi, M. Sakr, and A. Lesuisse, “MobilityDB: A mobility database based on PostgreSQL and PostGIS,” ACM Transactions on Database Systems, vol. 45, no. 4, pp. 19:1–19:42, 2020. [33] W. Ahmed, L. Gómez, A. Vaisman, and E. Zimányi, “Reconciling tuple and attribute timestamping for temporal data warehouses,” The VLDB Journal, vol. 34, 2025. [34] Transaction Processing Performance Council, TPC Benchmark DS: Standard Specification, Version 4.0.0, https://www.tpc.org/TPC Docum ents Current Versions/pdf/TPC-DS v4.0.0.pdf, Transaction Processing Performance Council, 2024, accessed: 2026-05-20. [35] K. Kulkarni and J.-E. Michels, “Temporal features in SQL:2011,” ACM SIGMOD Record, vol. 41, no. 3, pp. 34–43, 2012. [Online]. Available: https://sigmodrecord.org/2012/09/30/temporal-features-in-sql2011/
[36] A. Dignös, M. H. Böhlen, and J. Gamper, “Temporal alignment,” in Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, 2012, pp. 433–444. [37] A. Dignös, B. Glavic, X. Niu, M. H. Böhlen, and J. Gamper, “Snapshot semantics for temporal multiset relations,” Proceedings of the VLDB Endowment, vol. 12, no. 6, pp. 639–652, 2019. [38] B. Salzberg and V. J. Tsotras, “Comparison of access methods for timeevolving data,” ACM Computing Surveys, vol. 31, no. 2, pp. 158–221, 1999. [39] J. Gendrano, B. Huang, J. Rodrigue, B. Moon, and R. Snodgrass, “Parallel algorithms for computing temporal aggregates,” in Proceedings 15th International Conference on Data Engineering (Cat. No.99CB36337), 1999, pp. 418–427. [40] J. Jestes, J. M. Phillips, F. Li, and M. Tang, “Ranking large temporal data,” Proceedings of the VLDB Endowment, vol. 5, no. 11, pp. 1412– 1423, 2012. [41] T. Akidau, P. Barbier, I. Cseri, F. Hueske, T. Jones, S. Lionheart, D. Mills, D. Pauliukevich, L. Probst, N. Semmler, D. Sotolongo, and B. Zhang, “What’s the difference? incremental processing with change queries in Snowflake,” Proceedings of the ACM on Management of Data, vol. 1, no. 2, 2023. [42] A. Chavan and A. Deshpande, “DEX: Query execution in a deltabased storage system,” in Proceedings of the 2017 ACM International Conference on Management of Data, 2017, pp. 171–186. [43] J. Dean and S. Ghemawat, “Mapreduce: Simplified data processing on large clusters,” in Proceedings of the 6th Conference on Symposium on Operating Systems Design & Implementation - Volume 6, ser. OSDI’04. Berkeley, CA, USA: USENIX Association, 2004, pp. 10–10. [Online]. Available: http://dl.acm.org/citation.cfm?id=1251254.1251264 [44] M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauley, M. J. Franklin, S. Shenker, and I. Stoica, “Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing,” in 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI 12). San Jose, CA, USA: USENIX Association, 2012, pp. 15–28. [Online]. Available: https://www.usenix.org/conference/nsdi12/t echnical-sessions/presentation/zaharia [45] T. Akidau, R. Bradshaw, C. Chambers, S. Chernyak, R. J. FernándezMoctezuma, R. Lax, S. McVeety, D. Mills, F. Perry, E. Schmidt, and S. Whittle, “The dataflow model: A practical approach to balancing correctness, latency, and cost in massive-scale, unbounded, out-of-order data processing,” Proceedings of the VLDB Endowment, vol. 8, no. 12, pp. 1792–1803, 2015. [46] P. K. Agarwal, G. Cormode, Z. Huang, J. M. Phillips, Z. Wei, and K. Yi, “Mergeable summaries,” in Proceedings of the 31st ACM SIGMODSIGACT-SIGAI Symposium on Principles of Database Systems, 2012, pp. 23–34. [47] C. Koch, Y. Ahmad, O. Kennedy, M. Nikolic, A. Nötzli, D. Lupei, and A. Shaikhha, “DBToaster: Higher-order delta processing for dynamic, frequently fresh views,” The VLDB Journal, vol. 23, no. 2, pp. 253–278, 2014. [48] M. Budiu, T. Chajed, F. McSherry, L. Ryzhyk, and V. Tannen, “DBSP: Automatic incremental view maintenance for rich query languages,” Proceedings of the VLDB Endowment, vol. 16, no. 7, pp. 1601–1614, 2023. [49] A. Kara, M. Nikolic, D. Olteanu, and H. Zhang, “F-IVM: Analytics over relational databases under updates,” The VLDB Journal, vol. 33, pp. 903–929, 2024.