Pith. sign in

REVIEW 3 major objections 5 minor 37 references

Instance-Optimized String Fingerprints

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Pith's one-line read Assigning letters to bins via mixed-integer optimization yields the lowest possible false positive rate for a workload, and the benefit carries to unseen queries.

desk verdict The MILP formulation is a real step, but the optimality claim doesn't match the row-weighted FPR that speedups depend on. read the letter →

arxiv 2507.10391 v1 pith:2277BSCJ submitted 2025-07-14 cs.DB

classification cs.DB
keywords stringfingerprintsLIKEpredicatesmixed-integeroptimizationfalsepositiveratetablescanaccelerationcolumnarqueryenginesbitmaskindexinginstance-optimized
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

String fingerprints replace each string value with a fixed-width bitmask over bins of letters; a LIKE predicate is then tested cheaply by checking whether the pattern's bitmask is a subset of the value's bitmask. This paper claims that the letter-to-bin assignment can be instance-optimized: solving a mixed-integer program over a small sample of the column and a workload of queries yields the partition with the lowest possible false positive rate for that data and those queries, with no false negatives. The authors report that on a real movie-title column in a columnar engine, the optimized 16-bit fingerprints speed up table scans by up to 1.36x, and that the advantage transfers to 280 queries never used during training. Since text-heavy workloads are common in cloud data warehouses, a workload-aware fingerprint that skips more rows without ever missing a true match is a practical acceleration for string predicates.

What carries the argument

The load-bearing mechanism is the letter-to-bin partition itself, encoded as binary variables $x_{a,i}$, together with auxiliary $d$ variables that produce each string's fingerprint bitmask. Model (1) optimizes these variables to maximize the count of query-word pairs that are correctly rejected, subject to: every character in exactly one bin; $d$ consistent with $x$; and a subset constraint that prevents false negatives. The bilinear product in constraint (1f) is linearized by standard reformulation, giving a MILP solvable by a generic optimizer. The partition's quality is what the whole argument turns on: with the same bitwidth, a better partition means fewer false positives, and therefore fewer rows on which the exact LIKE predicate must be run.

What would settle it

Build a column whose first block has a deliberately different letter distribution from the rest (for example, sort by the first character or mix two languages), train the MIP on a 50-tuple sample of that first block, and measure the row-frequency-weighted false positive rate on the full column for held-out queries. If the optimized partition's weighted FPR is no better than the round-robin baseline, or if the full-table scan is slower, the generalization claim is falsified.

Watch

Extended reading notes

Core claim

The paper's central claim is that string fingerprints, fixed-width bitmasks over a partition of the alphabet, can be made instance-optimized: solving the mixed-integer model (1) to global optimality produces the letter-to-bin partition with the lowest possible false positive rate for the given query workload and column values, and the benefit transfers to predicates that were not part of the optimization. The model maximizes the number of correctly classified query-word pairs while guaranteeing, by construction, that no true match is ever rejected, so the optimized index never introduces false negatives. Empirically, partitions trained on a 50-string sample from the first block of a 2.37M-row title column keep competitive false positive rates on the full table and on 280 unseen queries, yielding table-scan speedups of up to 1.36x.

Load-bearing premise

A partition trained on 50 strings from the first block, using only the seen queries, keeps its false-positive advantage on the full column and on queries never seen during training.

Editorial extensions

If this is right

  • A columnar engine can evaluate the bitmask predicate before the exact LIKE check, so the optimizer's lower false positive rate translates directly into fewer string comparisons and faster scans.
  • Partitions trained on 20 seen queries and a 50-string sample of the first data block retained their advantage on the full column, so the optimization appears to capture stable column-level letter structure rather than memorizing training queries.
  • For 16-bit fingerprints, the reported speedup reaches 1.36x on seen predicates and 1.26x on unseen predicates, and the 300-second optimization cost is recovered by the fourth workload run.
  • With longer patterns (up to 10 letters) and a bounded alphabet, larger bitwidths make instance optimization less necessary, because low bin density already yields sparse fingerprints.

Reading between the lines

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

  • The objective in model (1) counts each distinct query-word pair equally; a row-frequency-weighted version of the same objective would directly target scan cost and could be a natural next experiment.
  • The alphabet is restricted to 100 printable bytes; extending the formulation to full Unicode or to n-grams would increase the variable count substantially, so a practical deployment would likely need grouping or sampling rather than a direct solve.
  • The same subset-bitmask test applies to any predicate expressible as a required letter set, such as simple regex character classes, so the instance-optimization recipe could generalize beyond LIKE to other text predicates and to multi-column fingerprints.
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

