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.00012262678
Overall Rank: 1,052 | 92.95%
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
128	The Design of the Borealis Stream Processing Engine	2005	CIDR	0.00030317705
433	Flexible Time Management in Data Stream Systems	2004	PODS	0.00018370788
1,285	Streaming Pattern Discovery in Multiple Time-Series	2005	VLDB	0.00011189681
1,762	Towards a Streaming SQL Standard	2008	VLDB	9.6949462e-05
1,841	Fault-Tolerance in the Borealis Distributed Stream Processing System	2005	SIGMOD	9.5155524e-05
2,510	Operator Scheduling in a Data Stream Manager	2003	VLDB	8.3492737e-05
2,563	Tuple Routing Strategies for Distributed Eddies	2003	VLDB	8.2699925e-05
3,380	Dynamic Plan Migration for Continuous Queries Over Data Streams	2004	SIGMOD	7.3415892e-05
3,586	STREAM: The Stanford Stream Data Manager (Demonstration Description)	2003	SIGMOD	7.1688645e-05
4,708	Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams	2004	SIGMOD	6.4419838e-05
5,128	Run-Time Operator State Spilling for Memory Intensive Long-Running Queries	2006	SIGMOD	6.248773e-05
6,178	Load Shedding in Stream Databases: A Control-Based Approach	2006	VLDB	5.8430416e-05
6,201	Finding Global Icebergs over Distributed Data Sets	2006	PODS	5.8350139e-05
8,154	Thrifty Query Execution via Incrementability	2020	SIGMOD	5.3732833e-05
8,290	CAPE: Continuous Query Engine with Heterogeneous-Grained Adaptivity	2004	VLDB	5.3446379e-05
8,874	Efficient Scheduling of Heterogeneous Continuous Queries	2006	VLDB	5.2455339e-05
9,206	Experimental Evaluation of Optimizing Memory Consumption in SAP HANA Using PEOopt	2025	SIGMOD	5.1944456e-05
9,822	Memory Efficient Scheduling of Query Pipeline Execution	2022	CIDR	5.1092136e-05
10,640	Enjima: A Resource-Adaptive Stream Processing System	2026	SIGMOD	4.9605343e-05
12,022	Klink: Progress-Aware Scheduling for Streaming Data Systems	2021	SIGMOD	4.9605343e-05
12,450	CE-Storm: Confidential Elastic Processing of Data Streams	2015	SIGMOD	4.9605343e-05
12,592	Utility-Maximizing Event Stream Suppression	2013	SIGMOD	4.9605343e-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.00051942573
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00040739114
149	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00028910892
152	Query Processing, Resource Management, and Approximation in a Data Stream Management System	2003	CIDR	0.00028566618
173	Monitoring Streams – A New Class of Data Management Applications	2002	VLDB	0.0002691472
201	Continuously Adaptive Continuous Queries over Streams	2002	SIGMOD	0.00025363666
336	An Adaptive Query Execution System for Data Integration*	1999	SIGMOD	0.00020619345
370	Continuous Queries over Append-Only Databases	1992	SIGMOD	0.00019781831
426	Cost-based Query Scrambling for Initial Delays	1998	SIGMOD	0.00018432573
856	Streaming Queries over Streaming Data	2002	VLDB	0.00013407433
1,035	Rate-Based Query Optimization for Streaming Information Sources	2002	SIGMOD	0.00012361763
1,652	SQL Memory Management in Oracle9i	2002	VLDB	9.9624199e-05
1,809	Dynamic Pipeline Scheduling for Improving Interactive Query Performance	2001	VLDB	9.5834851e-05
3,375	SVP - a Model Capturing Sets, Streams, and Parallelism	1992	VLDB	7.34646e-05
3,975	Tribeca: A Stream Database Manager For Network Traffic Analysis	1996	VLDB	6.8730259e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,485	Update-Pattern-Aware Modeling and Processing of Continuous Queries	2005	SIGMOD
2	2,762	Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams	2003	VLDB
3	2,510	Operator Scheduling in a Data Stream Manager	2003	VLDB
4	2,790	Scheduling for shared window joins over data streams	2003	VLDB
5	14,134	Scheduling Continuous Queries in Data Stream Management Systems	2008	VLDB
6	8,874	Efficient Scheduling of Heterogeneous Continuous Queries	2006	VLDB
7	6,671	State-Slice: New Paradigm of Multi-query Optimization of Window-based Stream Queries	2006	VLDB
8	3,735	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB
9	1,674	Characterizing Memory Requirements for Queries over Continuous Data Streams	2002	PODS
10	9,822	Memory Efficient Scheduling of Query Pipeline Execution	2022	CIDR