{"id":"f435e7d9-6fe4-4aeb-99db-75b7ac01155f","arxiv_id":"2411.15835","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"UMJoin uses an LSM-Tree disk backend to keep long stream join state beyond memory, and TSC rewrites binary join plans into UMJoin nodes.","lead":"This paper proposes UMJoin, a multi-way stream join operator that stores long-lived join state on disk using an LSM-Tree, and a plan-rewriting method called TSC that converts binary join trees in streaming SQL into UMJoin plans. A systems reader might care because it addresses memory limits in long-running stateful stream joins, a practical bottleneck for streaming SQL engines.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The integrity guarantee is only proven without state expiration, but §3.1.2 introduces a hybrid expiration strategy that deletes state, and §4.2's own text contradicts itself on whether UMJoin produced complete output under 2GB memory.","rationale":"The reader's weakest_assumption identifies exactly the load-bearing gap: the integrity proof in Section 3.1.3 assumes no expiration, while Section 3.1.2 introduces expiration. My stress-test confirms this and sharpens it with a direct internal contradiction: Section 3.1.2 claims the design ensures completeness of results, and Section 4.2 contains two mutually incompatible statements about output completeness under 2GB memory (two-thirds vs. complete). This is not merely a missing edge case in the proof; it is a possible refutation of the central empirical claim. However, the issue is resolvable by re-running the experiment or by correcting the text, and the reader's CONDITIONAL verdict already requires such clarification before acceptance. Since my concern does not change the reader's recommended outcome, the verdict remains UNCHANGED. I see no additional fundamental flaw beyond this: the algebraic proof is sound under its stated assumptions, the LSM-Tree design is a plausible engineering contribution, and the TSC method's structural validation, while weaker than semantic equivalence checking, is not the central claim. The most valuable next step is the 2GB reproducibility test with expiration logging, which would settle whether the completeness claim holds or must be qualified.","tokens_in":11369,"tokens_out":7401,"duration_ms":62923,"concrete_test":"Re-run the TPC-DS 2GB experiment exactly as specified (Flink 1.17, parallelism 32, backend memory 2GB, the same four-table query), and compare the UMJoin output row count against the exact four-table join result computed offline from the input CSVs. If the counts differ, or if UMJoin outputs roughly two-thirds of the exact count, the completeness claim is false under memory constraint. In parallel, instrument the LSM-Tree backend to log all expiration events during the run; if any tuple is expired before the stream ends, the output cannot be complete even if the counts accidentally match, because the Section 3.1.3 proof does not apply once state is deleted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.1.3 proves Equation 6 only under the assumptions that the backend stores the full input volume and that data expiration is disregarded. Under those assumptions the proof reduces to a multiset expansion of the join and is sound. However, Section 3.1.2 immediately preceding it describes a 'hybrid expiration strategy' that removes state items after a time threshold based on retention business rules, and closes by claiming the design ensures 'the completeness of the processing results from the UMJoin operator.' These two passages are in direct tension: once state expires, a future tuple cannot probe against it, so the cumulative output misses those matches and Equation 6 fails because the state sets shrink rather than only grow. The tension becomes concrete in Section 4.2, which states that under the 2GB memory condition the UMJoin operator produced only about two-thirds of the total output results, yet two sentences later reports that the UMJoin operator successfully generated complete processing results across all three memory capacities. If the two-thirds sentence is accurate, the central empirical claim of complete processing under memory constraints is refuted for the 2GB case. If it is a typo for MultiStream, the paper must say so explicitly. Either way, the paper does not currently resolve the role of expiration in its experiments, so the claimed completeness guarantee is unsubstantiated in operation.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":11589,"tokens_out":2752,"duration_ms":26666,"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":[{"comment":"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).","section":"3.1.2-3.1.3, Eq. (6)"},{"comment":"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.","section":"4.2, first paragraph"},{"comment":"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.","section":"3.1.2, LSM-Tree Backend"}],"minor_comments":[{"comment":"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.","section":"1 and 3.1.1"},{"comment":"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.","section":"References"},{"comment":"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.","section":"4.3, Table 3"},{"comment":"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.","section":"4.2, Figures 5-7"},{"comment":"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.","section":"Algorithms 2 and 3"}],"recommendation":"major_revision","confidential_remarks":"The paper's core idea is reasonable and the algebraic proof is sound under its stated assumptions, so I do not see a reason for outright rejection. The stumbling block is that the manuscript currently overclaims completeness in the presence of its own expiration mechanism and contains a direct experimental contradiction in Section 4.2. Both issues are fixable within the scope of the paper: the authors can narrow the integrity claim, specify the expiration semantics, and correct or clarify the 2GB result. I would also ask the editor to ensure the reference list is complete before resubmission."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a plausible engineering contribution—an LSM-Tree-backed multi-way join operator plus a plan-rewriting step—but the paper's central completeness guarantee is unproven in the operating regime it actually implements, and the 2GB experiment contradicts the headline claim. The algebraic proof is fine under the idealization; the problem is that the idealization excludes the paper's own expiration mechanism.\n\nWhat's new: putting a disk-backed LSM state backend under a multi-way join operator (rather than chaining binary joins) is a sensible combination of known parts—MJoin/MultiStream plus the RocksDB state backend in Flink. The TSC method is a modest heuristic for recognizing binary join sub-trees and replacing them with UMJoin nodes. The paper does not oversell it much, and the example is clear.\n\nThe proof in Section 3.1.3 is a straightforward multiset expansion and it is correct as stated: if every stream is fully retained and increments don't overlap, the sum of per-input increments equals the total increment. The problem is the preceding subsection. Section 3.1.2 introduces a hybrid expiration strategy that removes old state based on business rules, and it claims this design still ensures completeness. Those two claims cannot both hold. Once state expires, a later tuple cannot probe it, so Equation 6 no longer applies. The paper needs to either remove the completeness claim for the expiring case or prove a bounded-approximation bound.\n\nThe experiments don't resolve this. Section 4.2 says that under 2GB, UMJoin produced only about two-thirds of the output results, and then two sentences later says UMJoin generated complete results across all three capacities. That is an internal contradiction on the paper's main empirical claim. If two-thirds is real, the memory-advantage story is refuted for 2GB; if it's a typo for MultiStream, it must be stated clearly. As written, it's impossible to tell. There are also smaller issues: no error bars, no code release, a missing citation for the MultiStream baseline, and the TSC validation checks only plan shape, not semantic equivalence or runtime behavior.\n\nBottom line: the core idea is worth discussing, and the proof is sound under the stated idealization. But as submitted, the paper does not substantiate the completeness guarantee that motivates it. This is a major-revision situation, not a desk reject. A careful referee could help the authors separate the ideal proof from the approximate reality and re-run the experiments with a clear definition of completeness. I'd send it out.","headline":"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.","tokens_in":12164,"tokens_out":2874,"would_cite":false,"duration_ms":24987,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Disk-backed joins keep long streams running in small memory","keywords":["streaming SQL","multi-way join","UMJoin","LSM-Tree","state backend","execution plan conversion","TPC-DS","TPC-H"],"falsifier":"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.","tokens_in":1485,"feed_emoji":"🗄️","tokens_out":2013,"duration_ms":73160,"temperature":0.7,"pith_summary":"The paper tries to establish that a multi-way stream join can be run by a single operator, UMJoin, whose per-stream state lives in a disk-backed LSM-Tree, so long state-based streams no longer have to fit in memory. It further argues that when the backend retains the full history of every input stream, UMJoin's per-input result increments sum exactly to the theoretical full join increment, so result integrity is preserved. To make this usable through streaming SQL, it proposes the Two-Step Convert (TSC) method, which rewrites binary-join execution plans into plans containing UMJoin nodes. Reported experiments on TPC-DS and TPC-H support both the memory-limited operation and the plan-conversion claims.","feed_headline":"Disk-backed joins keep long streams running in small memory","feed_subtitle":"A new UMJoin operator spills join state to disk, handling long streams where in-memory multi-way joins run out of memory.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"supplies the stream processing framework and long-term state storage background on which the UMJoin design and experiments are built.","marker":"[7]"},{"why":"supplies the LSM-Tree storage structure that the UMJoin state backend is based on.","marker":"[8]"},{"why":"supplies the LSM-Tree implementation concept, the RocksDB state backend, that UMJoin extends to a multi-way join setting.","marker":"[28]"},{"why":"is the in-memory hash-table multi-way stream join operator that UMJoin is compared against in the memory-constrained experiments.","marker":"[42]"}],"fun_headline_variants":["Disk-backed joins conquer long streams with limited memory","LSM-Tree state spills join to disk, cutting memory needs","Multi-way join spills to disk, survives long streams","One operator, disk-resident state, keeps long joins alive","Streaming SQL join spills to disk, survives memory limits"],"cache_read_input_tokens":14208,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Disk-backed joins conquer long streams with limited memory","LSM-Tree state spills join to disk, cutting memory needs","Multi-way join spills to disk, survives long streams","One operator, disk-resident state, keeps long joins alive","Streaming SQL join spills to disk, survives memory limits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001375,"raw_usage":{"total_tokens":5588,"prompt_tokens":975,"completion_tokens":4613,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":591,"completion_tokens_details":{"reasoning_tokens":4532}},"tokens_in":591,"tokens_out":4613,"duration_ms":28865,"temperature":1.0,"reasoning_tokens":4532,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T13:50:43.269702+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Apache flink: Stream analytics at scale","cited_arxiv_id":null,"evidence_quote":"supplies the stream processing framework and long-term state storage background on which the UMJoin design and experiments are built."},{"cited_title":"Myrocks: Lsm-tree database storage engine serving facebook’s social graph","cited_arxiv_id":null,"evidence_quote":"supplies the LSM-Tree storage structure that the UMJoin state backend is based on."},{"cited_title":"Rocksdb: Evolution of development priorities in a key-value store serving large-scale applications","cited_arxiv_id":null,"evidence_quote":"supplies the LSM-Tree implementation concept, the RocksDB state backend, that UMJoin extends to a multi-way join setting."}],"review_version":1}