3 major / 5 minor

Summary. The paper proposes instance-optimized string fingerprints for accelerating LIKE predicates in columnar engines. The alphabet is partitioned into n bins, each string is represented by a bitmask indicating which bins contain its letters, and a query pattern prefilter evaluates whether the pattern's bitmask is a subset of the string's bitmask. The authors formulate a mixed-integer program (Model 1) that, for a fixed query set Q and word set W, maximizes the number of correctly rejected query–word pairs subject to partition constraints and a no-false-negative condition. They evaluate the approach on the IMDb title column in DuckDB v1.3, reporting table-scan speedups of up to 1.36x for 20 seen queries and 1.26x for 280 unseen queries, with a round-robin partition as the only baseline.

Significance. If the empirical claims hold, the paper contributes a clean and practical instance-optimization formulation for a lightweight string index: the MILP is well specified, the no-false-negative argument (Constraints 1c–1e and the redundancy discussion) is correct, and the artifact link is a strength. The paper also honestly reports optimization gaps for the 4-bit and 8-bit settings. However, the central optimality claim is currently stated for an objective over distinct words, while the reported speedups depend on frequency-weighted row-level false positives; the transfer from a 50-tuple training sample to the full table is also not stress-tested. These are fixable within the scope of the paper, making the contribution promising but not yet fully supported.

major comments (3)
  1. [Section 2.1, Eq. (1a) and Table 1] The objective in Eq. (1a) sums over W, which Table 1 defines as the set of the column's string values (distinct words). Every word therefore contributes exactly one unit regardless of its row frequency, and the global-optimality guarantee stated in Section 2.1 ('the lowest possible false positive rate for the given queries and data') applies only to this unweighted distinct-pair rate. The reported table-scan speedups, however, are determined by row-level false positives on the full 2.37M-tuple column: a frequent value that is hard to classify dominates scan cost while contributing a single unit to the objective. The 50-tuple training sample does not repair this mismatch, because collapsing the sample to distinct words discards exactly the frequency information needed for the row-level metric. Please either reweight the objective by value frequencies or restrict the optimality claims to distinct-pair accuracy and provide empirical evidence (e.g., comparing weighted and unweighted optima on skewed columns) that the two coincide on the reported data.
  2. [Section 3, Setup] The instance-optimized partitions are trained on a 50-tuple sample drawn from the first data block (216 tuples) and then evaluated on the full table, but no sensitivity analysis is reported for the sample size or the block choice. If the first block's letter distribution is unrepresentative of the column as a whole, the optimized partition could underperform the round-robin baseline on real scans. Please add experiments that vary the training sample size and sample from multiple blocks, and report row-weighted false positive rates separately from distinct-pair accuracy so that the transfer from training to full-table performance is directly measured.
  3. [Section 3, Figure 3 and 1st Observation] The only baseline is a naive round-robin character binning. This does not isolate the benefit of optimization: a simple heuristic such as frequency-based binning or several random partitions would help establish that the solver's solution is meaningfully better than any reasonable workload-agnostic assignment. In addition, the speedup on the 20 seen queries is partially in-sample by construction, so the 1.26x on the 280 unseen queries is the stronger evidence; the paper should present this distinction more prominently and state the workload repetition assumptions behind the claim that the optimization time amortizes in the 4th run.
minor comments (5)
  1. [Section 2.1, Model Description] The phrase 'equivalent to minimizing the false positive rate' should be qualified as 'minimizing the distinct-pair false positive rate' to avoid ambiguity, especially since Section 3 evaluates row-level FPR.
  2. [Section 3, Figure 3] Figure 3 is dense: the upper subplots show FPR bars and the lower subplots show normalized latency versus optimization time, but the legend and axis labels do not clearly distinguish seen versus unseen queries across all three bitwidths. Please add explicit labels and, if possible, separate the intermediate solver solutions from the final trained partition.
  3. [Table 1 and Section 3] The paper does not explicitly state whether W in the experiments contains distinct values from the 50-tuple sample, from the first block, or from the full column. Please make the construction of W and the corresponding training set explicit.
  4. [Section 3, 3rd Observation] The heading is written as '3nd Observation'; it should be '3rd Observation'. The section heading 'EV ALUATION' also appears to be a typo for 'EVALUATION'.
  5. [Section 3, 1st Observation] The statement that optimization time amortizes in the 4th run should be accompanied by the assumed workload repetition count and whether this includes both seen and unseen queries; otherwise the amortization claim is hard to interpret.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the unseen-query result provides independent evidence, and the in-sample seen-query speedup is explicitly labeled as such.

full rationale

