Pith. sign in

REVIEW 5 major objections 8 minor 30 references

Order in Desbordante: Techniques for Efficient Implementation of Order Dependency Discovery Algorithms

T0 review · 5 major / 8 minor · reviewed 2026-07-30 · grok-4.5

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

Pith's one-line read Careful C++ reimplementation plus range-based partitions speeds order-dependency discovery up to 10× and cuts memory up to 2.9×.

desk verdict Solid engineering paper: real C++ speed-ups and a useful range-based partition trick for OD mining, not a new theory result. read the letter →

arxiv 2607.23632 v1 pith:E6HFDK3A submitted 2026-07-26 cs.DB cs.AIcs.LGcs.PF

Yakov Kuzin , Dmitriy Shcheka , Michael Polyntsov , Kirill Stupakov , Mikhail Firsov , George Chernishev This is my paper · ORCID
classification cs.DBcs.AIcs.LGcs.PF
keywords orderdependencyODdiscoveryFASTODdataprofilingstrippedpartitionsrange-basedimplementationoptimization
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

Order dependencies capture the fact that sorting a table by one list of columns also sorts it by another; they matter for query optimization, cleaning, deduplication, and anomaly detection. Prior work treated discovery purely as an algorithmic problem and shipped only Java research prototypes, leaving a large engineering gap on a task that is already computationally heavy. This paper reimplements the two main miners—ORDER (list-based, incomplete but fast) and FASTOD (set-based, complete)—in C++, then attacks their real bottlenecks with new data-structure techniques. The central result is that implementation choices alone move OD discovery much closer to practical, industrial use.

What carries the argument

Range-based stripped partitions: equivalence classes are stored as contiguous index ranges rather than full index lists, chosen automatically when a column has enough runs, intersected by a fast range-product algorithm, and switched back to ordinary lists once ranges become too fragmented.

What would settle it

Run the optimized FASTOD side-by-side with the plain C++ baseline on a large table whose run-length distribution sits near the three switch thresholds; if the optimized version is slower or more memory-hungry while still returning the identical dependency set, the claimed gains do not generalize.

Watch

Extended reading notes

Core claim

Simply rewriting ORDER and FASTOD in C++ already yields up to roughly 3× lower runtime and substantially less memory than the original Java prototypes; adding the authors’ targeted techniques—especially a range-based representation of stripped partitions for FASTOD and faster containers and sorts for ORDER—raises total speed-ups to as much as 10× while reducing memory consumption by up to 2.9×.

Load-bearing premise

Three fixed numeric thresholds that decide when to start with ranges and when to switch back work well on tables beyond the evaluation suite and never silently hurt correctness or cost.

Editorial extensions

If this is right

  • OD discovery becomes feasible on larger tables that previously exhausted time or RAM.
  • Other lattice miners that rely on equivalence-class partitions can reuse the same range representation.
  • Practitioners can pick ORDER for a fast incomplete sketch or FASTOD for a complete result, both now at usable speed.
  • Query optimizers and cleaning pipelines can afford OD checks more frequently.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same range-compression idea is likely to help other partition-heavy dependency miners such as functional-dependency and denial-constraint algorithms.
  • The three hand-chosen constants point to a natural next step: an adaptive or learned policy for choosing and switching representations.
  • A hybrid pipeline that runs fast incomplete ORDER first as a pre-filter before complete FASTOD is an untested but direct corollary of the two algorithms’ complementary strengths.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

5 major / 8 minor

Summary. The paper presents C++ reimplementations of two order-dependency (OD) discovery algorithms — FASTOD (set-based axiomatization) and ORDER (list-based) — inside the open-source Desbordante profiler, plus two classes of optimizations: (i) a range-based stripped-partition representation for FASTOD with a preprocessing-time selection heuristic and a dynamic switch back to the standard representation, governed by three constants; and (ii) Boost-based replacements (flat stable sort / block indirect sort, unordered flat set/map) for ORDER's hot paths. Experiments against the original Java implementations on 15 (FASTOD) and 7 (ORDER) real datasets report speedups of up to ~10x total and memory reductions of up to ~2.9x, with three-run averages, scalability plots over column count, and breakdowns of baseline-vs-optimized contributions. The paper also gives a tutorial-style treatment of both OD axiomatizations and an honest account of ORDER's incompleteness relative to FASTOD.

