MySQL OR vs IN: Why a Long OR List Can Run for Hours
- Jinyou Ma
- 335 reads
A MySQL query with a long OR list ran for about 67,254 seconds on 1M rows. The evaluation model, not table size, explains why IN handles the same job far better.

OR conditions show up everywhere in business logic, so it's easy to forget how MySQL actually runs them. A query on a 1-million-row table with a long chain of id = ... OR id = ... terms logged a Query_time of roughly 67,254 seconds, close to 18.7 hours, while examining every row. The same job written with IN finishes in a fraction of that time. My read is that the gap comes from how the optimizer represents and walks the list, and it's predictable once you see the mechanics.

# User@Host: msandbox[msandbox] @ localhost [127.0.0.1] Id: 188 # Schema: Last_errno: 1160 Killed: 0 # Query_time: 67254.081455 Lock_time: 0.000006 Rows_sent: 1 Rows_examined: 1000000 Rows_affected: 0 Bytes_sent: 0 ... SELECT COUNT(*) FROM db1.sbtest1 WHERE id = 1 OR id = 2 OR id = 3 OR id = 4 OR id = 5 OR id = 6 OR id = 7 OR id = 8 OR id = 9 ... ...
The profile makes the diagnosis fairly blunt. On MySQL 8.4, 99% of CPU time sits in Item_cond_or::val_int(). Of that, the comparison work inside Item_func_eq and Arg_comparator::compare_int_signed accounts for most of it, while the index read path (row_search_mvcc) takes 0.02%. The engine isn't waiting on I/O. It's burning cycles deciding whether each row matches.
What the OR list becomes inside the server
MySQL folds the whole chain into one Item_cond_or node that holds N Item_func_eq children. Evaluation is a straight linear scan: for each term, check it, and stop at the first hit. That gives you a simple cost rule. A row matching term k costs k comparisons. A row matching nothing costs N. Averaged over matching rows, that's about N/2 per row, and it's still O(N) per row evaluated.
IN is structured differently. The server builds a sorted array of constants and runs std::binary_search against it, which is O(log N) per row. Same logical filter, very different per-row work. At N in the tens of thousands, the gap between linear and logarithmic lookup is enormous.
Where the nested loop bites
The OR list doesn't run once. The outer loop walks R candidate rows, and the inner loop walks up to N terms for each one. Total cost is O(R × N). Everything then hinges on R, and R depends on the access type the optimizer picks.
Range access: quadratic, but table-size independent
With a range plan, the index does the initial filtering and hands back only the matching keys. The server then re-checks each returned row term by term, so R tracks N and the cost becomes roughly N²/2. That's quadratic, and it doesn't involve T at all. Here's the part that surprised me: in the tests described, 100k, 500k and 1M-row tables take about the same time for this query. Only the number of matching keys matters.
R isn't always equal to N. It falls below N when only part of the list exists in the table, and it rises above N when each value matches several rows. In that general case the cost is O(p × N²), where p is the fraction of the table matched.


Index scan and full scan: linear in N, but multiplied by T
When the optimizer falls back to an index plan, it reads every entry in the index, so R equals T. Every row goes through the full inner loop, and the T − N non-matching rows each pay the full N terms. Cost becomes O(T × N). A full table scan (type: ALL) lands in the same complexity class when no usable index exists.
Linear in N sounds gentler than quadratic, and that's the trap. T is much larger than N, so the constant factor dominates. At N = 40,000 on a table of about 1M rows, range access checks roughly 0.8 billion terms. The index scan checks about 40 billion, around 50 times more.

The boundary effect is worth noting. Going from 34,753 to 34,754 OR conditions pushed the range plan past its memory limit, and the query went from 37 seconds to 2,907 seconds, about 79 times slower, for one extra term. With the index scan on the same 40,000-value query, runtimes were 3,406 seconds on 1M rows, 1,752 seconds on 500k, and 265 seconds on 100k. That scaling tracks T directly.

Why the optimizer switches away from range
Two mechanisms push the plan from range to index. The first is memory. range_optimizer_max_mem_size defaults to 8 MB, and when the range build exceeds it, the server raises warning 3170 and skips range optimization entirely. That's a cliff, not a slope, which explains the 79× jump above.
The second is the cost model. The optimizer trace for the range alternative shows an estimated cost of about 11,006.7 for 10,000 rows, marked as not chosen with cause "cost." Once the range option is priced out, the server defaults to a scan whose cost grows with T. Neither path is cheap at this N, but the optimizer's estimates decide which expensive path you get.
What the IN rewrite changes
Rewriting the same predicate with IN converts the chain into one sorted lookup per row. The source's measured runtime for the IN version appears only in a chart, so I'd treat the exact figure as something to confirm on your own hardware. The direction is clear, though: the per-row cost drops from O(N) to O(log N), and the query stops depending on the quadratic or T × N term.
Here's the thing: a rewrite is a fix for the query, not for the optimizer. If your application generates long OR lists from business rules, the cleaner path is to normalize them into a set, a temporary table, or a join. That's where the next round of tuning effort tends to pay off. Watch for how the optimizer's memory limit and cost estimates change across MySQL releases, because the cliff at 8 MB is the part most likely to surprise a team after an upgrade.