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 →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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.
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
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [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.
- [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.
- [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)
- [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.
- [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.
- [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.
- [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'.
- [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
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
free parameters (4)
- bitwidth n =
4, 8, 16
- training sample size =
50 tuples
- MIP time limit =
300 seconds (60 seconds sufficient)
- query workload composition =
10 highest/mid/lowest frequency k-grams for k=1..10
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.
- domain assumption The alphabet is restricted to the 100 printable bytes, and the table is filtered to tuples containing only these bytes.
- 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.
- standard math Products of binary variables in constraint (1f) can be linearized without changing the optimal solution (Glover-Woolsey 1974).
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
Reference graph
Works this paper leans on
-
[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]
-
[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]
-
[5]
Burton H Bloom. 1970. Space/Time Trade-offs in Hash Coding with Allowable Errors. Commun. ACM 13, 7 (1970), 422–426
work page 1970
-
[6]
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, ...
arXiv 2024
-
[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
work page 2020
-
[8]
Junghoo Cho and Sridhar Rajagopalan. 2002. A fast regular expression indexing engine. In Proceedings 18th International Conference on Data Engineering . IEEE, 419–430
work page 2002
Show all 37 references
-
[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
2025 doi
-
[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
2014 doi
-
[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
2023 doi
-
[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
2024 doi
-
[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
1974
-
[15]
Gurobi Optimization, LLC. 2024. Gurobi Optimizer Reference Manual. https: //www.gurobi.com
2024
-
[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
2004
-
[17]
IBM ILOG CPLEX Optimizer. [n.d.]. IBM ILOG CPLEX Optimizer. https: //www.ibm.com/products/ilog-cplex-optimization-studio/cplex-optimizer
-
[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
2013
-
[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
2025
-
[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
2015
-
[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
1998
-
[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 ...
2022
-
[23]
Tobias Schmidt, Andreas Kipf, Dominik Horn, Gaurav Saxena, and Tim Kraska
-
[24]
Suraj Shetiya, Saravanan Thirumuruganathan, Nick Koudas, and Gautam Das
-
[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
2025 arXiv
-
[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)
2023 arXiv
-
[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
2011
-
[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)...
2024
-
[29]
Alexander van Renen and Viktor Leis. 2023. Cloud Analytics Benchmark. In VLDB
2023
-
[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
2018
-
[31]
Junchang Wang and Manos Athanassoulis. 2024. CUBIT: Concurrent Updatable Bitmap Indexing. Proceedings of the VLDB Endowment 18, 2 (2024), 399–412
2024
-
[32]
Laurence A. Wolsey. 2020. Integer Programming. John Wiley & Sons, Inc. https: //doi.org/10.1002/9781119606475
2020 doi
-
[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
2018
-
[34]
Patel, and Karthikeyan Sankaralingam
Ling Zhang, Shaleen Deep, Jignesh M. Patel, and Karthikeyan Sankaralingam
-
[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 , ...
2025
-
[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
2020
-
[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...
2024
-
[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
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.