Chain: Operator Scheduling for Memory Minimization in Data Stream Systems

Summary: Introduces Chain, an adaptive, load-aware operator scheduler that minimizes memory under bursty streaming loads. Near-optimal for single-stream queries (selections, projections, joins) and effective for sliding-window workloads, with experiments. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: ha3e17c1f5a3e0468
Venue: SIGMOD
Year: 2003
Pagerank: 0.00012308922
Overall Rank: 1,047 | 92.97%
DOI: 10.1145/872757.872789

Incoming Non-self Citations Over Time

Authors

1. Brian Babcock (Stanford University)
2. Shivnath Babu (Stanford University)
3. Mayur Datar (Stanford University)
4. Rajeev Motwani (Stanford University)

BibTeX Citation

@inproceedings{babcock_sigmod03,
        title = {{Chain: Operator Scheduling for Memory Minimization in Data Stream Systems}},
        author = {Babcock, Brian and Babu, Shivnath and Datar, Mayur and Motwani, Rajeev},
        series = {{SIGMOD} '03},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/872757.872789},
        url = {https://dl.acm.org/doi/10.1145/872757.872789},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 22 of 22 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
127	The Design of the Borealis Stream Processing Engine	2005	CIDR	0.00030427614
429	Flexible Time Management in Data Stream Systems	2004	PODS	0.00018439857
1,278	Streaming Pattern Discovery in Multiple Time-Series	2005	VLDB	0.00011231952
1,750	Towards a Streaming SQL Standard	2008	VLDB	9.7311887e-05
1,828	Fault-Tolerance in the Borealis Distributed Stream Processing System	2005	SIGMOD	9.5516021e-05
2,500	Operator Scheduling in a Data Stream Manager	2003	VLDB	8.3809217e-05
2,558	Tuple Routing Strategies for Distributed Eddies	2003	VLDB	8.3007355e-05
3,371	Dynamic Plan Migration for Continuous Queries Over Data Streams	2004	SIGMOD	7.3693585e-05
3,583	STREAM: The Stanford Stream Data Manager (Demonstration Description)	2003	SIGMOD	7.1908304e-05
4,693	Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams	2004	SIGMOD	6.4662079e-05
5,103	Run-Time Operator State Spilling for Memory Intensive Long-Running Queries	2006	SIGMOD	6.2724506e-05
6,160	Load Shedding in Stream Databases: A Control-Based Approach	2006	VLDB	5.8652029e-05
6,188	Finding Global Icebergs over Distributed Data Sets	2006	PODS	5.8571256e-05
8,131	Thrifty Query Execution via Incrementability	2020	SIGMOD	5.3936608e-05
8,268	CAPE: Continuous Query Engine with Heterogeneous-Grained Adaptivity	2004	VLDB	5.3648996e-05
8,843	Efficient Scheduling of Heterogeneous Continuous Queries	2006	VLDB	5.265429e-05
9,168	Experimental Evaluation of Optimizing Memory Consumption in SAP HANA Using PEOopt	2025	SIGMOD	5.214147e-05
9,784	Memory Efficient Scheduling of Query Pipeline Execution	2022	CIDR	5.1285917e-05
10,566	Enjima: A Resource-Adaptive Stream Processing System	2026	SIGMOD	4.9793485e-05
11,972	Klink: Progress-Aware Scheduling for Streaming Data Systems	2021	SIGMOD	4.9793485e-05
12,401	CE-Storm: Confidential Elastic Processing of Data Streams	2015	SIGMOD	4.9793485e-05
12,543	Utility-Maximizing Event Stream Suppression	2013	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
26	Models and Issues in Data Stream Systems	2002	PODS	0.00052121228
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00040860054
149	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00028981723
152	Query Processing, Resource Management, and Approximation in a Data Stream Management System	2003	CIDR	0.0002867034
171	Monitoring Streams – A New Class of Data Management Applications	2002	VLDB	0.00027011593
200	Continuously Adaptive Continuous Queries over Streams	2002	SIGMOD	0.000254553
334	An Adaptive Query Execution System for Data Integration*	1999	SIGMOD	0.00020691326
369	Continuous Queries over Append-Only Databases	1992	SIGMOD	0.00019854467
424	Cost-based Query Scrambling for Initial Delays	1998	SIGMOD	0.0001848836
852	Streaming Queries over Streaming Data	2002	VLDB	0.00013451343
1,030	Rate-Based Query Optimization for Streaming Information Sources	2002	SIGMOD	0.00012407749
1,659	SQL Memory Management in Oracle9i	2002	VLDB	9.9624689e-05
1,796	Dynamic Pipeline Scheduling for Improving Interactive Query Performance	2001	VLDB	9.6193021e-05
3,363	SVP - a Model Capturing Sets, Streams, and Parallelism	1992	VLDB	7.3742531e-05
3,958	Tribeca: A Stream Database Manager For Network Traffic Analysis	1996	VLDB	6.898757e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,462	Update-Pattern-Aware Modeling and Processing of Continuous Queries	2005	SIGMOD
2	2,753	Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams	2003	VLDB
3	2,500	Operator Scheduling in a Data Stream Manager	2003	VLDB
4	2,782	Scheduling for shared window joins over data streams	2003	VLDB
5	14,089	Scheduling Continuous Queries in Data Stream Management Systems	2008	VLDB
6	8,843	Efficient Scheduling of Heterogeneous Continuous Queries	2006	VLDB
7	6,655	State-Slice: New Paradigm of Multi-query Optimization of Window-based Stream Queries	2006	VLDB
8	3,727	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB
9	1,666	Characterizing Memory Requirements for Queries over Continuous Data Streams	2002	PODS
10	9,784	Memory Efficient Scheduling of Query Pipeline Execution	2022	CIDR