Significance. If the numbers hold up after the requested audit, this is a useful systems contribution: it ships what appear to be the only open-source C++ implementations of ORDER and FASTOD, merged into Desbordante (PRs 294, 355), with a public data repository — a genuine reproducibility asset. The range-based stripped partition with adaptive switch-over is a clean, reusable data-structure idea with applicability to other partition-based dependency-discovery algorithms. The evaluation is broad (15 FASTOD and 7 ORDER datasets) and commendably honest in places: the authors report that the optimized variant uses more memory than the baseline (Table VI) and that Java wins on one ORDER dataset (Table VIII). These are the marks of a credible empirical study, and the claimed gains (up to ~10x time, ~2.9x memory) would matter for practical OD discovery.

major comments (5)
  1. [Abstract; Tables V–VIII] Abstract/§VI vs. Tables V, VI, VIII: the headline numbers are internally inconsistent. The abstract claims 'up to 3x' for reimplementation, 'up to 10x' with techniques, and 'up to 2.9x' memory. Table V shows FASTOD base-vs-Java up to 7.77x (S1) and total up to 10.16x (D1); §V-B Exp. 1 says 'up to 8, average 4'; Table VIII shows ORDER total up to 24.06x (Modis); Table VI shows Java-vs-base memory up to 14.96x (D2). The abstract matches none of these. Since the speed-up factors are the paper's central claim, all quoted numbers must be reconciled with the tables.
  2. [§II, Theorem 2.2, Examples 2.2/2.4] Theorem 2.2 ('X↦→< Y iff X↦→≤ Y') is false as stated: on r = {(1,1),(1,2)} over single attributes X,Y the strict OD holds vacuously (no pair satisfies sX < tX) while the ≤-OD is violated by the split. This also contradicts the paper's own §II-C statement that splits invalidate only ≤/≥ ODs. Relatedly, Example 2.2/2.4 asserts FD {Weight}→{Shipment cost} holds in Table I, but tuples t2 (15,48) and t4 (15,28) — the very split cited in Ex. 2.4 — violate that FD. The intended FD-vs-OD teaching point requires a corrected example.
  3. [§V-A/B, Experimental Setup] JVM methodology is unspecified, yet the 'ME'/∞ entries in Tables V–VI and the claim that Java runs out of RAM are load-bearing for the memory-savings story. Default -Xmx is typically a fraction of physical RAM, so a heap error does not establish 'not enough RAM on the computer.' Report JVM flags (-Xmx, GC), warmup handling, and how peak memory was measured on both sides; otherwise the ∞ rows and the memory ratios are not interpretable.
  4. [§IV-D, §V] No correctness validation of the reimplementations is reported. The paper never states that the C++ FASTOD/ORDER outputs are identical to the Java references' outputs (or that optimized and baseline C++ agree). Table IV's #OD/#FD/#OCD columns suggest result counts are available — please state explicitly whether dependency sets match the Java baselines on the integer-transformed datasets. For a paper whose premise is faithful reimplementation, this check is essential.
  5. [§IV-E] The three constants governing the range-based partition (range-forming proportion 0.001, small-range cutoff 40, switch-over ratio 0.5) are asserted without justification or sensitivity analysis. RQ3's no-degradation claim and the adaptive-switch behavior rest on these values. A small sensitivity sweep on two or three datasets (or a principled selection procedure) would substantiate that the technique is robust rather than tuned to the evaluation suite.
