Pith. sign in

REVIEW 4 major objections 5 minor 33 references

Fast Discovery of Inclusion Dependencies with Desbordante

T0 review · 4 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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

desk verdict 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. read the letter →

arxiv 2608.02213 v1 pith:RQCFGN5T submitted 2026-08-03 cs.DB cs.AIcs.DCcs.LGcs.PF

Alexander Smirnov , Anton Chizhov , Ilya Shchuckin , Nikita Bobrov , George Chernishev This is my paper · ORCID
classification cs.DBcs.AIcs.DCcs.LGcs.PF
keywords inclusiondependencyforeignkeydiscoverydataprofilingalgorithmengineeringparallelizationSIMDvectorizationhashtableselectionSpiderandFaida
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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

What would settle it

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.

Watch

Extended reading notes

Core claim

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–

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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).
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

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.

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 (4)
  1. [Sec. V-B, Spider max-value pruning] 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.
  2. [Sec. VI-B, Faida accuracy assertion] 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.
  3. [Sec. VI-B, Table III and IV] 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.
  4. [Sec. VI, experimental methodology] 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.
minor comments (5)
  1. [Sec. II, Definition 1] Typo: 'One cay say' should be 'One may say.'
  2. [Sec. V-A, inverted index description] 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.
  3. [Sec. VI-C, Fig. 2 and 3] The figure labels use 'VECSTR' while the text consistently uses 'VECSTR' and also occasionally 'VECTORSTR' in Sec. VI-C. Please standardize.
  4. [Sec. VI-D, conclusion] 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.
  5. [Throughout] Minor spacing and capitalization issues: 'A VX2' should be 'AVX2', and 'has to be carefully taken into account' could be tightened.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the speedup claims are direct benchmark comparisons against Metanome; the main issues are correctness/evidence gaps, not circular derivation.

full rationale

The paper's central claims are direct benchmark measurements of C++ implementations versus Metanome Java implementations. No quantity is fitted to data and then reported as a prediction, and no parameter is defined in terms of the target result. The authors state that they 'carefully converted the code to C++, preserving the initial logic of programs' (Sec. II), so the reported speedups are comparisons of implementations, not derivations from the outputs or from the paper's own definitions. Self-citations to Desbordante papers [24] and [32] describe the tool and prior experiments, but they do not supply the measured runtimes or the optimization results, so they are not load-bearing for the central claims. The main validity concerns are non-circular: (1) the Spider max-value pruning rule in Sec. V-B is false as written ('inclusion dependency A⊆B will not hold if the maximum value in A is less than the maximum value in B'), which would prune valid INDs if implemented literally, and no output-set comparison with Metanome is reported; (2) Sec. VI-B does not re-evaluate Faida accuracy, relying on earlier works [11], [25] and the assertion that 'none of our techniques should impact it.' These are correctness and evidence gaps, not circularity: the paper does not use those assumptions to define or derive the measured speedups. There is no self-definitional step, no fitted input called a prediction, no load-bearing self-citation chain, no imported uniqueness theorem, and no renaming of a known result as a derivation. The manuscript even lists relevant threats to validity in Sec. VII, further indicating that the limitations are acknowledged empirically rather than concealed by construction. Overall, the derivation chain is not circular.

Assumptions & free parameters 5 free parameters · 4 assumptions · 0 invented entities

The central claims rely on no new theoretical entities; the only new artifacts are implementation data structures (lock-free bit vectors, reference-based vector keys), which are engineering choices rather than postulated entities. The headline speedups are conditional on several algorithm/tuning constants inherited from prior work or chosen by the authors.

