{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T16:22:33Z","timestamp":1781194953226,"version":"3.54.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:p>Many stream-processing systems enforce an order on data streams during query evaluation to help unblock blocking operators and purge state from stateful operators. Such in-order processing (IOP) systems not only must enforce order on input streams, but also require that query operators preserve order. This order-preserving requirement constrains the implementation of stream systems and incurs significant performance penalties, particularly for memory consumption. Especially for high-performance, potentially distributed stream systems, the cost of enforcing order can be prohibitive. We introduce a new architecture for stream systems, out-of-order processing (OOP), that avoids ordering constraints. The OOP architecture frees stream systems from the burden of order maintenance by using explicit stream progress indicators, such as punctuation or heartbeats, to unblock and purge operators. We describe the implementation of OOP stream systems and discuss the benefits of this architecture in depth. For example, the OOP approach has proven useful for smoothing workload bursts caused by expensive end-of-window operations, which can overwhelm internal communication paths in IOP approaches. We have implemented OOP in two stream systems, Gigascope and NiagaraST. Our experimental study shows that the OOP approach can significantly outperform IOP in a number of aspects, including memory, throughput and latency.<\/jats:p>","DOI":"10.14778\/1453856.1453890","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"274-288","source":"Crossref","is-referenced-by-count":129,"title":["Out-of-order processing"],"prefix":"10.14778","volume":"1","author":[{"given":"Jin","family":"Li","sequence":"first","affiliation":[{"name":"Portland State University, Portland, OR"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kristin","family":"Tufte","sequence":"additional","affiliation":[{"name":"Portland State University, Portland, OR"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vladislav","family":"Shkapenyuk","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs - Research, Florham Park, NJ"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vassilis","family":"Papadimos","sequence":"additional","affiliation":[{"name":"Portland State University, Portland, OR"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Theodore","family":"Johnson","sequence":"additional","affiliation":[{"name":"AT&amp;T Labs - Research, Florham Park, NJ"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Maier","sequence":"additional","affiliation":[{"name":"Portland State University, Portland, OR"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2008,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-003-0095-z"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-004-0147-z"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/335191.335420"},{"key":"e_1_2_1_4_1","volume-title":"J. Resource Sharing in Continuous Sliding-window Aggregates. VLDB","author":"Arasu A.","year":"2004","unstructured":"Arasu , A. , Widom , J. Resource Sharing in Continuous Sliding-window Aggregates. VLDB 2004 . Arasu, A., Widom, J. Resource Sharing in Continuous Sliding-window Aggregates. VLDB 2004."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066160"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007575"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872838"},{"key":"e_1_2_1_8_1","volume-title":"Joining Punctuated Streams. EDBT","author":"Ding L.","year":"2004","unstructured":"Ding , L. , Joining Punctuated Streams. EDBT 2004 . Ding, L., et al. Joining Punctuated Streams. EDBT 2004."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031171.1031189"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315495"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497489"},{"key":"e_1_2_1_12_1","volume-title":"SSDBM","author":"Hammad M.","year":"2005","unstructured":"Hammad , M. et al. Optimizing In-Order Execution of Continuous Queries over Streamed Sensor Data . SSDBM 2005 . Hammad, M. et al. Optimizing In-Order Execution of Continuous Queries over Streamed Sensor Data. SSDBM 2005."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315478"},{"key":"e_1_2_1_14_1","volume-title":"VLDB","author":"Li","year":"2006","unstructured":"Li , Hua-Gang, Safety Guarantee of Continuous Join Queries over Punctuated Data Streams . VLDB 2006 . Li, Hua-Gang, et al. Safety Guarantee of Continuous Join Queries over Punctuated Data Streams. VLDB 2006."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1058150.1058158"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066193"},{"key":"e_1_2_1_17_1","volume-title":"VLDB","author":"Theodore Johnson","year":"2005","unstructured":"Theodore Johnson , et al. A Heartbeat Mechanism and Its Application in Gigascope . VLDB 2005 . Theodore Johnson, et al. A Heartbeat Mechanism and Its Application in Gigascope. VLDB 2005."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2003.1260804"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071690.1064223"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142543"},{"key":"e_1_2_1_21_1","volume-title":"et al. The Niagara Internet Query System","author":"Naughton J.","year":"2001","unstructured":"Naughton , J. et al. The Niagara Internet Query System . IEEE Data Eng. Bulletin 24(2), June 2001 . Naughton, J. et al. The Niagara Internet Query System. IEEE Data Eng. Bulletin 24(2), June 2001."},{"key":"e_1_2_1_22_1","unstructured":"Passive Measurement and Analysis Project. San Diego Supercomputer Center. http:\/\/pma.nlanr.net\/PMA.  Passive Measurement and Analysis Project. San Diego Supercomputer Center. http:\/\/pma.nlanr.net\/PMA."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/645925.671663"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316832"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055596"},{"key":"e_1_2_1_26_1","volume-title":"J. Memory-Limited Execution of Windowed Stream Joins. VLDB","author":"Srivastava U","year":"2004","unstructured":"Srivastava , U , Widom , J. Memory-Limited Execution of Windowed Stream Joins. VLDB 2004 . Srivastava, U, Widom, J. Memory-Limited Execution of Windowed Stream Joins. VLDB 2004."},{"key":"e_1_2_1_27_1","unstructured":"StreamSQL. http:\/\/www.streamsql.org.  StreamSQL. http:\/\/www.streamsql.org."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1198390"},{"key":"e_1_2_1_30_1","volume-title":"XJoin: A Reactively-Scheduled Pipelined Join Operator","author":"Urhan T.","year":"2000","unstructured":"Urhan , T. , Franklin , M. J. XJoin: A Reactively-Scheduled Pipelined Join Operator . IEEE Data Eng. Bull . 23(2), 2000 . Urhan, T., Franklin, M. J. XJoin: A Reactively-Scheduled Pipelined Join Operator. IEEE Data Eng. Bull. 23(2), 2000."},{"key":"e_1_2_1_31_1","volume-title":"Dynamic Pipeline Scheduling for Improving Interactive Query Performance. VLDB","author":"Urban T.","year":"2001","unstructured":"Urban , T. and Franklin , M. J . Dynamic Pipeline Scheduling for Improving Interactive Query Performance. VLDB 2001 . Urban, T. and Franklin, M. J. Dynamic Pipeline Scheduling for Improving Interactive Query Performance. VLDB 2001."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315477"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1453856.1453890","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:08:48Z","timestamp":1672225728000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1453856.1453890"}},"subtitle":["a new architecture for high-performance stream systems"],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.14778\/1453856.1453890"],"URL":"https:\/\/doi.org\/10.14778\/1453856.1453890","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2008,8]]}}}