minor comments (8)
  1. [§V-C, Table II] Table II: the combined speedup exceeds the product of the individual ones (Diabetes: 1.017 × 4.954 × 0.969 ≈ 4.88 vs. 6.253 reported); 'sort' alone is a slowdown on Diabetes (0.969x); flat_set alone yields 4.95x only on Diabetes. The interaction effects deserve a sentence of analysis.
  2. [§V-C] Several ORDER runtimes are sub-second (Pfw optimized 0.209s, Diabetes optimized 0.591s) and each experiment is averaged over only three runs. Report standard deviations and consider more repetitions, since timer noise at this scale is comparable to the measured effects.
  3. [Table VI] Table VI, row D2: the 14.96x memory reduction is an outlier against 1.8–3.9x elsewhere and deserves an explanation (also the D2 dataset is 5 MB on disk while Java uses 1 GB).
  4. [§V-B, Table IV] Dataset provenance is weak: Table IV names such as 'file.csv', 'Dataset norm.csv', and 'Test norm.csv' are uninformative. Please give sources, and describe the integer-encoding transformation applied for Java FASTOD, including whether it preserves partition/equivalence-class structure (otherwise the comparison could be skewed).
  5. [§V-C] §V-C Exp. 1: Java beats the C++ baseline on Diabetes (0.901x). This is noted only as motivation for optimizations; a brief analysis of why the Java version wins here would strengthen the evaluation.
  6. [§VI] Conclusion is garbled: 'ORDER is significantly faster than FASTOD, but misses some dependencies... ORDER, on the other hand, can be useful for quick profiling' — the second subject should presumably be FASTOD; the same confusion appears in §V-C.
  7. [Throughout] Typos/notation: '80es' (§I), 'altough' (§III), 'out knowledge' (§III), 'XX\{A,B}' in the C+/C− definitions (§IV-C), broken header layout in Table V, and barely legible bar labels in Figures 1–2. State the Boost version used in §IV-F.
  8. [§III] §III contrasts ORDER's O(|R|!) with FASTOD's O(2^|R|) and says FASTOD 'achieves greater performance', while §V-C shows ORDER is empirically much faster. Clarify that the complexity bounds concern lattice size, not observed runtime.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: empirical systems paper whose speed/memory claims are measured against external Java baselines, not derived from self-defined or fitted quantities.

full rationale

The paper reimplements two known OD algorithms (ORDER, FASTOD) in C++, adds engineering optimizations (range-based stripped partitions with three fixed thresholds; Boost sort/hash structures), and reports wall-clock and memory ratios versus the original Java prototypes on public tables. The central claims are purely experimental (up to 3x from language change, up to 10x with techniques, up to 2.9x less RAM). No equation equates an output quantity to an input by construction; the three partition constants (0.001, 40, 0.5) are stated as fixed heuristics, not fitted parameters later presented as predictions. Self-citations to prior Desbordante papers supply only the host framework and earlier anecdotal C++ gains; they are not load-bearing for the measured OD results. Completeness/incompleteness statements about the algorithms are taken from the external literature being reimplemented. Consequently the derivation chain contains no self-definitional loop, fitted-input-as-prediction, uniqueness import, or ansatz smuggling.

Assumptions & free parameters 3 free parameters · 2 assumptions · 1 invented entities

The central performance claims rest on three hand-tuned numeric thresholds inside the range-based partition logic plus the standard correctness assumptions of the original ORDER and FASTOD algorithms. No new mathematical axioms are introduced; the invented entity is the range representation itself.

free parameters (3)
  • range-forming proportion threshold = 0.001
    Column is flagged for range representation if the fraction of values that form contiguous runs exceeds this constant (Section IV-E).
  • small-range size cutoff = 40
    Ranges shorter than this length are counted as ‘small’ when deciding whether to switch representation (Section IV-E).
  • switch-over ratio = 0.5
    If the fraction of small ranges exceeds this constant after a product, the partition is converted back to the ordinary list representation (Section IV-E).
assumptions (2)
  • domain assumption The original ORDER and FASTOD algorithms (including their pruning rules and partition-product correctness) are sound for the respective list-based and set-based OD axiomatizations.
    All speed claims are relative to these baselines; the paper does not re-prove them (Sections II–IV).
  • standard math Storing equivalence classes as index ranges instead of explicit index lists is information-preserving until an explicit conversion occurs.
    Used to justify that the optimized FASTOD still returns exactly the same ODs (Section IV-E).
