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: 3499
Venue: SIGMOD
Year: 2003
Pagerank: 0.00012563656
Overall Rank: 1,027 | 92.96%
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.00030738755
424	Flexible Time Management in Data Stream Systems	2004	PODS	0.0001870735
1,252	Streaming Pattern Discovery in Multiple Time-Series	2005	VLDB	0.00011483752
1,718	Towards a Streaming SQL Standard	2008	VLDB	9.9297933e-05
1,789	Fault-Tolerance in the Borealis Distributed Stream Processing System	2005	SIGMOD	9.7502324e-05
2,447	Operator Scheduling in a Data Stream Manager	2003	VLDB	8.5728111e-05
2,513	Tuple Routing Strategies for Distributed Eddies	2003	VLDB	8.48462e-05
3,321	Dynamic Plan Migration for Continuous Queries Over Data Streams	2004	SIGMOD	7.5216049e-05
3,515	STREAM: The Stanford Stream Data Manager (Demonstration Description)	2003	SIGMOD	7.3540246e-05
4,596	Static Optimization of Conjunctive Queries with Sliding Windows Over Infinite Streams	2004	SIGMOD	6.6133976e-05
5,035	Run-Time Operator State Spilling for Memory Intensive Long-Running Queries	2006	SIGMOD	6.3920216e-05
6,033	Load Shedding in Stream Databases: A Control-Based Approach	2006	VLDB	5.9998228e-05
6,060	Finding Global Icebergs over Distributed Data Sets	2006	PODS	5.9914746e-05
7,967	Thrifty Query Execution via Incrementability	2020	SIGMOD	5.5169373e-05
8,139	CAPE: Continuous Query Engine with Heterogeneous-Grained Adaptivity	2004	VLDB	5.4803781e-05
8,679	Efficient Scheduling of Heterogeneous Continuous Queries	2006	VLDB	5.3862828e-05
9,007	Experimental Evaluation of Optimizing Memory Consumption in SAP HANA Using PEOopt	2025	SIGMOD	5.3338237e-05
9,612	Memory Efficient Scheduling of Query Pipeline Execution	2022	CIDR	5.2449175e-05
10,368	Enjima: A Resource-Adaptive Stream Processing System	2026	SIGMOD	5.093636e-05
11,665	Klink: Progress-Aware Scheduling for Streaming Data Systems	2021	SIGMOD	5.093636e-05
12,108	CE-Storm: Confidential Elastic Processing of Data Streams	2015	SIGMOD	5.093636e-05
12,252	Utility-Maximizing Event Stream Suppression	2013	SIGMOD	5.093636e-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.00052982574
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00041071971
150	Query Processing, Resource Management, and Approximation in a Data Stream Management System	2003	CIDR	0.00029208207
151	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00029161879
167	Monitoring Streams – A New Class of Data Management Applications	2002	VLDB	0.0002757283
193	Continuously Adaptive Continuous Queries over Streams	2002	SIGMOD	0.00025964286
328	An Adaptive Query Execution System for Data Integration*	1999	SIGMOD	0.00021081317
368	Continuous Queries over Append-Only Databases	1992	SIGMOD	0.00019968151
419	Cost-based Query Scrambling for Initial Delays	1998	SIGMOD	0.0001879684
832	Streaming Queries over Streaming Data	2002	VLDB	0.00013736125
1,016	Rate-Based Query Optimization for Streaming Information Sources	2002	SIGMOD	0.00012645699
1,706	SQL Memory Management in Oracle9i	2002	VLDB	9.9628446e-05
1,763	Dynamic Pipeline Scheduling for Improving Interactive Query Performance	2001	VLDB	9.8124899e-05
3,299	SVP - a Model Capturing Sets, Streams, and Parallelism	1992	VLDB	7.5418401e-05
3,879	Tribeca: A Stream Database Manager For Network Traffic Analysis	1996	VLDB	7.0504052e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,321	Update-Pattern-Aware Modeling and Processing of Continuous Queries	2005	SIGMOD
2	3,255	Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams	2003	VLDB
3	2,447	Operator Scheduling in a Data Stream Manager	2003	VLDB
4	2,735	Scheduling for shared window joins over data streams	2003	VLDB
5	13,778	Scheduling Continuous Queries in Data Stream Management Systems	2008	VLDB
6	8,679	Efficient Scheduling of Heterogeneous Continuous Queries	2006	VLDB
7	6,528	State-Slice: New Paradigm of Multi-query Optimization of Window-based Stream Queries	2006	VLDB
8	3,657	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB
9	1,656	Characterizing Memory Requirements for Queries over Continuous Data Streams	2002	PODS
10	9,612	Memory Efficient Scheduling of Query Pipeline Execution	2022	CIDR