{"id":"d439d1e1-4ebd-4ffb-9a9d-f492f0f8defd","arxiv_id":"2411.13245","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"On AsterixDB, hash-based group-by is faster for small in-memory workloads and few groups, while sort-based group-by is faster at high group cardinality and under memory pressure.","lead":"This paper compares two ways databases run group-by aggregation, sorting versus hash tables, on the Apache AsterixDB system. It finds hash-based grouping wins for small in-memory workloads, while sort-based grouping wins when group counts are high or memory is tight.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed sort/hash crossover is likely confounded by AsterixDB's open data type, which disables normalized-key sorting and forces byte-wise comparison of full records.","rationale":"Good-faith reading: the paper is a careful single-system study with plausible internal mechanisms (spill volume, sort comparisons). I am not objecting to the measurements. The objection is to the inference from these measurements to the general claim in the abstract and conclusion. The text itself supplies the evidence for the confound: Section 3.1 says open types disable normalized-key sorting, and Expr. 2 and Expr. 4 use open data. The low-group-count result is exactly where that implementation detail matters most, because sort-based GBA sorts the full input before aggregating and thus cannot exploit the small number of groups to shrink its working set, while hash-based GBA naturally can. This makes the headline \"hash preferable for small datasets/low group counts\" a likely artifact of the chosen datatype and memory budget, not a robust property of the algorithm families. The reader's conditional verdict already flags representativeness; my check sharpens it into a falsifiable test. Verdict remains CONDITIONAL: the paper's measurements can be trusted, but its generalizable conclusions need either closed-type re-runs or a second system before acceptance as general guidance.","tokens_in":11575,"tokens_out":3830,"duration_ms":41555,"concrete_test":"Re-run Expr. 2 and Expr. 4 with the grouping attribute declared in a closed datatype so AsterixDB sorts normalized keys instead of full records, keeping all other settings identical. If the hash advantage at 10 groups shrinks or reverses, the \"small datasets/low group counts\" conclusion is an artifact of open-type sorting. Separately, repeat both experiments with per-partition GBA memory raised from 64 MB to 256 MB; if the crossover group count in Figure 13 moves by more than a factor of 10, the fixed budget is a confound. Optionally repeat on PostgreSQL with work_mem scaled analogously to test cross-system generality.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central, generalizable conclusion (\"hash preferable for small datasets or low group counts, sort better under high cardinality/memory pressure\") depends on experiments whose sort-based operator runs without its optimized comparison path. Section 3.1 states: \"However, when using open types, the actual records are sorted rather than the normalized representation.\" Expr. 2 uses an open data type, Expr. 4 inherits that setup, and Expr. 3.4.2 explicitly classifies the dataset as Open to disable normalized keys. For small group counts, the sort-based GBA therefore sorts full records before aggregating, while the hash-based GBA maintains only aggregate entries; the hash method's working set shrinks with group count and the sort method's does not. This is an implementation property, not a fundamental property of sort-versus-hash algorithm families. The crossover in Figures 6 and 13 may thus be driven by the open-type record representation plus the fixed 64 MB per-partition budget, not by the algorithms themselves. The high-cardinality result is less suspect but shares the same single-system, single-plan confound. Because the abstract states the crossover as general guidance, the load-bearing assumption that the specific AsterixDB implementations under open types represent the general families is not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper reports a focused empirical comparison of sort-based and hash-based group-by-aggregate (GBA) execution in Apache AsterixDB. It uses TPC-H and TPC-DS workloads plus controlled synthetic data from a modified Wisconsin benchmark to measure execution time, disk spilling, and sort-comparison counts across data size, group cardinality, aggregation type, and data type. The central claim is a crossover: hash-based GBA is preferable for small datasets or low group counts, while sort-based GBA performs better under high group cardinality or memory pressure. The paper is explicitly an AsterixDB study, but Section 2.2 asserts that the findings are extendable to other similar systems.","tokens_in":11752,"tokens_out":7549,"duration_ms":81521,"significance":"If taken as a statement about AsterixDB's two GBA implementations under the tested configuration, this is a useful and mostly well-documented empirical datapoint: it reports spill-volume and comparison-count evidence for the proposed mechanism, uses both realistic TPC queries and controlled synthetic data, discards the first of 11 runs, and describes the cluster and memory budget concretely. The use of an author-created data generator is not itself circular because the generator does not encode the outcome being measured. However, the paper's abstract and conclusion generalize well beyond what the experiments establish. The main confound—the sort-based operator runs without normalized-key sorting on open-type records—is a load-bearing threat to the central crossover claim, and the single-system, single-plan design does not support the stated generality. The study is therefore a solid AsterixDB-specific experiment but needs either an additional closed-type control or substantially narrowed claims before it can support the broad guidance in the abstract.","major_comments":[{"comment":"The central crossover result is measured under an implementation choice that asymmetrically disadvantages the sort-based operator. Section 3.1 states that \"when using open types, the actual records are sorted rather than the normalized representation,\" and Section 4.3 states that Expr. 2's Wisconsin datasets use AsterixDB's open data type; Expr. 4 \"remains consistent with earlier experiments\" and appears to inherit the same setting. Section 4.4.2 explicitly classifies its dataset as Open to disable normalized keys. With open types, the sort-based GBA performs byte-wise, full-record comparisons while the hash-based GBA keeps only an aggregate entry per group. Consequently, in the low-cardinality experiments (10 groups), the hash operator's memory footprint collapses to about ten entries per partition while the sort operator's working set remains the full record stream, so the observed hash advantage is at least partly an artifact of this representation asymmetry rather than a general property of hash versus sort grouping. The paper must either rerun the controlled experiments with a closed data type so that normalized-key sorting is enabled, or explicitly restrict the conclusions to open-type, AsterixDB-specific execution. As written, the abstract's general guidance is not supported.","section":"Section 3.1, Sections 4.3-4.5"},{"comment":"The executive summary overstates and internally mismatches the experimental results. The abstract says \"sort-based methods excel in scenarios with large datasets,\" but Expr. 2 (Figure 6) shows the opposite for every tested dataset size from 2 GB to 64 GB when the group count is 10; the actual crossover in Section 4.5 is about group cardinality, not dataset size per se. The paper's own conclusion correctly conditions on \"high-cardinality or memory-limited scenarios,\" which is a different statement from the abstract's \"large datasets\" clause. Additionally, memory pressure is not treated as an independent variable: Section 4.1 fixes the GBA memory budget at 64 MB per data partition for all experiments, so the paper demonstrates only that sort outperforms hash under one memory setting, not that the ranking is caused by memory pressure. The abstract and Section 6 should be rewritten to state the conditional result actually shown: for AsterixDB with open-type records and a fixed 64 MB per-partition budget, hash wins at low group cardinality and sort wins at high group cardinality.","section":"Abstract and Section 6"},{"comment":"The claim in Section 2.2 that the findings are \"extendable to other systems\" is not tested and is too strong for the evidence. All experiments use one execution plan (local aggregation, hash-partition exchange, global aggregation, as shown in Figure 3), one operator memory budget, one record representation (open ADM), and one DBMS implementation of each algorithm family. A second system, a second plan, or even a sensitivity analysis over memory budgets and data types would be needed to justify cross-system generalization. I am not requiring a full multi-system study, but the scope of the claim should match the evidence: without such additional evidence, the conclusions should be framed as \"in AsterixDB under these settings,\" not as general guidance for hash- versus sort-based GBA.","section":"Section 2.2"}],"minor_comments":[{"comment":"The paper does not state the AsterixDB version used; a version number would improve reproducibility.","section":"Section 4.1"},{"comment":"It should be defined explicitly what \"amount of data spilled\" counts: raw sort-run spilling, aggregated-output spilling, or both. The claim that sort-based GBA spills little with 10 groups is surprising if full records are sorted, and a precise definition would clarify the mechanism.","section":"Section 4.3 and Figure 7"},{"comment":"The paper reports only the average of the last 10 runs, with no variance information or per-trial data. A standard deviation or raw timing table would help assess the reliability of the smaller differences, especially in the TPC experiments of Figure 5.","section":"Section 4.3 and Figure 6"},{"comment":"There is a typo in the text: \"respectively, in Figures1111-(a), -(b), and -(c)\" should be \"Figure 11-(a), -(b), and -(c).\"","section":"Section 4.4.2"}],"recommendation":"major_revision","confidential_remarks":"The paper fits an experiments-track venue, and the controlled AsterixDB study is a reasonable contribution if the claims are scoped correctly. The main revision pressure should be on the open-type confound: either run a closed-type/normalized-key condition or narrow the abstract and conclusion to AsterixDB with open-type records. The self-citation to the Wisconsin JSON generator is understandable because the generator is the basis of the controlled workload; I do not see a citation-pattern problem."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth a look if you care about AsterixDB or about how system-specific sort-vs-hash crossover claims actually hold up. The paper is an honest, carefully run empirical study: sort- and hash-based GBA on AsterixDB with controlled data sizes, group counts, and data types, plus spill and comparison counters that back the mechanism. The headline crossover is real for this system: hash wins for few groups and in-memory fits, sort wins at high cardinality and under memory pressure. But the crossover is not new—it's essentially a re-measurement of the tradeoff in Graefe et al. 1994 and Do et al. 2022—and the new value is the specific measurements: the hash table eating roughly a third of operator memory, the spill behaviors, the sort-comparison counts. Those are useful data points.\n\nThe execution is decent: 11 runs, averaging last 10, cache-clearing scans, memory clamped on nodes. The high-cardinality result in Expr 4 looks robust—hash spills badly with 10^6 groups while sort degrades more gradually.\n\nThe soft spots are real. The biggest is the open-type confound flagged in the stress-test, and I think it lands. Expr 2 loads data as open type and Section 3.1 says open types sort actual records rather than normalized keys; Expr 4 inherits that. For small group counts, sort-based sorts full records while hash-based keeps only aggregate entries, so the hash working set shrinks with group count and the sort working set doesn't. That means the crossover in Figures 6 and 13 is partly an implementation property of AsterixDB's open-data path, not an inherent property of sorting vs. hashing. The paper doesn't test closed types, so the general claim in the abstract is over-broad. Also missing: error bars, raw data, code/scripts, AsterixDB version, and any test on a second system. The extendability claim in Section 2.2 is asserted, not demonstrated.\n\nThe paper is still worth a serious referee. It's a concrete, reproducible-in-principle case study that gives AsterixDB users a practical rule of thumb, and the mechanism data are valuable. I'd send it to review with the expectation that the authors tighten the claims, either test closed-type data or explicitly scope the conclusion to open-data systems, and ship the artifacts. My verdict would be conditional, not reject.","headline":"Honest, well-run AsterixDB experiments; the crossover is real for this system but not new, and the open-type normalization issue muddies the small-group story.","tokens_in":12353,"tokens_out":3953,"would_cite":false,"duration_ms":40245,"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":"Hash group-by wins on small data, sort on large data","keywords":["group-by-aggregate","hash-based aggregation","sort-based aggregation","spilling","group cardinality","AsterixDB","empirical study","query optimization"],"falsifier":"Run the same Wisconsin-style group-by experiments on another parallel DBMS with an equivalent per-operator memory budget and the same open-record layout; if the crossover point (where sort starts beating hash) moves by more than a small factor or disappears, the general trend claimed here is AsterixDB-specific rather than intrinsic to the algorithm families. Alternatively, vary the per-partition budget from 64 MB to 1 GB and observe whether hash-based remains competitive at high group counts once memory pressure is relieved.","tokens_in":11308,"feed_emoji":"📊","tokens_out":6254,"duration_ms":57969,"temperature":0.7,"pith_summary":"This paper reports a controlled, head-to-head comparison of hash-based versus sort-based group-by-aggregate execution on Apache AsterixDB, varying dataset size, group count, data type, and string characteristics. The central claim is that the two methods have opposite sweet spots: hash-based aggregation is preferable when datasets are small or group counts are low (because it stays in memory and avoids sorting), while sort-based aggregation wins for large datasets, high group cardinality, and memory-limited situations (because it handles spilling more predictably). The authors argue their controlled Wisconsin-style experiments isolate the GBA operator better than TPC-H and TPC-DS, whose additional operators mask its behavior. If the claim holds, query optimizers should pick a group-by algorithm based on estimated group cardinality and memory pressure, not just on dataset size.","feed_headline":"Hash group-by wins on small data, sort on large data","feed_subtitle":"Controlled AsterixDB experiments map where each group-by-aggregate method beats the other under a fixed memory budget.","key_machinery":"The load-bearing mechanism is the interaction between a fixed per-partition operator memory budget (64 MB per data partition) and the number of distinct group keys. In AsterixDB, sort-based GBA uses an external merge sort with normalized keys and a record pointer array for comparison-based ordering, then aggregates in a merge pass; hash-based GBA uses a partition table plus a hash table, spilling partitions to disk recursively when the aggregate state exceeds the budget. When group cardinality is low, the hash table fits in memory and avoids all sorting; when cardinality is high, hash-table overhead (roughly a third of the memory) forces earlier and heavier spilling, while the sort-based method spills in a more controlled merge order. This spilling-versus-comparison trade-off is what the paper measures in its execution-time, spilling, and sort-comparison plots.","core_discovery":"On its own terms, the paper establishes a performance crossover: with a fixed per-partition memory budget of 64 MB, hash-based group-by is faster than sort-based when the input fits in memory or produces few groups (e.g., ten groups), because it performs no sorting and spills almost nothing. As group cardinality rises toward one million, the hash table overflows the memory budget, its spilling rises sharply, and its execution time climbs steeply, while sort-based group-by degrades more gradually and ends up faster. The same mechanism explains the string findings: hash-based suffers from the extra memory taken by hash-table overhead when keys are unique, while sort-based slows dramatically when keys share long common prefixes, because character-by-character comparisons multiply. The paper also reports that aggregate type (COUNT vs. SUM) does not change the ranking, and that on the complex TPC workloads the two methods are often comparable because the GBA operator receives relatively little data after filtering and joins.","pith_inferences":["The same crossover logic should apply on other shared-nothing systems, but the memory-budget threshold is likely system-specific; the qualitative result (hash prefers low cardinality, sort prefers high cardinality and tight memory) is the transferable part.","An adaptive operator could start with hashing and switch to sorting when its spill rate crosses a threshold, effectively tracking the crossover at runtime without query-plan statistics.","The paper's open-data-type setup is a conservative case for sorting (it disables normalized-key comparison); on closed datasets with fixed-width fields, sort-based GBA may close part of the low-cardinality gap.","The observed sharp degradation of hash-based GBA at one million groups suggests a practical ceiling heuristic: if estimated groups exceed a memory-derived bound, route the query to sort."],"forward_implications":["Query optimizers that estimate group cardinality can choose hash-based GBA for low-cardinality groupings and sort-based GBA for high-cardinality or memory-limited ones, avoiding spills.","When a downstream operator needs sorted output, sort-based GBA can serve double duty, which the paper identifies as a reason it stays competitive on TPC-H queries 9 and 13.","The performance gap between the two methods widens with open-typed, long, or prefix-similar string keys, making data type a first-class input to operator choice.","The near-identical results for COUNT and SUM suggest aggregate function type matters less for choosing between the two approaches than group cardinality and memory pressure.","Databases that expose memory-budget hints can use these results to set or advise operator memory so that hash aggregation avoids spill regimes."],"supporting_citations":[{"why":"Provides the TPC-DS analytical workload used in Experiment 1 to compare the two approaches under realistic complex queries.","marker":"[2]"},{"why":"Provides the TPC-H analytical workload used in Experiment 1, including the high-volume Query 18 case where sort-based GBA wins.","marker":"[3]"},{"why":"Supplies the Wisconsin data generator used to create controlled datasets with tunable group counts, string lengths, and distributions for Experiments 2-4.","marker":"[4]"},{"why":"Describes the AsterixDB system architecture, including its shared-nothing design and parallel operator execution, which forms the experimental platform.","marker":"[5]"},{"why":"Documents that sort-based GBA is the default in AsterixDB, hash-based GBA is selected via a hint, and open data types and memory budget parameters are configured per operator.","marker":"[7]"},{"why":"Explains normalized-key sorting and record pointer arrays, the mechanisms behind the sort-based GBA implementation whose comparison costs are central to the crossover.","marker":"[14]"},{"why":"The modified Wisconsin benchmark whose JSON generator is the basis for the controlled experiments isolating GBA operator behavior.","marker":"[19]"},{"why":"Describes the hash table and partition structure and the memory management and spilling behavior of AsterixDB that underlie the hash-based GBA results.","marker":"[21]"}],"fun_headline_variants":["With 64MB budget, hash wins small groups, sort wins large","Group-by crossover: hash wins few groups, sort wins many","Hash beats sort for few groups, loses for many under 64MB","Memory budget decides group-by winner: hash for few, sort for many"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The experiments assume the AsterixDB sort and hash group-by implementations are representative of the general algorithm families, and that the fixed 64 MB per-partition memory budget, the open data type, and the hash-partition exchange plan do not secretly determine the crossover.","fun_headline_variants_meta":{"raw":{"variants":["With 64MB budget, hash wins small groups, sort wins large","Group-by crossover: hash wins few groups, sort wins many","Hash beats sort for few groups, loses for many under 64MB","Memory budget decides group-by winner: hash for few, sort for many"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000928,"raw_usage":{"total_tokens":3975,"prompt_tokens":944,"completion_tokens":3031,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":560,"completion_tokens_details":{"reasoning_tokens":2954}},"tokens_in":560,"tokens_out":3031,"duration_ms":22042,"temperature":1.0,"reasoning_tokens":2954,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T16:39:37.888942+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the same Wisconsin-style group-by experiments on another parallel DBMS with an equivalent per-operator memory budget and the same open-record layout; if the crossover point (where sort starts beating hash) moves by more than a small factor or disappears, the general trend claimed here is AsterixDB-specific rather than intrinsic to the algorithm families. Alternatively, vary the per-partition budget from 64 MB to 1 GB and observe whether hash-based remains competitive at high group counts once memory pressure is relieved.","supporting_citations":[{"cited_title":"https://www.tpc.org/tpcds/","cited_arxiv_id":null,"evidence_quote":"Provides the TPC-DS analytical workload used in Experiment 1 to compare the two approaches under realistic complex queries."},{"cited_title":"https://www.tpc.org/tpch/","cited_arxiv_id":null,"evidence_quote":"Provides the TPC-H analytical workload used in Experiment 1, including the high-volume Query 18 case where sort-based GBA wins."},{"cited_title":"https://github.com/shivajah/JSON- Wisconsin-Data-Generator","cited_arxiv_id":null,"evidence_quote":"Supplies the Wisconsin data generator used to create controlled datasets with tunable group counts, string lengths, and distributions for Experiments 2-4."},{"cited_title":"Borkar, Yingyi Bu, Michael J","cited_arxiv_id":null,"evidence_quote":"Describes the AsterixDB system architecture, including its shared-nothing design and parallel operator execution, which forms the experimental platform."},{"cited_title":"AsterixDB SQL++ User Manual , 2023","cited_arxiv_id":null,"evidence_quote":"Documents that sort-based GBA is the default in AsterixDB, hash-based GBA is selected via a hint, and open data types and memory budget parameters are configured per operator."},{"cited_title":"Implementing sorting in database systems","cited_arxiv_id":null,"evidence_quote":"Explains normalized-key sorting and record pointer arrays, the mechanisms behind the sort-based GBA implementation whose comparison costs are central to the crossover."},{"cited_title":"Wisconsin benchmark data generator: To JSON and beyond","cited_arxiv_id":null,"evidence_quote":"The modified Wisconsin benchmark whose JSON generator is the basis for the controlled experiments isolating GBA operator behavior."},{"cited_title":"Borkar, Yingyi Bu, Michael J","cited_arxiv_id":null,"evidence_quote":"Describes the hash table and partition structure and the memory management and spilling behavior of AsterixDB that underlie the hash-based GBA results."}],"review_version":1}