Why MySQL OR is slower than IN

November 19, 2026
Author
Jinyou Ma
Share this Post:

Queries with OR conditions are commonly used to implement business logic.

However, it might be slower than we expected. 

Although the query below scans only 1 million rows, it runs for 6,7254 seconds.

The CPU profile indicates that 99% of CPU time was spent in Item_cond_or::val_int() on MySQL 8.4.

How MySQL evaluates OR conditions

MySQL turns id = 1 OR id = 2 OR ... OR id = N into one Item_cond_or holding N Item_func_eq  elements.

It checks each OR  element in the list until it finds a match.

  • If a row matches term k, it costs k.
  • If a row matches nothing, it costs N.

The cost of the linear search is O(N).

How MySQL evaluates IN conditions

The cost of the binary search is O(log N).

The cost of OR conditions

MySQL evaluates OR conditions in a nested loop.

The outer loop walks the rows from the table, and the inner loop walks the OR list:

Assume that

  • N is the number of values in the OR list
  • R is the number of rows the filter evaluates
  • T is the number of rows in the table

A row that matches term k leaves the inner loop after k checks, which is about N/2 on average.

A row that matches nothing runs all N.

The OR list costs O(R × N).

R depends on the query’s access type.

How access type impacts the cost

Range access: O(N²)

When the optimizer chooses range access type, it reads only the matching keys from the index:

The range has already done the filtering, but the server checks each row again, term by term.

R grows with N, and each row checks about N/2 terms: R × N/2 ≈ N²/2.

R is equal to N when all OR conditions in the table exist.

In general, the cost is O(N²).

Since the table size T does not appear in this cost, the increasing number of rows does not increase the execution time.

The same query on tables of 100k, 500k, and 1M rows takes about the same time:

Although the number of rows in the table grows 10 times from 100k to 1M, the execution time is still close.

Range access reads only the N matching rows, so only N matters.

However, R is not always equal to N.

R is less than N when only part of the list exists in the table.

R is greater than N when each value matches several rows.

In this case, the cost is O(p × N²), where p is the percentage of rows matched from the table.

Index scan: O(T × N)

When the optimizer chooses index access type, it reads all records from the index:

Now R = T. Every row in the table goes through the inner loop, and the T − N rows that match nothing run all N terms.

The cost is O(T × N). T does not change as N grows, so the cost is linear in N.

Linear does not mean cheaper, because T is much larger than N.

At N = 40,000 on this table of about 1M rows, range access checks about N²/2 = 0.8 billion terms.

The index scan checks about T × N = 40 billion, roughly 50 times more.

Going from 34,753 OR conditions to 34,754 OR conditions pushed the ranges past the limit.

The OR query went from 37 s to 2,907 s, which is 79 times longer.

 

In the index  access type, the table size T is part of this cost, and the test shows it.

The same 40,000-value OR query with an index scan took 3,406 s on a 1M-row table, 1,752 s on a 500k-row table, and 265 s on a 100k-row table.

Full table scan: O(T × N)

This is similar to the index scan, which occurs when no suitable index is available for the query.

Why does the optimizer switch from range to index

Reason 1: the range_optimizer_max_mem_size  (8 MB by default) limit is exceeded.

In this case, the server raises warning 3170 and does not use range access.

Please read more blogs about it

Low Value in range_optimizer_max_mem_size Might Cause Full Table Scan

Why Are Queries with Many IN Values More Expensive After Upgrading to MySQL 8.x?

Reason 2: the cost model thinks the index scan is cheaper.

The optimizer trace indicates it does not choose the range scan because of its cost.

The cost of IN conditions

In general, the cost of evaluating the entire IN condition is O(R log N). 

Similar to OR conditions, R depends on the query’s access type.

After rewriting the query with IN, the execution time is below.

Conclusion

Since the time complexity of OR conditions is more expensive than that of IN, the query with OR conditions is slower than the query with IN conditions.

 

0 0 votes
Article Rating
Subscribe
Notify of
guest

0 Comments
Oldest
Newest Most Voted

Far
Enough.

Said no pioneer ever.
MySQL, PostgreSQL, InnoDB, MariaDB, MongoDB and Kubernetes are trademarks for their respective owners.
© 2026 Percona All Rights Reserved