{"id":"98a2f13a-16dd-4954-8fc5-17fd44f31f38","arxiv_id":"2411.15827","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"A runtime-optimized multi-way stream join operator uses exponential smoothing forecasts and a cost-based dpPick search to reorder probes each cycle, outperforming static orderings on a TPC-DS four-way join.","lead":"This paper proposes a way to make multi-way stream joins faster by repeatedly reordering the join steps at runtime based on predicted data patterns. It could help streaming systems adapt to changing data rates without manual tuning.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The reported TPC-DS gains do not actually exercise runtime adaptation: randomly shuffled static data is not a changing stream, so the central claim about non-stationary streams is untested.","rationale":"The reader's weakest assumption centers on uncalibrated constants and smoothing under non-stationarity. I go further upstream: the experiments never create non-stationarity, so the central claim cannot be evaluated at all. The constants alpha_q, alpha_m, c, m and the smoothing parameters would matter only if the workload actually changed; on a stationary random shuffle, predicting 'next cycle' statistics is a variance-reduction exercise, not adaptation. This is why the concern is load-bearing: the strongest experimental claim (22/24 orderings, average 31.2% improvement) is consistent with a static-order explanation. The cost-model mu-factor issue in Eqs. 1, 7, and 8 is also worth checking, but the non-stationarity gap is broader: even a perfect cost model would not validate runtime adaptation if the stream never changes. I therefore recommend keeping the verdict conditional, with the condition being a non-stationary workload experiment; no internal inconsistency forces rejection.","tokens_in":14301,"tokens_out":9105,"duration_ms":89422,"concrete_test":"Re-run the Section 5.2 comparison on synthetic four-stream workloads with controlled non-stationarity: every T cycles, switch join selectivity by an order of magnitude (e.g., shift hot key ranges, or double one stream's arrival rate), and also include a burst period. Use the same T and L values as Section 5.4. Record per-cycle runtime and the probe order dpPick selects. If dpPick's average improvement over fixedOrder and over dpPick_noSmooth disappears or reverses in the non-stationary phases, the claim that cyclic re-prediction and reoptimization helps on changing streams is falsified; if it persists, the central claim is supported. Reporting the chosen order each cycle would additionally verify that the optimizer is actually reacting to regime changes.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that cyclic reoptimization of probe order using predicted statistics improves multi-way stream join efficiency on changing streams. The only experimental support (Section 5.2, Fig. 2) feeds a static TPC-DS scale-factor-10 dataset to Kafka in random order (Section 5.1). Randomizing the arrival order of a fixed dataset changes the tuple sequence but not the underlying statistics: matching rates, match counts, and key counts in each cycle remain samples from the same stationary distribution. There is no regime shift, burst, or distribution drift for the optimizer to track. Consequently, the reported 6.0% to 53.7% runtime reductions versus fixedOrder, and the smoothing ablation in Section 5.3, can be explained by dpPick selecting a better static order (or by noise reduction), not by runtime adaptation to changing streams. Section 5.1's statement that random order 'simulate[s] real-time data streams that change dynamically' is the key unsupported step; the experiments as designed cannot validate the central claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes a runtime-optimized multi-way stream join operator for state-based stream processing on Flink. The operator divides execution into cycles, collects per-cycle statistics (match success probability, average number of matches, and key counts), predicts next-cycle statistics using exponential smoothing, and invokes a dynamic-programming algorithm, dpPick, that uses an approximate cost model to choose a probe order for each input stream. Experiments on a four-table TPC-DS join compare dpPick with fixed-order, selectivity-first, and greedy-cost baselines across 24 initial orders, together with ablations that remove query cost, match cost, or smoothing. The paper reports large average runtime reductions over the baselines and concludes that the adaptive strategy improves processing efficiency for unknown, changing data streams.","tokens_in":14569,"tokens_out":5813,"duration_ms":52455,"significance":"If the central claim were established, runtime reoptimization of probe order for multi-way stream joins would be a useful and practical contribution to stream processing engines, especially for workloads with drifting statistics. The paper's strengths include a clean recursive cost formulation, a memoized dynamic-programming optimizer (Algorithm 3), a clearly described operator architecture, and an ablation design that separates query-cost, match-cost, and smoothing contributions. The main limitation is evidential: the experiments use a static dataset and therefore do not exercise the adaptation mechanism that motivates the work, and the cost model's free parameters are left unspecified. The contribution is plausible but not yet demonstrated at the level claimed.","major_comments":[{"comment":"The experimental design does not test adaptation to changing streams. Randomizing the order in which a static TPC-DS dataset is read from Kafka changes tuple interleaving but leaves the marginal distributions of keys, match counts, and match rates stationary; successive optimization cycles see sampling noise, not drift. The reported 6.0% to 53.7% reductions versus fixedOrder can therefore be explained by dpPick finding a better static order rather than by runtime tracking of non-stationary statistics. The statement in Section 5.1 that random order 'simulate[s] real-time data streams that change dynamically' is not justified. Please add experiments with explicit drift or bursts (e.g., changing key distributions, arrival rates, or selectivities over cycles) and compare against a no-reoptimization control and an adaptive baseline such as A-Greedy.","section":"Section 5.1, Section 5.2"},{"comment":"The cost model contains unspecified constants alpha_q, alpha_m, c, and m, and the smoothing method has unspecified parameters (Holt's alpha, beta, and damping phi). The paper reports no values, no calibration procedure, and no sensitivity analysis. Because dpPick selects probe orders by minimizing this approximate cost, the ranking of orders could depend strongly on these constants; without evidence of robustness, the claim that dpPick identifies a near-optimal order is not well supported. Please specify parameter values, state how they were chosen, and report sensitivity of the selected order and runtime to these parameters.","section":"Sections 4.1-4.3, Eqs. (4)-(8)"},{"comment":"The performance comparison rests on a single four-way join query with no repeated runs, error bars, or statistical tests. The statement that dpPick 'significantly outperforms' the comparative methods is not supported by the evidence as reported. Please provide multiple runs with variance estimates, additional query shapes with different selectivities and numbers of streams, and ideally additional datasets.","section":"Section 5.2"},{"comment":"dpPick enumerates all possible probe sequences via depth-first search, and the paper gives no complexity analysis. For a complete join graph with n input streams, the number of candidate sequences is O(n!), which is prohibitive for the 'large-scale' multi-way joins claimed in the title and for per-cycle reoptimization beyond small n. Please report the time complexity of dpPick and include experiments with more than four streams to substantiate the scalability claim.","section":"Section 4.2, Algorithms 3-4"},{"comment":"The smoothing ablation is not conclusive for the same reason as the first major comment: on randomized static data, the previous cycle's statistics are nearly exchangeable with the smoothed prediction, so the 2.5% to 11.6% differences may reflect noise or one-workload effects rather than prediction quality. Please report prediction error (e.g., MAPE) of the smoothing method against held-out cycles and evaluate the ablation on drifting streams.","section":"Section 5.3"}],"minor_comments":[{"comment":"The text cites 'MJoin[35]' and 'GrubJoin[19]', but references [35] and [19] are unrelated papers; the correct citations appear to be [6] and [7]. Similarly, 'MultiStream[42]' does not exist in the reference list; the MultiStream operator is cited as [8] and [32].","section":"Section 5.2"},{"comment":"Line 2 initializes subMemo with the key '(null, 0)', which does not match the subsequence keys used in calculateCost; line 10 also contains a typo, 'subsequence' for 'subSequence'. Please make the memoization key type consistent.","section":"Algorithm 3"},{"comment":"Line 21 contains the typo 'allSequencces', and line 3 omits a separator between 'allSequences.add(...)' and 'return'.","section":"Algorithm 4"},{"comment":"The text mentions Holt's linear trend method and damping trend method but gives no update equations. Please add the smoothing equations or a precise citation to the definitions used.","section":"Section 4.3"},{"comment":"The explanation of kappa/(2m) as the average linked-list traversal length is imprecise; under uniform hashing with separate chaining, the expected number of probes for a successful search is 1 + kappa/(2m), while the average chain length is kappa/m. Please clarify the intended interpretation.","section":"Eq. (5)"}],"recommendation":"major_revision","confidential_remarks":"The manuscript reads like a preliminary technical report rather than a fully validated systems paper. The central technical idea is reasonable, and the requested additional experiments and parameter specifications are within the scope of a revision, so I do not recommend rejection. The main risk is that the adaptation claim is currently untested; if the authors cannot demonstrate behavior on drifting streams, the contribution reduces to static join-order optimization, which has a different and weaker significance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper has a plausible mechanism but its only experiment doesn't support the central claim. dpPick—reoptimizing probe order each cycle with quadratic exponential smoothing and memoized DP—is a reasonable engineering contribution. The cost model explicitly includes query cost, which earlier multi-way join operators mostly ignore, and the ablation shows both cost terms and smoothing matter. That is real, incremental value.\n\nThe problem is Section 5.1: they feed TPC-DS to Kafka in random order and call it \"dynamic.\" Randomizing a fixed dataset changes tuple arrival order, not the underlying statistics. Match rates, match counts, and key counts stay samples from the same stationary distribution. There is no drift, burst, or regime shift for the optimizer to track. So the 6–53% improvement over fixedOrder is most plausibly dpPick finding a better static order than the given initial order, not adapting to a changing stream. The smoothing ablation (dpPick vs dpPick_noSmooth) could also just be variance reduction, not trend tracking. The central claim—that runtime reoptimization helps on non-stationary streams—is untested.\n\nOther soft spots: no error bars or repeated runs; one four-way join query; no adaptive baseline like A-Greedy or other reoptimization methods; the cost coefficients alpha_q, alpha_m, c, m are never calibrated or swept; no sensitivity analysis for T or L beyond two orders; no code or data released. These are fixable, but together they make the current evidence weak.\n\nI should also say the math is not contradictory. The cost recursion is standard, the memoized enumeration is correct for small n, and the paper is honest about the heuristic nature of the approximation. The related-work coverage is decent.\n\nBottom line: this is a workshop-level idea that needs a real evaluation before the \"runtime adaptation\" claim can be taken seriously. If the authors rerun with injected drift, add error bars, and release the code, the result might hold. As is, I'd send it to a referee because the idea is worth engaging, but the verdict should be major revision.","headline":"The adaptive reoptimization idea is sound, but the experiments never actually test adaptation—randomly shuffled static data is stationary, so the claimed gains likely just reflect better static order selection.","tokens_in":15021,"tokens_out":2117,"would_cite":false,"duration_ms":20736,"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":"On a four-table TPC-DS stream, re-optimizing probe order each cycle cut runtime by 31.2% on average versus a fixed order.","keywords":["multi-way stream join","probe order optimization","runtime adaptation","cost model","quadratic exponential smoothing","dpPick","stream processing","TPC-DS"],"falsifier":"Run dpPick on a synthetic stream where each cycle a different join becomes selective, or where selectivities shift abruptly, and compare its chosen order's measured cost with the predicted cost from the recursive formula. If the predicted and measured per-cycle costs have near-zero rank correlation, or if dpPick's runtime is worse than a fixed order for more than a small fraction of cycles, the central claim fails. A simpler version: sweep $\\alpha_q$ and $\\alpha_m$ over a grid on the same TPC-DS workload; if the reported average advantage over fixedOrder disappears or reverses for reasonable constant values, the model is miscalibrated.","tokens_in":14107,"feed_emoji":"⚡","tokens_out":9624,"duration_ms":75880,"temperature":0.7,"pith_summary":"Multi-way stream join operators combine several input streams into one result, and their efficiency depends on the order in which each incoming tuple probes the other streams. This order is usually fixed before execution, which works for static data but not for live streams whose arrival rates and match selectivities drift. The paper argues that the probe order should be re-optimized at runtime: the operator divides time into cycles, collects per-cycle statistics (match success rates, average match counts, key counts), predicts the next cycle with quadratic exponential smoothing, and then uses a recursive cost model with a memoized search, dpPick, to choose the lowest-cost probe order. On a four-table TPC-DS stream, the claimed effect is a 6.0%–53.7% runtime reduction relative to a fixed initial order in 22 of 24 orderings (average 31.2%), and better runtime than greedy and selectivity-first baselines in all 24. If true, this gives stream engines a way to stay efficient on unpredictable data without manual tuning.","feed_headline":"Probe-order reoptimization cuts stream join runtime by up to 54%","feed_subtitle":"On TPC-DS, dpPick re-picks the join order each cycle and beats fixed, greedy, and selectivity-first baselines.","key_machinery":"The load-bearing object is the probe-order optimizer dpPick combined with its cost model. dpPick treats a join as a graph whose edges are probe pairs $\\langle l_i, r_i\\rangle$, enumerates all complete probe sequences with depth-first search, and memoizes subsequence costs so each subsequence is evaluated once. Costs come from the recursive formula that adds a query cost $\\alpha_q f(\\kappa_{r_i})$ to a probabilistic match cost $\\gamma_{l_i}^{r_i}(\\alpha_m \\mu_{l_i}^{r_i} + C_{o_{i+1}})$; the statistics $\\gamma$, $\\mu$, and $\\kappa$ are collected per cycle and projected to the next cycle with quadratic exponential smoothing (Holt's linear trend for counts, damping trend for match rates). This machinery is what lets the operator adapt its probe order without prior knowledge of stream characteristics.","core_discovery":"The paper's central claim is that cyclic, statistics-driven reordering of probe pairs inside a multi-way stream join operator yields materially faster processing than any static or greedily chosen order. The operator stores one state backend per input stream; on each arriving tuple it iteratively probes the other backends in a chosen order, stopping early when a probe fails. dpPick takes a join graph, estimates each probe's query cost and match cost from predicted statistics, recursively evaluates every complete probe sequence with memoization, and installs the cheapest sequence for the next cycle. The cost estimate for a probe pair is $C_{o_i}\\approx \\alpha_q f(\\kappa_{r_i}) + \\gamma_{l_i}^{r_i}(\\alpha_m \\mu_{l_i}^{r_i} + C_{o_{i+1}})$, where $\\gamma$ is the predicted match-success probability, $\\mu$ the average number of matched records, and $\\kappa$ the predicted number of keys in the probed backend. The authors support the claim with TPC-DS experiments: dpPick beat a fixed initial order in 22 of 24 orderings (6.0%–53.7% lower runtime, 31.2% average), beat a cost-greedy baseline in all 24 (1.5%–42.8% lower, 20.4% average), and beat a selectivity-first baseline in all 24 (43.6%–75.3% lower, 56.1% average).","pith_inferences":["The experiments use one dataset and one four-table join shape; a natural test is whether the same gains appear on higher-degree joins or real-world streams with sudden regime changes, and whether the smoothing horizon needs to adapt.","The cost model constants $\\alpha_q$, $\\alpha_m$, $c$, and $m$ are left unspecified and uncalibrated, so the method's portability to other backends likely hinges on tuning them; a sensitivity analysis over a constant grid would reveal how robust the claimed gains are.","The full enumeration of probe sequences in dpPick could become a bottleneck when the join graph is dense; an extension that prunes by branch-and-bound would make the approach scale beyond small graphs.","A direct check of the prediction layer would be to compare predicted $\\gamma$, $\\mu$, and $\\kappa$ against observed values cycle by cycle; if prediction error is large, the runtime gains come from the cost model rather than the smoothing, which would change how one would improve the operator."],"forward_implications":["On the tested four-table TPC-DS join, changing probe order every cycle instead of keeping it fixed cuts runtime by 31.2% on average, with reductions up to 53.7%.","A cost model that includes both query cost and match cost outperforms either cost alone, by 19.5% and 6.3% on average respectively.","Predicting next-cycle statistics with quadratic exponential smoothing beats using the previous cycle's raw statistics in 22 of 24 orderings.","Optimization cycle periods of roughly 3–13 seconds and prediction history lengths near 60 give the best stability; much shorter or longer periods increase runtime.","Adaptive reordering removes the need to know stream statistics in advance, so the operator can track evolving workloads automatically."],"supporting_citations":[{"why":"Viglas, Naughton, and Burger's MJoin, the iterative-probing multi-way join operator whose low-selectivity probe order dpPick replaces; serves as the execution model and a baseline.","marker":"[6]"},{"why":"Gedik et al.'s GrubJoin, a windowed multi-way stream join with load shedding and low-selectivity-first ordering; baseline for the selectivity-first strategy.","marker":"[7]"},{"why":"Dossinger's MultiStream work, greedy cost-based probe order optimization for iterative probing; the direct baseline dpPick outperforms.","marker":"[8]"},{"why":"Viglas and Naughton's rate-based query optimization, which motivates using stream rates and selectivities rather than static cardinalities in cost estimation.","marker":"[20]"},{"why":"Babu et al.'s adaptive ordering of pipelined stream filters, which shows how to adapt filter or probe order at runtime by tracking selectivity; the adaptive idea dpPick builds on.","marker":"[28]"},{"why":"Chen et al.'s TPC-DS benchmark work, which supplies the dataset and query workload used in the experiments.","marker":"[36]"}],"fun_headline_variants":["Adaptive probe order slashes stream join runtime by 54%","dpPick reorders stream joins to cut time up to 54%","Runtime-optimized stream joins beat fixed and greedy orders","Cyclic re-picking of join order boosts streams by 54%"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument rests on the cost model ranking probe orders correctly; that ranking depends on uncalibrated constants in the cost formulas, and on the assumption that smoothed historical statistics predict the next cycle in streams that are changing.","fun_headline_variants_meta":{"raw":{"variants":["Adaptive probe order slashes stream join runtime by 54%","dpPick reorders stream joins to cut time up to 54%","Runtime-optimized stream joins beat fixed and greedy orders","Cyclic re-picking of join order boosts streams by 54%"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000253,"raw_usage":{"total_tokens":1639,"prompt_tokens":1091,"completion_tokens":548,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":707,"completion_tokens_details":{"reasoning_tokens":473}},"tokens_in":707,"tokens_out":548,"duration_ms":4781,"temperature":1.0,"reasoning_tokens":473,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T13:51:32.362390+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run dpPick on a synthetic stream where each cycle a different join becomes selective, or where selectivities shift abruptly, and compare its chosen order's measured cost with the predicted cost from the recursive formula. If the predicted and measured per-cycle costs have near-zero rank correlation, or if dpPick's runtime is worse than a fixed order for more than a small fraction of cycles, the central claim fails. A simpler version: sweep $\\alpha_q$ and $\\alpha_m$ over a grid on the same TPC-DS workload; if the reported average advantage over fixedOrder disappears or reverses for reasonable constant values, the model is miscalibrated.","supporting_citations":[{"cited_title":"Maximizing the output rate of multi-way join queries over streaming information sources","cited_arxiv_id":null,"evidence_quote":"Viglas, Naughton, and Burger's MJoin, the iterative-probing multi-way join operator whose low-selectivity probe order dpPick replaces; serves as the execution model and a baseline."},{"cited_title":"Grubjoin: An adaptive, multi-way, windowed stream join with time correlation- aware cpu load shedding","cited_arxiv_id":null,"evidence_quote":"Gedik et al.'s GrubJoin, a windowed multi-way stream join with load shedding and low-selectivity-first ordering; baseline for the selectivity-first strategy."},{"cited_title":"Optimizing Multi-Way Joins for Adaptive, Scale-out Stream Processing","cited_arxiv_id":null,"evidence_quote":"Dossinger's MultiStream work, greedy cost-based probe order optimization for iterative probing; the direct baseline dpPick outperforms."},{"cited_title":"Rate-based query optimization for streaming information sources","cited_arxiv_id":null,"evidence_quote":"Viglas and Naughton's rate-based query optimization, which motivates using stream rates and selectivities rather than static cardinalities in cost estimation."},{"cited_title":"Adaptive ordering of pipelined stream filters","cited_arxiv_id":null,"evidence_quote":"Babu et al.'s adaptive ordering of pipelined stream filters, which shows how to adapt filter or probe order at runtime by tracking selectivity; the adaptive idea dpPick builds on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Chen et al.'s TPC-DS benchmark work, which supplies the dataset and query workload used in the experiments."}],"review_version":1}