invented entities (1)
  • RangeBasedStrippedPartition independent evidence
    purpose: Compact representation of stripped partitions that stores contiguous identical-value runs as intervals, enabling faster products and lower memory on run-heavy columns.
    Introduced in Section IV-E together with the dynamic switch heuristic and the specialized intersection algorithm; not present in prior OD literature.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Order in Desbordante: Techniques for Efficient Implementation of Order Dependency Discovery Algorithms." pith.science (2026). https://pith.science/paper/E6HFDK3A

@misc{pith2026260723632,
  author       = {Pith},
  title        = {Pith review of: Order in Desbordante: Techniques for Efficient Implementation of Order Dependency Discovery Algorithms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/E6HFDK3A}},
  note         = {Machine review of arXiv:2607.23632}
}
read the original abstract

Science-intensive data profiling focuses on discovery and validation of various patterns in datasets. This study considers discovery of one such pattern - order dependency (OD). Simply put, OD states that some list of columns is ordered according to another one. It is of use for database query optimization, data cleaning and deduplication, anomaly detection, and much more. Existing discovery methods have approached this problem solely from the algorithmic standpoint, without focusing on the implementation side. At the same time, this problem is very computationally intensive, and therefore this part should not be ignored, as it brings ODs closer to industrial use. In this paper, we study two algorithms for OD discovery which target different OD axiomatizations - FASTOD and ORDER. We start by reimplementing these algorithms in C++ in order to speed them up and lower their memory consumption. We then analyze their bottlenecks and propose several techniques which improve their performance even further. To perform evaluation, we have implemented these algorithms inside Desbordante - a science-intensive, high-performance, and open-source data profiling tool developed in C++. Experiments have demonstrated a performance improvement of up to 3x obtained by reimplemented versions, and, with the application of our techniques, up to 10x. Memory consumption has been lowered by up to 2.9x.

Figures

Figures reproduced from arXiv: 2607.23632 by the authors.