free parameters (5)
  • Faida sample size n = 500
    Chosen from the original Faida paper; controls the inverted-index sample and affects running time and false-positive behavior.
  • HyperLogLog accuracy = 0.1%
    Chosen from the original Faida paper; controls memory use and cardinality-estimation accuracy; not varied in experiments.
  • Spider memory cap = 22 GB in main experiment; 256MB–4GB in memory-scaling experiment
    Chosen by the authors; determines when chunks are flushed to disk, directly affecting run time and memory.
  • Thread count = 16
    Maximum threads of the benchmark machine; Spider and Faida parallel speedups are conditional on this.
  • VECPAIR chunk-size cap = 4 GB
    Implementation limit because offsets are stored as uint; forces splitting of larger files and affects the >4GB recommendation.
assumptions (4)
  • domain assumption IND validity reduces to set containment, |s(Y)|=|s(X)∪s(Y)|
    Used in Faida validation (Sec IV-A3); inherited from the original algorithm, not proved in this paper.
  • domain assumption Faida's approximate output (complete with false positives) is acceptable; hash collisions and HLL error only add false positives and are not re-measured here
    The paper states accuracy was studied earlier and is not evaluated (Sec VI-B), so speedups are decoupled from quality.
  • domain assumption NULLs are equal to each other and unequal to all non-NULL values
    Adopted as 'well-known policy' in Sec VI-A; affects sorted and deduplicated column files.
  • ad hoc to paper The max-value pruning rule is correct (A⊆B excluded when max(A)<max(B))
    Stated in Sec V-B with no proof; it is false as written, so any implementation using it would be unsound.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fast Discovery of Inclusion Dependencies with Desbordante." pith.science (2026). https://pith.science/paper/RQCFGN5T

@misc{pith2026260802213,
  author       = {Pith},
  title        = {Pith review of: Fast Discovery of Inclusion Dependencies with Desbordante},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RQCFGN5T}},
  note         = {Machine review of arXiv:2608.02213}
}
read the original abstract

Inclusion dependency is a relation between attributes of tables that indicates possible Primary Key-Foreign Key references. Automatic discovery of inclusion dependencies is a relevant problem for both academic and industrial communities. The core concern for this problem is the efficiency of discovery process, since it is a computationally expensive task. However, existing studies only address the algorithmic side, while leaving out the implementation aspect. At the same time, engineering details are at least as important as the algorithmic ones for achieving good performance. In this paper, we describe techniques for efficient implementation of two algorithms for discovery of inclusion dependencies - Spider and Faida. The first one is a classic algorithm whose ideas lie in the foundation of many other inclusion dependency discovery algorithms. We propose an efficient parallelization technique, which greatly speeds up the algorithm while simultaneously reducing its memory consumption. The second one is the state-of-the-art approximate algorithm, which we approach by applying four types of optimizations: data buffering, SIMD-enabled execution, careful hash-table selection and parallelization. In order to experimentally evaluate our techniques, we have implemented these algorithms in Desbordante - an open-source science-intensive data profiler written in C++. For Spider, we have evaluated several different options, and in case of Faida we have demonstrated that all our optimization techniques yield results. We also compared our implementations with Metanome - a Java-based data profiler. Overall, we report up to 5x improvement in terms of run time reduction for Spider and up to 8x for Faida.

Figures

Figures reproduced from arXiv: 2608.02213 by the authors.

