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
- 2. Thomas Neumann
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 |
|---|---|---|---|---|
| 418 | Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age | 2014 | SIGMOD | 0.00023729211 |
| 735 | Umbra: A Disk-Based System with In-Memory Performance | 2020 | CIDR | 0.00017452467 |
| 1,582 | Execution Strategies for SQL Subqueries | 2007 | SIGMOD | 0.00011265079 |
| 2,504 | Enhanced Subquery Optimizations in Oracle | 2009 | VLDB | 8.6351917e-05 |
| 5,388 | Troubles with Nulls, Views from the Users | 2022 | VLDB | 5.5373113e-05 |
| 6,781 | SQL Nulls and Two-Valued Logic | 2023 | PODS | 4.927459e-05 |
| 8,207 | SQLStorm: Taking Database Benchmarking into the LLM Era | 2025 | VLDB | 4.5583637e-05 |