On the Vexing Difficulty of Evaluating IN Predicates
Summary: Characterizes the intrinsic difficulty of evaluating SQL IN and quantified-comparison predicates under NULL-aware SQL semantics: proves no general subquadratic algorithm exists unless SAT can be solved faster, explaining why many engines are quadratic or incorrect. Presents practical techniques and algorithms that run in linear time on common cases (and much faster in typical worst cases), yielding large empirical runtime improvements over existing systems. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Altan Birler (Technical University of Munich)
- 2. Thomas Neumann (Technical University of Munich)
BibTeX Citation
@inproceedings{birler_cidr26,
address = {Amsterdam, Netherlands},
series = {{CIDR} '26},
title = {{On the Vexing Difficulty of Evaluating IN Predicates}},
booktitle = {Proceedings of the {Conference} on {Innovative} {Data} {Systems} {Research}},
author = {Birler, Altan and Neumann, Thomas},
year = {2026}
}Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Outgoing Citations (Sorted by Pagerank)
Showing 7 of 7 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 241 | Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age | 2014 | SIGMOD | 0.00023654664 |
| 422 | Umbra: A Disk-Based System with In-Memory Performance | 2020 | CIDR | 0.00018732744 |
| 1,362 | Execution Strategies for SQL Subqueries | 2007 | SIGMOD | 0.00011032204 |
| 2,095 | Enhanced Subquery Optimizations in Oracle | 2009 | VLDB | 9.1803718e-05 |
| 5,378 | Troubles with Nulls, Views from the Users | 2022 | VLDB | 6.2406439e-05 |
| 5,744 | SQLStorm: Taking Database Benchmarking into the LLM Era | 2025 | VLDB | 6.1019672e-05 |
| 6,950 | SQL Nulls and Two-Valued Logic | 2023 | PODS | 5.7303405e-05 |
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 12,289 | Efficient Implementation of Generalized Quantification in Relational Query Languages | 2013 | VLDB |
| 2 | 3,801 | On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates | 1998 | PODS |
| 3 | 6,009 | Optimization of Conjunctive Predicates for Main Memory Column Stores | 2016 | VLDB |
| 4 | 6,678 | Output-sensitive Conjunctive Query Evaluation | 2024 | PODS |
| 5 | 1,467 | The Complexity of Evaluating Relational Queries | 1983 | PODS |
| 6 | 6,282 | Solving Implication Problems in Database Applications | 1989 | SIGMOD |
| 7 | 1,592 | Efficient Processing of Joins on Set-valued Attributes | 2003 | SIGMOD |
| 8 | 2,465 | Optimization of Queries with User-defined Predicates | 1996 | VLDB |
| 9 | 6,072 | Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited | 1989 | SIGMOD |
| 10 | 7,161 | Computing the Difference of Conjunctive Queries Efficiently | 2023 | SIGMOD |