The claimed instance-optimization is defined by model (1), whose objective (1a) is the number of correctly classified query-word pairs. Consequently, minimization of the false positive rate on the training (seen) queries and the sampled words is intrinsic to the model rather than an independent prediction. The paper does not hide this: Section 3 states that the 300-query workload is "randomly split into 20 seen and 280 unseen queries" and that instance-optimized partitions are "trained on a 50-tuple sample from the first data block using the seen queries." The headline 1.36x speedup is reported for the seen set, and the 1.26x speedup for the 280 unseen queries is obtained with partitions not fitted to those queries, providing an independent check of generalization. No load-bearing step is justified only by self-citation: the string fingerprint mechanism is fully described in Section 2, and reference [25] is background for the prior introduction of the structure. The optimality guarantee in Section 2.1 is a direct property of the MIP; the only caveat, a potential mismatch between the distinct-word objective and row-weighted scan false positive rate, is a correctness/transfer concern rather than circularity.

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

The model itself introduces no fitted constants beyond the experimental choices listed; the MIP variables are all decision variables. The main dependencies are the domain assumption that 1-gram letter sets are a safe necessary condition and the restriction to printable bytes, plus the standard MILP linearization. No new physical or conceptual entities are invented.

free parameters (4)
  • bitwidth n = 4, 8, 16
    User-chosen number of bins, the central design knob; results in Figures 1 and 3 are reported for these values.
  • training sample size = 50 tuples
    Instance-optimized partitions are trained on a random 50-tuple sample from the first data block (Section 3 Setup); no sensitivity analysis is reported, so the choice is hand-picked.
  • MIP time limit = 300 seconds (60 seconds sufficient)
    Gurobi stops early for 4-bit and 8-bit problems, leaving optimality gaps of 5.6% and 1.9%; affects the quality of the reported partitions.
  • query workload composition = 10 highest/mid/lowest frequency k-grams for k=1..10
    The 300-query workload is built by this rule (Section 3 Benchmark); the seen/unseen split and the FPR results depend on it.
assumptions (4)
  • domain assumption The set of letters of a pattern being a subset of the set of letters of a string is a necessary condition for substring containment.
    This is the core correctness invariant of fingerprints (Section 2 Preliminaries); it holds for exact substring matching but may need adaptation for collations or case-insensitive modes.
  • domain assumption The alphabet is restricted to the 100 printable bytes, and the table is filtered to tuples containing only these bytes.
    Section 3 Benchmark states |A|=100 and reduces 2.53M to 2.37M tuples; non-printable bytes are assumed irrelevant for the workload.
  • ad hoc to paper Each character must be assigned to exactly one bin, i.e., the solution space is restricted to partitions of the alphabet.
    Constraint (1b) enforces a partition; arbitrary many-to-many character-bin assignments could yield lower FPR but are outside the model.
  • standard math Products of binary variables in constraint (1f) can be linearized without changing the optimal solution (Glover-Woolsey 1974).
    The paper invokes reference [14] for the standard linearization; this is a known correct technique.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Instance-Optimized String Fingerprints." pith.science (2026). https://pith.science/paper/2277BSCJ

@misc{pith2026250710391,
  author       = {Pith},
  title        = {Pith review of: Instance-Optimized String Fingerprints},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2277BSCJ}},
  note         = {Machine review of arXiv:2507.10391}
}
abstract

Recent research found that cloud data warehouses are text-heavy. However, their capabilities for efficiently processing string columns remain limited, relying primarily on techniques like dictionary encoding and prefix-based partition pruning. In recent work, we introduced string fingerprints - a lightweight secondary index structure designed to approximate LIKE predicates, albeit with false positives. This approach is particularly compelling for columnar query engines, where fingerprints can help reduce both compute and I/O overhead. We show that string fingerprints can be optimized for specific workloads using mixed-integer optimization, and that they can generalize to unseen table predicates. On an IMDb column evaluated in DuckDB v1.3, this yields table-scan speedups of up to 1.36$\times$.

Figures

Figures reproduced from arXiv: 2507.10391 by the authors.