Figure 1
Figure 1. Run time of implementations of Faida on different datasets. [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 2
Figure 2. Run time of implementations of Spider on different datasets. [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Memory consumption of implementations of Spider on different datasets. [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Time and memory consumption of Spider on Varying Memory Limits. [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references

  1. [1]

    Extending the database relational model to capture more meaning,

    E. F. Codd, “Extending the database relational model to capture more meaning,”ACM Trans. Database Syst., vol. 4, no. 4, p. 397–434, dec 1979

    1979

  2. [2]

    Database abstractions: Aggregation,

    J. M. Smith and D. C. P. Smith, “Database abstractions: Aggregation,” Commun. ACM, vol. 20, no. 6, p. 405–413, jun 1977

    1977

  3. [3]

    A normal form for relational databases that is based on domains and keys,

    R. Fagin, “A normal form for relational databases that is based on domains and keys,” vol. 6, no. 3, p. 387–415, sep 1981

    1981

  4. [4]

    Inclusion dependencies and their interaction with functional dependencies,

    M. A. Casanovaet al., “Inclusion dependencies and their interaction with functional dependencies,” inProceedings of the 1st ACM SIGACT- SIGMOD Symposium on Principles of Database Systems, ser. PODS ’82. New York, NY , USA: Association for Computing Machinery, 1982, p. 171–176

    1982

  5. [5]

    Data dependencies for query optimization: a survey,

    J. Kossmannet al., “Data dependencies for query optimization: a survey,”The VLDB Journal, vol. 31, 06 2021

    2021

  6. [6]

    Justification for inclusion dependency normal form,

    M. Levene and M. Vincent, “Justification for inclusion dependency normal form,”IEEE Transactions on Knowledge and Data Engineering, vol. 12, no. 2, pp. 281–291, 2000

    2000

  7. [7]

    The clio project: Managing heterogeneity,

    R. Milleret al., “The clio project: Managing heterogeneity,”SIGMOD Record, vol. 30, pp. 78–83, 03 2001

    2001

  8. [8]

    A machine learning approach to foreign key discovery

    A. Rostinet al., “A machine learning approach to foreign key discovery.” 01 2009

    2009

Show all 33 references
  1. [9]

    On multi-column foreign key discovery

    M. Zhanget al., “On multi-column foreign key discovery.”PVLDB, vol. 3, pp. 805–814, 09 2010

    2010

  2. [10]

    Dependencies revisited for improving data quality,

    W. Fan, “Dependencies revisited for improving data quality,” inProceed- ings of the Twenty-Seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, ser. PODS ’08. New York, NY , USA: Association for Computing Machinery, 2008, p. 159–170

    2008

  3. [11]

    Fast approximate discovery of inclusion dependencies,

    S. Kruseet al., “Fast approximate discovery of inclusion dependencies,” 03 2017

    2017

  4. [12]

    Efficiently detecting inclusion dependencies,

    J. Bauckmannet al., “Efficiently detecting inclusion dependencies,” in 2007 IEEE 23rd International Conference on Data Engineering, 2007, pp. 1448–1450

    2007

  5. [13]

    Discovery of constraints and data de- pendencies in relational databases (extended abstract),

    S. Bell and P. Brockhausen, “Discovery of constraints and data de- pendencies in relational databases (extended abstract),” inMachine Learning: ECML-95, N. Lavrac and S. Wrobel, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 1995, pp. 267–270

    1995

  6. [14]

    Efficient algorithms for mining inclusion depen- dencies,

    F. De Marchiet al., “Efficient algorithms for mining inclusion depen- dencies,” inAdvances in Database Technology — EDBT 2002. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002, pp. 464–476

    2002

  7. [15]

    Unary and n-ary inclusion dependency discovery in relational databases,

    F. D. Marchiet al., “Unary and n-ary inclusion dependency discovery in relational databases,”Journal of Intelligent Information Systems, vol. 32, pp. 53–73, 2009

    2009

  8. [16]

    Zigzag: a new algorithm for mining large inclusion dependencies in databases,

    F. De Marchi and J.-M. Petit, “Zigzag: a new algorithm for mining large inclusion dependencies in databases,” inThird IEEE International Conference on Data Mining, 2003, pp. 27–34

    2003

  9. [17]

    Discovery of high-dimensional inclusion dependencies,

    A. Koeller and E. A. Rundensteiner, “Discovery of high-dimensional inclusion dependencies,” inIn Proceedings of the International Confer- ence on Data Engineering (ICDE), 2003, pp. 683–685

    2003

  10. [18]

    Detecting maximum inclusion dependen- cies without candidate generation,

    N. Shaabani and C. Meinel, “Detecting maximum inclusion dependen- cies without candidate generation,” vol. 9828, 09 2016, pp. 118–133

    2016

  11. [19]

    Detecting inclusion dependencies on very many tables,

    F. Tschirschnitzet al., “Detecting inclusion dependencies on very many tables,”ACM Transactions on Database Systems, vol. 42, pp. 1–29, 07 2017

    2017

  12. [20]

    Discovering interesting inclusion dependencies: appli- cation to logical database tuning,

    S. Lopeset al., “Discovering interesting inclusion dependencies: appli- cation to logical database tuning,”Information Systems, vol. 27, no. 1, pp. 1–19, 2002

    2002

  13. [21]

    Rdfind: Scalable conditional inclusion dependency discovery in rdf datasets,

    S. Kruseet al., “Rdfind: Scalable conditional inclusion dependency discovery in rdf datasets,” ser. SIGMOD ’16. New York, NY , USA: Association for Computing Machinery, 2016, p. 953–967

    2016

  14. [22]

    Scaling out the discovery of inclusion dependencies,

    S. Kruse, T. Papenbrock, and F. Naumann, “Scaling out the discovery of inclusion dependencies,” inDatenbanksysteme f ¨ur Business, Technologie und Web (BTW 2015). Gesellschaft f ¨ur Informatik e.V ., 2015, pp. 445– 454

    2015

  15. [23]

    Data profiling with metanome,

    T. Papenbrocket al., “Data profiling with metanome,”Proc. VLDB Endow., vol. 8, no. 12, p. 1860–1863, aug 2015

    2015

  16. [24]

    Desbordante: from benchmarking suite to high- performance science-intensive data profiler (preprint),

    G. Chernishevet al., “Desbordante: from benchmarking suite to high- performance science-intensive data profiler (preprint),” 2023

    2023

  17. [25]

    Inclusion dependency discovery: An experimental evaluation of thirteen algorithms,

    F. D ¨urschet al., “Inclusion dependency discovery: An experimental evaluation of thirteen algorithms,” inProceedings of the 28th ACM International Conference on Information and Knowledge Management, 2019, pp. 219–228

    2019

  18. [26]

    Bell and P

    S. Bell and P. Brockhausen,Discovery of data dependencies in relational databases. Citeseer, 1995

    1995

  19. [27]

    Scalable inclusion dependency discovery,

    N. Shaabani and C. Meinel, “Scalable inclusion dependency discovery,” inDatabase Systems for Advanced Applications: 20th International Con- ference, DASFAA 2015, Hanoi, Vietnam, April 20-23, 2015, Proceedings, Part I 20. Springer, 2015, pp. 425–440

    2015

  20. [28]

    Improving the efficiency of inclusion dependency detection,

    N. Shaabaniet al., “Improving the efficiency of inclusion dependency detection,” inProceedings of the 27th ACM International Conference on Information and Knowledge Management, ser. CIKM ’18. New York, NY , USA: Association for Computing Machinery, 2018, p. 207–216

    2018

  21. [29]

    Divide & conquer-based inclusion dependency discovery,

    T. Papenbrocket al., “Divide & conquer-based inclusion dependency discovery,”Proceedings of the VLDB Endowment, vol. 8, no. 7, pp. 774–785, 2015

    2015

  22. [30]

    HyperLogLog: the analysis of a near-optimal car- dinality estimation algorithm,

    P. Flajoletet al., “HyperLogLog: the analysis of a near-optimal car- dinality estimation algorithm,” inAofA: Analysis of Algorithms, ser. DMTCS Proceedings, P. Jacquet, Ed., vol. DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07). Juan les Pins, Fra...

    2007

  23. [31]

    Brazilian e-commerce public dataset by olist,

    Olist and A. Sionek, “Brazilian e-commerce public dataset by olist,”

  24. [32]

    Desbordante: a framework for exploring limits of dependency discovery algorithms,

    M. Strutovskiyet al., “Desbordante: a framework for exploring limits of dependency discovery algorithms,” in2021 29th Conference of Open Innovations Association (FRUCT), 2021, pp. 344–354

    2021

  25. [2018]

    Available: https://www.kaggle.com/dsv/195341

    [Online]. Available: https://www.kaggle.com/dsv/195341

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.