REVIEW 3 major objections 5 minor 28 references
Streaming SQL Multi-Way Join Method for Long State Streams
T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read Disk-backed joins keep long streams running in small memory
desk verdict An LSM-backed multi-way join operator with a correct but idealized integrity proof; the claimed completeness is undercut by the paper's own expiration design and an unresolved 2GB result. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the UMJoin operator with an LSM-Tree state backend. For each input stream it maintains a key-value store mapping join keys to lists of tuples; recent writes go into an in-memory skip list, which flushes to sorted string table files on disk, and probes move through the memory cache and disk levels. The carrying identity is the incremental-join algebra: with $S^*_{o_i} = S_{o_i} + dS_{o_i}$, expanding the full cross product and subtracting the old result leaves exactly one term per input increment, so the total result increment $dR$ equals $\sum_{i=1}^n dR_{o_i}$ (Equation 6). The second mechanism is TSC, a two-step method that identifies binary join tree patterns and replaces them with UMJoin nodes, with a pluggable pattern-recognition function.
What would settle it
Set up a two-stream join where the only match for a late-arriving tuple was inserted before the expiration deadline, and run UMJoin with that deadline enabled; if the late tuple produces no output because the old state was expired, then the practical completeness guarantee fails exactly where the operator's own expiration strategy intervenes.
Extended reading notes
Core claim
The central claim is that a multi-way stream join can be executed by one operator that keeps each input stream's history in a disk-resident LSM-Tree and, on each arriving tuple, inserts the tuple and probes the other streams' backends in order, halting at the first miss. The paper proves that if the full state of every stream is retained and inputs arrive as non-overlapping increments, then the sum of the operator's per-input result increments equals the theoretical total increment of the join, so the operator preserves result integrity. The operator therefore trades disk I/O for memory, and the paper reports that it completes a four-table TPC-DS stream join under 2, 3, and 4 GB of backend memory where an in-memory hash-table multi-way join operator terminates early.
Load-bearing premise
The load-bearing premise is that no data ever leaves the stored state before it stops being needed: the completeness proof assumes full retention and append-only inputs, while the implemented operator deliberately expires old state to prevent overflow.
Editorial extensions
If this is right
- Under full state retention, UMJoin's outputs are exact: the sum of per-input result increments equals the full join increment, so UMJoin can replace a binary join tree without changing the query result.
- On the four-table TPC-DS stream join with backend memory set to 2, 3, and 4 GB, UMJoin completed the stream while the in-memory hash-table operator terminated before finishing under the tightest memory settings.
- Against the best join order of a binary join tree using the same LSM-Tree backend at 9 GB of backend memory, UMJoin's output rate declined more gradually and it stored no intermediate join results, cutting that overhead substantially.
- The TSC conversion rewrote all 11 tested TPC-H multi-way join execution plans into plans with UMJoin nodes while preserving query logic, and the paper notes the pattern-recognition function can be modified to support other join-tree patterns.
- When backend memory grows large enough, the paper observes a crossover where a binary join tree becomes faster, attributing the shift to duplicate probing and disk overhead in UMJoin.
Reading between the lines
- A natural extension the paper leaves implicit is time-aware state cleanup: storing an expiration timestamp per tuple in the LSM-Tree value would let the backend itself enforce the hybrid expiration strategy, making the operator's practical completeness easier to reason about.
- Because TSC's pattern-recognition predicate is pluggable, the same two-step conversion could wrap other multi-way physical operators as long as their inputs form a join tree, generalizing the plan-conversion result beyond UMJoin.
- The reported crossover at 11-12 GB of backend memory suggests a hybrid policy, using a hash-table path when the full state fits in memory and the LSM-Tree path when it does not, would combine the best of both regimes; the paper does not test this.
- The completeness proof depends on append-only streams, so supporting updates or retractions would require a different delta-handling identity; that is likely the first obstacle to applying UMJoin to change-data-capture streams.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes UMJoin, a multi-way stream join operator whose state is stored in an LSM-Tree backend, with the goal of processing long state-based streams under memory constraints. It also proposes the TSC method for converting binary join tree execution plans into plans that contain UMJoin nodes, making the operator usable from streaming SQL. The central claims are that UMJoin preserves the integrity of its computed results when the backend can store the full input volume, that it can process long streams with limited memory where an in-memory MultiStream operator fails, and that TSC correctly transforms the tested TPC-H plan patterns. The integrity argument in Section 3.1.3 is a self-contained algebraic derivation, and the experiments use standard external benchmarks, but the manuscript contains an internal tension between the proof assumptions and the operator's actual expiration mechanism, plus a direct contradiction in the Section 4.2 experimental narrative.
Significance. If the claims hold, the paper would make a useful practical contribution: a disk-backed state backend for multi-way stream joins is a plausible way to extend stream processing to longer state streams, and the TSC plan-conversion method addresses a real gap in applying non-binary join operators in streaming SQL. Credit is due for the algebraic integrity proof, which is internally correct under its stated assumptions, and for the absence of fitted free parameters; the TPC-DS and TPC-H experiments give the work external grounding. However, the load-bearing completeness claim is currently stated more broadly than the proof supports, and the experimental report in Section 4.2 is self-contradictory about whether UMJoin produced complete output under 2GB memory. These issues must be resolved before the central claims can be accepted.
major comments (3)
- [3.1.2-3.1.3, Eq. (6)] The integrity proof in Section 3.1.3 explicitly assumes that the backend stores the full input volume and that data expiration is disregarded, and it relies on state sets only growing through Eq. (2). However, Section 3.1.2 introduces a hybrid expiration strategy that removes state items after a time threshold, and the same subsection claims that this design ensures the completeness of the processing results from the UMJoin operator. Once state expires, a future tuple cannot probe against the expired tuples, the cumulative output misses those matches, and Eq. (6) no longer follows because the state sets shrink. The paper must either restrict the integrity claim and the operator's specification to a no-expiration setting or extend both the proof and the design to state precisely what completeness means under expiration (e.g., completeness relative to a retention window).
- [4.2, first paragraph] The first results paragraph is internally contradictory: it states that under the 2GB memory condition the UMJoin operator 'produced only about two-thirds of the total output results,' and it says two sentences later that 'the UMJoin operator successfully generated complete processing results across all three memory capacities.' If the two-thirds statement is accurate, then the central empirical claim of complete processing under memory constraints is refuted for the 2GB case, and the 'complete results' sentence is false. If the two-thirds statement is a typo or refers to the MultiStream operator, the paper must say so explicitly. The authors should also report exact output counts or ratios for each memory configuration, and state whether state expiration was enabled during these experiments.
- [3.1.2, LSM-Tree Backend] The design section claims that the hybrid expiration strategy 'ensures ... the completeness of the processing results from the UMJoin operator,' but no formal or experimental evidence for this claim is provided. Because expiration is a state-deletion mechanism, this claim is in direct tension with Eq. (6), which is derived under the assumption of no deletion. The description of the expiration rule is also underspecified: 'a predetermined time threshold' and 'business rules regarding retention necessity' are not defined operationally, so a reader cannot tell when state is removed or what completeness property survives.
minor comments (5)
- [1 and 3.1.1] The join operator is written as × in Eq. (1) and the text says '× denotes the join operation,' but there is no formal definition of the schema compatibility condition, the join predicate, or the handling of duplicate matches. A concrete tuple-level example of the probing procedure would make the semantics much clearer.
- [References] The text cites references [42], [100], [101], and [102] in Sections 4.2 and 4.3, but the bibliography only lists entries up to [28]. Missing references must be added or the citation numbers renumbered.
- [4.3, Table 3] Table 3 lists check marks for 11 TPC-H queries but gives no quantitative criterion for success. The text says the transformed plan 'maintained logical consistency with the original plan,' but the verification procedure is not described; stating how equality or logical equivalence of plans was checked would strengthen the claim of 100% conversion accuracy.
- [4.2, Figures 5-7] The runtime and output-rate figures do not report the number of experimental runs, variance, or error bars. Given that the paper draws conclusions about gradual versus rapid declines in output rate, some indication of run-to-run variability is needed.
- [Algorithms 2 and 3] The pseudocode uses notation such as 'CAN BEMULTIJOIN GROUP MEMBER' and 'visitedM ap' inconsistently, and in Algorithm 3 the recursive call at line 5 does not pass the visitedM ap argument that the function signature implies. Cleaning up the pseudocode would improve reproducibility.
Circularity Check
No significant circularity: the integrity proof is a self-contained conditional algebra identity, and the empirical claims are evaluated against external TPC-DS/TPC-H benchmarks without fitted parameters or author self-citation loops.
full rationale
The paper's central derivations are not circular. Section 3.1.3 proves Equation 6 under the explicitly stated assumptions that the backend stores the full input volume and that data expiration is disregarded; the proof is a polynomial expansion of the multiset join expression and is self-contained. The LSM-Tree implementation is adapted from RocksDB/Flink infrastructure, which is legitimate prior engineering support rather than a self-referential argument. The TSC plan-conversion validation uses TPC-H queries and checks plan-pattern replacement independently of the paper's own claims, so no fitted parameter is renamed as a prediction. The claimed completeness under memory constraints does contain a serious internal tension, not a circularity: Section 3.1.2 introduces a hybrid expiration strategy that deletes state, while Section 3.1.3 proves integrity only when expiration is disregarded; moreover, Section 4.2 states that UMJoin produced only about two-thirds of the total output under the 2GB condition but then says it generated complete results across all memory capacities. These are correctness/consistency concerns about whether the operational guarantee matches the conditional proof, not reductions of the derivation to its own inputs. The text also contains dangling citations ([42] and [100]-[102] do not appear in the bibliography), a completeness defect in the manuscript, but it does not affect circularity. Accordingly, the circularity score is 0.
Assumptions & free parameters
assumptions (5)
- domain assumption Streams are append-only with no updates, deletes, or overlapping increments.
- domain assumption The backend disk storage is large enough to hold the entire stream history.
- domain assumption No state expiration is triggered during the integrity analysis.
- standard math Join distributes over the union of tuples.
- domain assumption LSM-Tree point lookups return all tuples matching the join key from the stored state.
invented entities (2)
-
UMJoin operator
independent evidence
-
TSC method
independent evidence
Cite this review
Pith. "Pith review of Streaming SQL Multi-Way Join Method for Long State Streams." pith.science (2026). https://pith.science/paper/SSIXNIPF
@misc{pith2026241115835,
author = {Pith},
title = {Pith review of: Streaming SQL Multi-Way Join Method for Long State Streams},
year = {2026},
howpublished = {\url{https://pith.science/paper/SSIXNIPF}},
note = {Machine review of arXiv:2411.15835}
}
read the original abstract
Streaming computing effectively manages large-scale streaming data in real-time, making it ideal for applications such as real-time recommendations, anomaly detection, and monitoring, all of which require immediate processing. In this context, the multi-way stream join operator is crucial, as it combines multiple data streams into a single operator, providing deeper insights through the integration of information from various sources. However, challenges related to memory limitations can arise when processing long state-based data streams, particularly in the area of streaming SQL. In this paper, we propose a streaming SQL multi-way stream join method that utilizes the LSM-Tree to address this issue. We first introduce a multi-way stream join operator called UMJoin, which employs an LSM-Tree state backend to leverage disk storage, thereby increasing the capacity for storing multi-way stream states beyond what memory can accommodate. Subsequently, we develop a method for converting execution plans, referred to as TSC, specifically for the UMJoin operator. This method identifies binary join tree patterns and generates corresponding multi-way stream join nodes, enabling us to transform execution plans based on binary joins into those that incorporate UMJoin nodes. This transformation facilitates the application of the UMJoin operator in streaming SQL. Experiments with the TPC-DS dataset demonstrate that the UMJoin operator can effectively process long state-based data streams, even with limited memory. Furthermore, tests on execution plan conversion for multi-way stream join queries using the TPC-H benchmark confirm the effectiveness of the TSC method in executing these conversions.
Figures
Figures from the paper (5 more)
Reference graph
Works this paper leans on
-
[1]
S. Kassing, D. Bhattacherjee, A. B. Águas, et al. Exploring the “internet from space” with hypatia. In Proceedings of the ACM Internet Measurement Conference , pages 214–229, New York, NY , USA, 2020. Association for Computing Machinery
work page 2020
-
[2]
L. Turchet, M. Lagrange, C. Rottondi, et al. The internet of sounds: Convergent trends, insights, and future directions. IEEE Internet of Things Journal , 10(13):11264–11292, 2023
work page 2023
-
[3]
Perkembangan internet of things (iot) pada sektor energi: Sistematik literatur review
A G Prawiyogi and A S Anwar. Perkembangan internet of things (iot) pada sektor energi: Sistematik literatur review. Jurnal MENTARI: Manajemen, Pendidikan dan Teknologi Informasi, 1(2), 2023
work page 2023
-
[4]
Identifying factors influencing consumers not to skip trueview advertising on youtube
K Napontun and P Senachai. Identifying factors influencing consumers not to skip trueview advertising on youtube. ABAC Journal, 43(1):85–102, 2023
work page 2023
-
[5]
Streaming platforms based on blockchain technology: A business model impact analysis
R Soares, A Araújo, G Rodrigues, et al. Streaming platforms based on blockchain technology: A business model impact analysis. In S Latifi, editor, ITNG 2023 20th International Conference on Information Technology-New Generations, pages 143–149. Springer International Publishing, 2023
work page 2023
-
[6]
Financial time series forecasting: A data stream mining-based system
Z Bousbaa, J Sanchez-Medina, and O Bencharef. Financial time series forecasting: A data stream mining-based system. Electronics, 12(9):2039, 2023
work page 2023
-
[7]
Apache flink: Stream analytics at scale
Katsifodimos A and Schelter S. Apache flink: Stream analytics at scale. In 2016 IEEE International Conference on Cloud Engineering Workshop (IC2EW), pages 193–193, 2016
work page 2016
-
[8]
Myrocks: Lsm-tree database storage engine serving facebook’s social graph
Y Matsunobu, S Dong, and H Lee. Myrocks: Lsm-tree database storage engine serving facebook’s social graph. Proceedings of the VLDB Endowment , 13(12):3217–3230, 2020
work page 2020
Show all 28 references
-
[9]
An efficient architecture for processing real-time traffic data streams using apache flink
Deepthi B G, Rani K S, Krishna P V , et al. An efficient architecture for processing real-time traffic data streams using apache flink. Multimedia Tools and Applications, 2023
2023
-
[10]
Big data analysis: Apache storm perspective
Hussain Iqbal M SZABIST and Rahim Soomro T. Big data analysis: Apache storm perspective. International Journal of Computer Trends and Technology, 19(1):9–14, 2015
2015
-
[11]
Analyzing apache storm as core for an event processing network model
Schulze C, Gerner C, Tyca M, et al. Analyzing apache storm as core for an event processing network model. In Intelligent Systems and Applications , pages 397–410, Cham, 2024. Springer Nature Switzerland
2024
-
[12]
Structured streaming: A declarative api for real-time applications in apache spark
Armbrust M, Das T, Torres J, et al. Structured streaming: A declarative api for real-time applications in apache spark. In Proceedings of the 2018 International Conference on Management of Data , pages 601–613, 2018
2018
-
[13]
A gas concentration prediction method driven by a spark streaming framework
Huang Y , Fan J, Yan Z, et al. A gas concentration prediction method driven by a spark streaming framework. Energies, 15(15):5335, 2022
2022
-
[14]
Integrating heterogeneous stream and historical data sources using sql.Journal of Information and Data Management , 13(2), 2022
Amará J, Ströele V , Braga R, et al. Integrating heterogeneous stream and historical data sources using sql.Journal of Information and Data Management , 13(2), 2022
2022
-
[15]
Unleashing the power of querying streaming data in a temporal database world: A relational algebra approach
Grandi F, Mandreoli F, Martoglia R, et al. Unleashing the power of querying streaming data in a temporal database world: A relational algebra approach. Information Systems, 103:101872, 2022
2022
-
[16]
Adaptive sql query optimization in distributed stream processing: A preliminary study
Sharkova D, Chernokoz A, Trofimov A, et al. Adaptive sql query optimization in distributed stream processing: A preliminary study. In Software F oundations for Data Interoperability, pages 96–109, Cham, 2022. Springer International Publishing. 13
2022
-
[17]
Aurora: a data stream management system
Abadi D, Carney D, Çetintemel U, et al. Aurora: a data stream management system. In Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data , page 666, New York, NY , USA, 2003. Association for Computing Machinery
2003
-
[18]
Stream: the stanford stream data manager (demonstration description)
Arasu A, Babcock B, Babu S, et al. Stream: the stanford stream data manager (demonstration description). In Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data , page 665, New York, NY , USA, 2003. Association for Computing Machinery
2003
-
[19]
S. A. Noghabi, K. Paramasivam, Y . Pan, et al. Samza: stateful scalable stream processing at linkedin.Proceedings of the VLDB Endowment , 10(12):1634–1645, 2017
2017
-
[20]
Drohobytskiy, V
Y . Drohobytskiy, V . Brevus, and Y . Skorenkyy. Spark structured streaming: Customizing kafka stream processing. In 2020 IEEE Third International Conference on Data Stream Mining & Processing (DSMP) , pages 296–299, 2020
2020
-
[21]
Van Dongen and D
G. Van Dongen and D. Van Den Poel. Influencing factors in the scalability of distributed stream processing jobs. IEEE Access, 9:109413–109431, 2021
2021
-
[22]
Petkovi´c
D. Petkovi´c. Specification of row pattern recognition in the sql standard and its implementations. Datenbank- Spektrum, 22(2):163–174, 2022
2022
-
[23]
Zhang, F
Y . Zhang, F. Zhang, H. Li, et al. Compressstreamdb: Fine-grained adaptive stream processing without decompres- sion. In 2023 IEEE 39th International Conference on Data Engineering (ICDE) , pages 408–422, 2023
2023
-
[24]
An lsm tree augmented with b+ tree on nonvolatile memory
D Kim, J Lee, K S Lim, et al. An lsm tree augmented with b+ tree on nonvolatile memory. ACM Transactions on Storage, 20(1):4:1–4:24, 2024
2024
-
[25]
Shadowsync: Latency long tail caused by hidden synchronization in real- time lsm-tree based stream processing systems
S Zhang, Q Wang, Y Kanemasa, et al. Shadowsync: Latency long tail caused by hidden synchronization in real- time lsm-tree based stream processing systems. In Proceedings of the 23rd ACM/IFIP International Middleware Conference, pages 281–294. Association for Computing Machinery, 2022
2022
-
[26]
Splitzns: Towards an efficient lsm-tree on zoned namespace ssds
D Huang, D Feng, Q Liu, et al. Splitzns: Towards an efficient lsm-tree on zoned namespace ssds. ACM Transactions on Architecture and Code Optimization, 20(3):45:1–45:26, 2023
2023
-
[27]
Flowkv: A semantic-aware store for large-scale state management of stream processing engines
G Lee, J Maeng, J Park, et al. Flowkv: A semantic-aware store for large-scale state management of stream processing engines. In Proceedings of the Eighteenth European Conference on Computer Systems , pages 768–783. Association for Computing Machinery, 2023
2023
-
[28]
Rocksdb: Evolution of development priorities in a key-value store serving large-scale applications
S Dong, A Kryczka, Y Jin, et al. Rocksdb: Evolution of development priorities in a key-value store serving large-scale applications. ACM Transactions on Storage, 17(4):26:1–26:32, 2021. 14
2021
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.