Figure 1
Figure 1. Using string fingerprints to speedup table scans [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. String fingerprints are bitmasks indexing letter bins [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. Effect of string fingerprints on table scans over IMDb’s [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

37 extracted references · 24 canonical work pages

  1. [1]

    Mehmet Aytimur and Ali Cakmak. 2018. Estimating the selectivity of LIKE queries using pattern-based histograms. Turkish J. Electr. Eng. Comput. Sci. 26, 6 (2018), 3320–3335. https://doi.org/10.3906/ELK-1806-96

  2. [2]

    Mehmet Aytimur and Ali Cakmak. 2021. Using positional sequence patterns to estimate the selectivity of SQL LIKE queries. Expert Syst. Appl. 165 (2021), 113762. https://doi.org/10.1016/J.ESWA.2020.113762

  3. [3]

    Mehmet Aytimur, Silvan Reiner, Leonard Wörteler, Theodoros Chondrogiannis, and Michael Grossniklaus. 2024. LPLM: A Neural Language Model for Cardinality Estimation of LIKE-Queries. Proc. ACM Manag. Data 2, 1 (2024), 54:1–54:25. https://doi.org/10.1145/3639309

  4. [4]

    Dimitris Bertsimas, Jack Dunn, Colin Pawlowski, and Ying Daisy Zhuo. 2019. Robust classification. INFORMS Journal on Optimization 1, 1 (2019), 2–34. https: //doi.org/10.1287/ijoo.2018.0001

  5. [5]

    Burton H Bloom. 1970. Space/Time Trade-offs in Hash Coding with Allowable Errors. Commun. ACM 13, 7 (1970), 422–426

  6. [6]

    Pfetsch, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Mark Turner, Stefan Vigerske, Dieter Weninger, and Liding Xu

    Suresh Bolusani, Mathieu Besançon, Ksenia Bestuzheva, Antonia Chmiela, João Dionísio, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Mohammed Ghannam, Ambros Gleixner, Christoph Graczyk, Katrin Halbig, Ivo Hedtke, Alexander Hoen, Christopher Hojny, Rolf van der Hulst, Dominik Kamp, Thorsten Koch, Kevin Kofler, Jurgen Lentz, Julian Manns, Gioni Mexi, ...

  7. [7]

    Peter Boncz, Thomas Neumann, and Viktor Leis. 2020. FSST: fast random access string compression. Proceedings of the VLDB Endowment 13, 12 (2020), 2649–2661

  8. [8]

    Junghoo Cho and Sridhar Rajagopalan. 2002. A fast regular expression indexing engine. In Proceedings 18th International Conference on Data Engineering . IEEE, 419–430

Show all 37 references
  1. [9]

    Fran¸cois Clautiaux and Ivana Ljubić. 2025. Last fifty years of integer linear pro- gramming: A focus on recent practical advances.European Journal of Operational Research 324, 3 (2025), 707–731. https://doi.org/10.1016/j.ejor.2024.11.018

  2. [10]

    Michele Conforti, Gérard Cornuéjols, and Giacomo Zambelli. 2014. Integer Programming. Graduate Texts in Mathematics, Vol. 271. Springer, Cham. xii+456 pages. https://doi.org/10.1007/978-3-319-11008-0

  3. [11]

    Bercea, Pedro Reviriego, and Rasmus Pagh

    Niv Dayan, Ioana O. Bercea, Pedro Reviriego, and Rasmus Pagh. 2023. InfiniFilter: Expanding Filters to Infinity and Beyond. Proc. ACM Manag. Data 1, 2 (2023), 140:1–140:27. https://doi.org/10.1145/3589285

  4. [13]

    Navid Eslami and Niv Dayan. 2024. Memento Filter: A Fast, Dynamic, and Robust Range Filter. Proc. ACM Manag. Data 2, 6 (2024), 244:1–244:27. https: //doi.org/10.1145/3698820

  5. [14]

    Fred Glover and Eugene Woolsey. 1974. Converting the 0-1 Polynomial Pro- gramming Problem to a 0-1 Linear Program. Operations Research 22, 1 (1974), 180–182

  6. [15]

    Gurobi Optimization, LLC. 2024. Gurobi Optimizer Reference Manual. https: //www.gurobi.com

  7. [16]

    Bijit Hore, Hakan Hacigumus, Bala Iyer, and Sharad Mehrotra. 2004. Indexing text data under space constraints. In Proceedings of the thirteenth ACM international conference on Information and knowledge management . 198–207

  8. [17]

    IBM ILOG CPLEX Optimizer. [n.d.]. IBM ILOG CPLEX Optimizer. https: //www.ibm.com/products/ilog-cplex-optimization-studio/cplex-optimizer

  9. [18]

    Younghoon Kim, Hyoungmin Park, Kyuseok Shim, and Kyoung-Gu Woo. 2013. Efficient processing of substring match queries with inverted variable-length gram indexes. Information Sciences 244 (2013), 119–141

  10. [19]

    Suyong Kwon, Kyuseok Shim, and Woohwan Jung. 2025. Cardinality Estimation of LIKE Predicate Queries using Deep Learning. Proceedings of the ACM on Management of Data 3, 1 (2025), 1–26

  11. [20]

    Boncz, Alfons Kemper, and Thomas Neumann

    Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter A. Boncz, Alfons Kemper, and Thomas Neumann. 2015. How Good Are Query Optimizers, Really? Proc. VLDB Endow. 9, 3 (2015), 204–215. https://doi.org/10.14778/2850583.2850594

  12. [21]

    Yasushi Ogawa and Toru Matsuda. 1998. Optimizing query evaluation in n-gram indexing. In Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval . 367–368

  13. [22]

    Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. 2022. Training language models to follow instructions with human feedback.Advances in neural information processing systems 35 ...

  14. [23]

    Tobias Schmidt, Andreas Kipf, Dominik Horn, Gaurav Saxena, and Tim Kraska

  15. [24]

    Suraj Shetiya, Saravanan Thirumuruganathan, Nick Koudas, and Gautam Das

  16. [25]

    Mihail Stoian, Andreas Zimmerer, Skander Krid, Amadou Latyr Ngom, Jialin Ding, Tim Kraska, and Andreas Kipf. 2025. Parachute: Single-Pass Bi-Directional Information Passing. arXiv:2506.13670 [cs.DB] https://arxiv.org/abs/2506.13670

  17. [26]

    Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. 2023. Llama: Open and Efficient Foundation Language Models. arXiv preprint arXiv:2302.13971 (2023)

  18. [27]

    Dominic Tsang and Sanjay Chawla. 2011. A robust index for regular expression queries. In Proceedings of the 20th ACM international conference on Information and knowledge management. 2365–2368

  19. [28]

    Alexander van Renen, Dominik Horn, Pascal Pfeil, Kapil Vaidya, Wenjian Dong, Murali Narayanaswamy, Zhengchun Liu, Gaurav Saxena, Andreas Kipf, and Tim Kraska. 2024. Why TPC is not enough: An analysis of the Amazon Redshift fleet. Proceedings of the VLDB Endowment 17, 11 (2024)...

  20. [29]

    Alexander van Renen and Viktor Leis. 2023. Cloud Analytics Benchmark. In VLDB

  21. [30]

    Adrian Vogelsgesang, Michael Haubenschild, Jan Finis, Alfons Kemper, Viktor Leis, Tobias Mühlbauer, Thomas Neumann, and Manuel Then. 2018. Get Real: How Benchmarks Fail to Represent the Real World. In DBTest

  22. [31]

    Junchang Wang and Manos Athanassoulis. 2024. CUBIT: Concurrent Updatable Bitmap Indexing. Proceedings of the VLDB Endowment 18, 2 (2024), 399–412

  23. [32]

    Laurence A. Wolsey. 2020. Integer Programming. John Wiley & Sons, Inc. https: //doi.org/10.1002/9781119606475

  24. [33]

    Huanchen Zhang, Hyeontaek Lim, Viktor Leis, David G Andersen, Michael Kaminsky, Kimberly Keeton, and Andrew Pavlo. 2018. SuRF: Practical Range Query Filtering with Fast Succinct Tries. In Proceedings of the 2018 International Conference on Management of Data . 323–336

  25. [34]

    Patel, and Karthikeyan Sankaralingam

    Ling Zhang, Shaleen Deep, Jignesh M. Patel, and Karthikeyan Sankaralingam

  26. [35]

    Andreas Zimmerer, Damien Dam, Jan Kossmann, Juliane Waack, Ismail Oukid, and Andreas Kipf. 2025. Pruning in Snowflake: Working Smarter, Not Harder. In Companion of the 2025 International Conference on Management of Data, SIG- MOD/PODS 2025, Berlin, Germany, June 22-27, 2025 , ...

  27. [2020]

    Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning. Proc. VLDB Endow. 14, 4 (2020), 471–484. https://doi.org/10.14778/ 3436905.3436907

  28. [2024]

    Predicate Caching: Query-Driven Secondary Indexing for Cloud Data Warehouses. In Companion of the 2024 International Conference on Management of Data, SIGMOD/PODS 2024, Santiago AA, Chile, June 9-15, 2024 , Pablo Barceló, Nayat Sánchez-Pi, Alexandra Meliou, and S. Sudarshan (E...

  29. [2025]

    arXiv:2504.12251 [cs.DB] https://arxiv.org/abs/2504.12251

    An Evaluation of N-Gram Selection Strategies for Regular Expression Indexing in Contemporary Text Analysis Tasks. arXiv:2504.12251 [cs.DB] https://arxiv.org/abs/2504.12251

Pith tools

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