Figure 3
Figure 3. Memory usage (FASTOD) C++ implementation outperforms Java implementations by 2.9–3.9 times and the optimized implementation outperforms it by 2.4–2.9 times. It is also noticeable that the optimized implementation consumes more memory than the baseline one. This is a necessary price to pay for reducing execution time. In addition, we found that the Java implementation con￾sumes too much memory. For example, its execu… view at source ↗
Figure 1
Figure 1. Scalability in number of columns, part 1 (FASTOD) [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Scalability in number of columns, part 2 (FASTOD) [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 2 canonical work pages

  1. [1]

    Holistic data cleani ng: Putting violations into context,

    X. Chu, I. F. Ilyas, and P . Papotti, “Holistic data cleani ng: Putting violations into context,” in ICDE’13, C. S. Jensen et al. , Eds. IEEE Computer Society, 2013, pp. 458–469

    2013

  2. [2]

    Abedjan, L

    Z. Abedjan, L. Golab, F. Naumann, and T. Papenbrock, Data Profiling. Morgan & Claypool Publishers, 2018

    2018

  3. [3]

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

    G. Chernishev et al. , “Desbordante: from benchmarking suite to high-performance science-intensive data profiler,” CoRR, vol. abs/2301.05965, 2023

    arXiv 2023

  4. [4]

    Functional dependency discovery: an experimental evaluation of seven algorithms,

    T. Papenbrock et al., “Functional dependency discovery: an experimental evaluation of seven algorithms,” Proc. VLDB Endow. , vol. 8, no. 10, p. 1082–1093, jun 2015

    2015

  5. [5]

    Inclusion dependency discovery: An experimental evaluation of thirteen algorithms,

    F. D¨ ursch et al. , “Inclusion dependency discovery: An experimental evaluation of thirteen algorithms,” in CIKM’19, 2019, p. 219–228. TABLE IV DATASET DESCRIPTION (FASTOD) Dataset Short name Columns Rows Size (MB) #OD #FD #OCD graduation dataset norm 15c.csv G 15 4424 0.14 333 1 332 Anonymize norm.csv A 23 38480 4.28 115400 7774 107626 PFW 2021 public n...

    2019

  6. [6]

    C. C. Aggarwal and J. Han, Frequent Pattern Mining . Springer Publishing Company, Incorporated, 2014

    2014

  7. [7]

    Bhunt: Automatic discovery of fuzzy alge- braic constraints in relational data,

    P . G. Brown and P . J. Hass, “Bhunt: Automatic discovery of fuzzy alge- braic constraints in relational data,” in VLDB’03. VLDB Endowment, 2003, p. 668–679

    2003

  8. [8]

    Sherlock: A deep learning approach to semantic data type detection,

    M. Hulsebos et al. , “Sherlock: A deep learning approach to semantic data type detection,” in SIGKDD’19, 2019, p. 1500–1508

    2019

Show all 30 references
  1. [9]

    Effective and complete discovery of order dependencies vi a set-based axiomatization,

    J. Szlichta, P . Godfrey, L. Golab, M. Kargar, and D. Sriva stava, “Effective and complete discovery of order dependencies vi a set-based axiomatization,” Proc. VLDB Endow., vol. 10, no. 7, pp. 721–732, 2017. [Online]. Available: http://www.vldb.org/pvldb/vol10/p721-szlichta.pdf

    2017

  2. [10]

    Expre ssiveness and complexity of order dependencies,

    J. Szlichta, P . Godfrey, J. Gryz, and C. Zuzarte, “Expre ssiveness and complexity of order dependencies,” Proc. VLDB Endow. , vol. 6, no. 14, pp. 1858–1869, 2013. [Online]. Available: ht tp: //www.vldb.org/pvldb/vol6/p1858-szlichta.pdf

    2013

  3. [11]

    Order dependency in the relati onal model,

    S. Ginsburg and R. Hull, “Order dependency in the relati onal model,” Theoretical Computer Science , vol. 26, no. 1, pp. 149–195, 1983. [Online]. Available: https://www.sciencedirect.com/sc ience/article/pii/ 0304397583900841

    1983

  4. [12]

    Efficient order dependency de tection,

    P . Langer and F. Naumann, “Efficient order dependency de tection,” VLDB J. , vol. 25, no. 2, pp. 223–241, 2016. [Online]. Available: https://doi.org/10.1007/s00778-015-0412-3

    2016 doi

  5. [13]

    Des- bordante: a framework for exploring limits of dependency di scovery algorithms,

    M. Strutovskiy, N. Bobrov, K. Smirnov, and G. Chernishe v, “Des- bordante: a framework for exploring limits of dependency di scovery algorithms,” in 2021 29th Conference of Open Innovations Association (FRUCT), 2021, pp. 344–354

    2021

  6. [14]

    Fast discovery of inclusion dependencies with desbordant e,

    A. Smirnov, A. Chizhov, I. Shchuckin, N. Bobrov, and G. C hernishev, “Fast discovery of inclusion dependencies with desbordant e,” in 2023 33rd Conference of Open Innovations Association (FRUCT) , 2023, pp. 264–275

    2023

  7. [15]

    Fundamentals of o rder dependencies,

    J. Szlichta, P . Godfrey, and J. Gryz, “Fundamentals of o rder dependencies,” Proc. VLDB Endow. , vol. 5, no. 11, p. 1220–1231, jul

  8. [16]

    An extension of the relational data model to inco rporate ordered domains,

    W. Ng, “An extension of the relational data model to inco rporate ordered domains,” ACM Trans. Database Syst. , vol. 26, no. 3, p. 344–383, sep

  9. [17]

    Effective and complete discovery of bidirectional order d ependencies via set-based axioms,

    J. Szlichta, P . Godfrey, L. Golab, M. Kargar, and D. Sriv astava, “Effective and complete discovery of bidirectional order d ependencies via set-based axioms,” The VLDB Journal , vol. 27, no. 4, p. 573–591, aug 2018. [Online]. Available: https://doi.org/ 10.1007/ s00778-018-0510-0

    2018

  10. [18]

    Fast incremental disco very of pointwise order dependencies,

    Z. Tan, A. Ran, S. Ma, and S. Qin, “Fast incremental disco very of pointwise order dependencies,” Proc. VLDB Endow. , vol. 13, no. 10, p. 1669–1681, jun 2020. [Online]. Available: https://doi. org/10.14778/ 3401960.3401965

    2020

  11. [19]

    Discovering denial constraints,

    X. Chu, I. F. Ilyas, and P . Papotti, “Discovering denial constraints,” Proc. VLDB Endow., vol. 6, no. 13, p. 1498–1509, aug 2013

    2013

  12. [20]

    Efficient bidirectional orde r dependency discovery,

    Y . Jin, L. Zhu, and Z. Tan, “Efficient bidirectional orde r dependency discovery,” in 2020 IEEE 36th International Conference on Data Engi- neering (ICDE) , 2020, pp. 61–72

    2020

  13. [21]

    Distributed imple mentations of dependency discovery algorithms,

    H. Saxena, L. Golab, and I. F. Ilyas, “Distributed imple mentations of dependency discovery algorithms,” Proc. VLDB Endow., vol. 12, no. 11, p. 1624–1636, jul 2019

    2019

  14. [22]

    Efficient distributed di scovery of bidirectional order dependencies,

    S. Schmidl and T. Papenbrock, “Efficient distributed di scovery of bidirectional order dependencies,” The VLDB Journal , vol. 31, no. 1, p. 49–74, aug 2021

    2021

  15. [23]

    Mining functional dependenc ies from data,

    H. Y ao and H. J. Hamilton, “Mining functional dependenc ies from data,” Data Min. Knowl. Discov. , vol. 16, no. 2, p. 197–219, apr 2008

    2008

  16. [24]

    Fastfds: A heu ristic-driven, depth-first algorithm for mining functional dependencies f rom relation instances extended abstract,

    C. Wyss, C. Giannella, and E. Robertson, “Fastfds: A heu ristic-driven, depth-first algorithm for mining functional dependencies f rom relation instances extended abstract,” in DaW aK, Y . Kambayashi et al. , Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2001, pp. 101–110

    2001

  17. [25]

    Tane: An efficient algorithm for discovering functional and approxi mate depen- dencies,

    Y . Huhtala, J. K¨ arkk¨ ainen, P . Porkka, and H. Toivonen , “Tane: An efficient algorithm for discovering functional and approxi mate depen- dencies,” The Computer Journal , vol. 42, no. 2, pp. 100–111, 1999

    1999

  18. [26]

    Discovering domain orders via order dependen- cies,

    R. Karegar, M. Mirsafian, P . Godfrey, L. Golab, M. Kargar , D. Srivas- tava, and J. Szlichta, “Discovering domain orders via order dependen- cies,” in ICDE’22, 2022, pp. 1098–1110

    2022

  19. [27]

    Discovering order dependencies through order com- patibility,

    C. Consonni et al., “Discovering order dependencies through order com- patibility,” in EDBT’19, M. Herschel et al., Eds. OpenProceedings.org, 2019, pp. 409–420

    2019

  20. [28]

    Errata note: Discovering order dependencies through order compat ibility,

    P . Godfrey, L. Golab, M. Kargar, D. Srivastava, and J. Sz lichta, “Errata note: Discovering order dependencies through order compat ibility,” CoRR, vol. abs/1905.02010, 2019

    1905 arXiv

  21. [2001]

    Available: https://doi.org/10.1145/502 030.502033

    [Online]. Available: https://doi.org/10.1145/502 030.502033

    doi

  22. [2012]

    Available: https://doi.org/10.14778/23 50229.2350241

    [Online]. Available: https://doi.org/10.14778/23 50229.2350241

Pith tools

Reviewed July 30, 2026 · model on record in the stance chip above.