{"id":"00d41740-8dbe-4e3c-bef7-1fc40bee5e5b","arxiv_id":"2608.02213","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"The Desbordante C++ implementations of Spider and Faida run up to 5x and 8x faster than their Java Metanome counterparts on the tested datasets.","lead":"This paper describes C++ engineering optimizations—chunked buffering, SIMD hash combining, hash-table selection, and parallelization—for two inclusion-dependency discovery algorithms, Spider and Faida, implemented in the open-source Desbordante profiler. It measures up to 5x and 8x runtime reductions over the Java-based Metanome profiler.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Spider's max-value pruning rule (Sec V-B) is false as written, so the reported speedup may partly be an artifact of incomplete output; no output-set comparison is reported.","rationale":"The reader's weakest assumption identifies exactly the same load-bearing concern: the Spider max-value pruning rule is false as written, and no output-set comparison is provided to confirm that the optimized implementations preserve semantics. My independent reading of Sec V-B confirms the rule is stated as 'inclusion dependency A⊆B will not hold if the maximum value in A is less than the maximum value in B,' which is logically incorrect for set inclusion. This is not a matter of external consensus; it is an internal correctness risk. The paper's experimental design measures only runtime and memory, never result equality, so an incomplete Spider would still produce fast runtimes. The claim in Sec VI-D that 'we proved that each of our techniques are useful' is therefore not supported for Spider unless output completeness is checked. The Faida accuracy non-remeasurement is a smaller concern, since Faida is explicitly approximate and has prior validation. I give credit to the paper for the incremental ablation design, the open-source implementation, and the plausible engineering improvements, but the absence of a correctness comparison is a fixable yet essential gap. Since the reader's verdict is already CONDITIONAL and this concern supports that condition, no verdict adjustment is needed.","tokens_in":17257,"tokens_out":2332,"duration_ms":18096,"concrete_test":"Run the open-source Desbordante Spider and the Metanome Spider on all six datasets (CI_PH, ECOMM, FITBIT, HAIND, TPCH-1, TPCH-10) with the proposed max-value pruning both enabled and disabled, and diff the complete sets of discovered INDs. If the pruned run omits any IND found by Metanome or by the unpruned run, the pruning rule in Sec V-B is implemented as written, and the speedup claim is compromised. A single such mismatch is sufficient to confirm the concern.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim requires that the optimized Desbordante implementations discover the same inclusion dependencies as the original algorithms. For Spider, Sec V-B introduces a heuristic: 'inclusion dependency A⊆B will not hold if the maximum value in A is less than the maximum value in B.' This condition is not a valid exclusion rule. If A={1} and B={1,2}, then A⊆B holds, yet max(A)=1 < max(B)=2. The correct exclusion is max(A) > max(B), not max(A) < max(B). If the heuristic is implemented literally, it prunes valid INDs, reducing the candidate validation workload and inflating the measured speedup relative to Metanome. The paper does not report any comparison of discovered IND sets between Desbordante and Metanome, nor between Spider variants with and without this pruning rule, so such incompleteness would not be detected. This is the load-bearing weakness: the claimed 1.26–4.89x Spider speedup is only meaningful if the output is identical. The Faida claim also relies on an unverified assumption ('none of our techniques should impact it', Sec VI-B), but the Spider issue is more concrete and potentially more damaging.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper describes engineering optimizations for two inclusion dependency (IND) discovery algorithms, Spider and Faida, implemented in the Desbordante data profiler in C++. For Faida, the authors propose data buffering, SIMD vectorization of combined-hash computation, a specialized hash table, and parallelization. For Spider, they propose vector-based preprocessing and a max-value pruning heuristic. The implementations are benchmarked against the Java-based Metanome tool on six datasets, with reported speedups of 1.26–4.89x for Spider and 1.6–8.2x for Faida. The paper also provides an experimental comparison among incremental versions of the optimizations and reports memory consumption for Spider variants.","tokens_in":17593,"tokens_out":2537,"duration_ms":24121,"significance":"If the results are correct, the paper offers practically valuable engineering findings: it demonstrates that implementation details can yield order-of-magnitude improvements in IND discovery, and it contributes open-source C++ implementations in a widely used profiling framework. The reproducible benchmark setup and the incremental ablation of optimizations are strengths. However, the central claim — that the optimized implementations discover the same INDs as the original algorithms while being faster — is not directly verified. The Spider max-value pruning rule as stated is logically false, which raises a concrete correctness risk that must be resolved before the speedup numbers can be interpreted as sound.","major_comments":[{"comment":"The stated rule, 'inclusion dependency A⊆B will not hold if the maximum value in A is less than the maximum value in B,' is false. For example, A={1} and B={1,2} satisfies A⊆B, yet max(A)=1 < max(B)=2. The correct exclusion is max(A) > max(B). If this pruning rule is implemented as written, it will discard valid INDs and the reported 1.26–4.89x speedups may be inflated by incomplete output. The paper does not report any comparison between the IND sets discovered by Desbordante and Metanome, nor between Spider variants with and without the pruning rule. This must be fixed: either the rule must be corrected to max(A) > max(B), or the performance evaluation must be redone with the rule removed; in either case, an explicit output-set equivalence check is required.","section":"Sec. V-B, Spider max-value pruning"},{"comment":"The paper states that Faida's accuracy is not re-evaluated because 'none of our techniques should impact it.' This is an assumption, not a demonstrated property. The optimized implementation changes hash-table behavior, introduces parallelism (which can affect insertion order and, with mutex-based structures, locking patterns), and modifies the data-filling routine. These changes should not affect the set of discovered dependencies, but the paper provides no evidence. An output comparison (e.g., precision and recall against the Metanome Faida results, at least on the smaller datasets) is needed to confirm that the engineering changes preserve the approximate algorithm's semantics.","section":"Sec. VI-B, Faida accuracy assertion"},{"comment":"For FITBIT, only unary results are reported because both implementations run out of memory during n-ary candidate generation. This means the headline 'up to 8x' Faida speedup does not apply to the n-ary case on this dataset, and the n-ary behavior of the optimized implementation remains untested. The paper should either include a discussion of this limitation in the main claims or restrict the strongest speedup statements to the settings where full results were obtained.","section":"Sec. VI-B, Table III and IV"},{"comment":"Run times are averaged over 5 runs, but no standard deviations, confidence intervals, or statistical tests are reported. Since performance measurements can be noisy even with cache clearing, some measure of variance is needed to support the claim that each incremental optimization gives a 'positive result.' This is not a blocking issue for the overall engineering contribution, but it would strengthen the paper.","section":"Sec. VI, experimental methodology"}],"minor_comments":[{"comment":"Typo: 'One cay say' should be 'One may say.'","section":"Sec. II, Definition 1"},{"comment":"The text says the inverted index is represented with 'std::map<int, std::set<int>>' after earlier describing the use of the emhash family. Please clarify which data structure is used for the production implementation and whether std::map or an unordered/hash map is meant.","section":"Sec. V-A, inverted index description"},{"comment":"The figure labels use 'VECSTR' while the text consistently uses 'VECSTR' and also occasionally 'VECTORSTR' in Sec. VI-C. Please standardize.","section":"Sec. VI-C, Fig. 2 and 3"},{"comment":"The phrase 'we proved that each of our techniques are useful' overstates what experiments show; experiments demonstrate positive results on the tested datasets, not proof in the mathematical sense. Consider rewording.","section":"Sec. VI-D, conclusion"},{"comment":"Minor spacing and capitalization issues: 'A VX2' should be 'AVX2', and 'has to be carefully taken into account' could be tightened.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper is a solid engineering study, but the Spider pruning error is a correctness issue that invalidates the headline speedup claims unless fixed. The lack of any output-equivalence verification is the key methodological gap. I would be willing to accept after the authors correct the pruning rule (or remove it), demonstrate output equivalence (for Spider exact equality; for Faida at least precision/recall against the Metanome implementation on the non-OOM datasets), and add variance information to the timing results. These are within scope of a revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core result is plausible and useful: the Desbordante C++ implementations of Spider and Faida are measured to be 1.26–4.89x and 1.6–8.2x faster than Metanome on several real and synthetic datasets, and the incremental ablation gives each technique its own number. That is a solid contribution to the data-profiling community, and the open-source angle makes it more than an academic exercise. The writeup is honest about what is optimized and what is not, and the memory-reduction story for Spider is convincing.\n\nThe soft spots are real but narrower than the stress test suggests. The false pruning rule in Sec. V-B is exactly as bad as stated: max(A) < max(B) does not rule out A⊆B (A={1}, B={1,2} is a counterexample). That is a genuine error in the paper. But it is not yet clear that the buggy rule is part of the benchmarked Spider variants. The paragraph reads like a possible extra optimization, and the measured implementations are distinguished by their preprocessing strategy, not by this check. The paper never says explicitly whether the max-value check was enabled in the experiments. If it was, the speedups could indeed be inflated by incomplete output; if it was not, the error is text-only. Either way, the authors need to correct the condition and — more importantly — report output-set comparisons between their implementations and the original ones. They claim semantics are preserved for Spider and unchanged for Faida, but never verify it. That is the load-bearing missing experiment, and it applies to all the speedup claims.\n\nMinor issues: no error bars or variance across the five runs, and no pinned commit or scripts for exact reproduction. The FITBIT n-ary OOM is understandable and disclosed. The Faida accuracy non-remeasurement is a bit hand-wavy ('none of our techniques should impact it') but defensible given the algorithm logic.\n\nWho is this for? Anyone implementing or benchmarking dependency-discovery algorithms, especially in C++ or with an eye on engineering-level speedups. It is not a theoretical paper and does not need to be. It deserves a serious referee: the experiments are reproducible in spirit, the speedups are large enough to matter, and the flaws are fixable with an output-equivalence test and a corrected heuristic. I would engage with it and recommend the editor send it to review.","headline":"A credible systems paper with real speedups and a solid ablation, but it states a false Spider pruning rule and never verifies output equivalence, so the correctness claims need fixing before it can be fully trusted.","tokens_in":18011,"tokens_out":1646,"would_cite":true,"duration_ms":14349,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that a C++ reimplementation of two inclusion-dependency discovery algorithms, Spider and Faida, using buffering, SIMD, hash-table selection, and parallelization, runs up to 5x and 8x faster than the corresponding Metanome","keywords":["inclusion dependency","foreign key discovery","data profiling","algorithm engineering","parallelization","SIMD vectorization","hash table selection","Spider and Faida"],"falsifier":"Run the optimized and reference implementations on the same datasets and compare their complete sets of discovered INDs; any valid dependency missing from the optimized Spider output—such as A={1}⊆B={1,2} under the max-value rule as printed—would show that the speedup is partly an artifact. A simpler check: correct the rule to max(A)>max(B) and remeasure.","tokens_in":17186,"feed_emoji":"⚡","tokens_out":5829,"duration_ms":51474,"temperature":0.7,"pith_summary":"Inclusion dependencies (INDs) are database constraints saying that every value in one column set also appears in another column set; they are the standard signal for possible foreign-key references. The paper's claim is that the real bottleneck in automatic IND discovery is engineering, not just algorithm design: the Java-based reference implementations leave large speedups unused. By reimplementing two IND algorithms—the classic Spider and the approximate Faida—in C++, and applying chunked buffering, vectorized hash computation, better hash tables, and parallel preprocessing, the authors report up to 5x faster Spider and up to 8x faster Faida than the corresponding Metanome implementations. Each Faida optimization is shown to help on its own, and Spider's gains come mainly from replacing single-threaded set-based preprocessing with parallel, disk-aware vector sorting and deduplication. The intended takeaway is that careful implementation choices can make existing IND discovery algorithms practical at larger scale.","feed_headline":"Up to 8x faster inclusion-dependency discovery via C++ engineering","feed_subtitle":"Careful buffering, SIMD hashing, and parallel sorting turn two classic IND algorithms into practical tools.","key_machinery":"The load-bearing objects are the two algorithms: Spider, which discovers unary INDs by sorting each column to disk, merging iterators in a min-heap, and intersecting candidate lists as equal values are seen; and Faida, which discovers unary and n-ary INDs approximately by hashing columns, building a sampled inverted index plus HyperLogLog sketches, and validating Apriori-generated candidates through XOR/ROTL-combined hash tuples. The paper's machinery is the engineering around these: chunked buffering that turns row-at-a-time filling into array-at-a-time processing, a specialized integer hash table for index lookups, AVX2 emulation of vectorized rotate-and-XOR for four hashes per instruction","core_discovery":"The paper's central claim is that substantial performance gains in IND discovery come from implementation techniques rather than new algorithmic ideas. For Faida, it identifies data-structure filling as the dominant cost and shows that chunked row buffering, a specialized integer hash table, AVX2 vectorized ROTL/XOR hashing, and parallel filling each reduce runtime, with the combined parallel version reaching 1.6–8.2x over Metanome across six datasets. For Spider, it replaces the original per-column, TreeSet-based, single-threaded preprocessing with one-pass chunked reading, parallel vector sorting and deduplication, and compact value keys (string_view or offset/length pairs), yielding 1.26–","pith_inferences":[],"forward_implications":["Spider-related algorithms such as S-indd and S-indd++ can likely be sped up by the same vector-based parallel preprocessing techniques.","Faida-style algorithms can adopt the optimizations incrementally, since each of hash-table selection, buffering, SIMD, and parallelization pays off independently.","Practical IND discovery on large tables becomes more feasible without changing the underlying algorithm, because the speedups come from engineering rather than new algorithmic ideas.","The memory footprint of Spider preprocessing can be traded against runtime by adjusting the available memory cap, as the vector-based implementations demonstrate.","If Faida's approximate semantics are preserved, users get the same complete-with-false-positives output in a fraction of the time.","The maximum-value pruning rule introduced for Spider, as written, is logically inverted; the valid exclusion is max(A) > max(B), not max(A) < max(B)."],"fun_headline_variants":["C++ engineering cuts IND discovery time up to 8x","Implementation tricks beat algorithms for IND discovery","Parallel C++ speeds up dependency discovery 8x","SIMD and parallel sorting slash inclusion-dependency search","Desbordante: 8x faster IND discovery via careful coding"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The reported speedups are only meaningful if the optimized implementations discover exactly the same inclusion dependencies as the original algorithms, but the paper does not verify that, and one new Spider pruning rule is stated backwards, which would drop valid dependencies.","fun_headline_variants_meta":{"raw":{"variants":["C++ engineering cuts IND discovery time up to 8x","Implementation tricks beat algorithms for IND discovery","Parallel C++ speeds up dependency discovery 8x","SIMD and parallel sorting slash inclusion-dependency search","Desbordante: 8x faster IND discovery via careful coding"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000966,"raw_usage":{"total_tokens":3980,"prompt_tokens":812,"completion_tokens":3168,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":556,"completion_tokens_details":{"reasoning_tokens":3089}},"tokens_in":556,"tokens_out":3168,"duration_ms":17377,"temperature":1.0,"reasoning_tokens":3089,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T11:19:57.462786+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the optimized and reference implementations on the same datasets and compare their complete sets of discovered INDs; any valid dependency missing from the optimized Spider output—such as A={1}⊆B={1,2} under the max-value rule as printed—would show that the speedup is partly an artifact. A simpler check: correct the rule to max(A)>max(B) and remeasure.","supporting_citations":[],"review_version":1}