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.

# 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 CPU profile indicates that 99% of CPU time was spent in Item_cond_or::val_int() on MySQL 8.4.

connection └ mysql_execute_command → Sql_cmd_dml::execute → Query_expression::ExecuteIteratorQuery └ AggregateIterator::Read 99.80% └ FilterIterator::Read 99.80% ├ Item_cond_or::val_int 98.96% │ └ Item::val_bool → Item_func_eq::val_int 91.27% │ └ Arg_comparator::compare_int_signed 58.46% │ ├ Item_field::val_int 16.18% │ └ (literal) val_int 10.04% └ IndexScanIterator::Read → row_search_mvcc 0.02%

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.

longlong Item_cond_or::val_int() { assert(fixed); List_iterator_fast<Item> li(list); Item *item; null_value = false; while ((item = li++)) { if (item->val_bool()) { null_value = false; return 1; } if (item->null_value) null_value = true; if (current_thd->is_error()) return error_int(); } return 0; }

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

bool in_longlong::find_item(Item *item) { if (m_used_size == 0) return false; packed_longlong result; val_item(item, &result); if (item->null_value) return false; return std::binary_search(base.begin(), base.begin() + m_used_size, result, Cmp_longlong()); }

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:

for each row r: -- outer loop: R rows for each term o: -- inner loop: up to N terms if r == o: break -- exit inner loop; continue with next row

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:

mysql > explain for connection 11\G *************************** 1. row *************************** id: 1 select_type: SIMPLE table: sbtest1 partitions: NULL type: range possible_keys: PRIMARY key: PRIMARY key_len: 8 ref: NULL rows: 34753 filtered: 100.00 Extra: Using where; Using index 1 row in set (0.00 sec)

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:

mysql > explain for connection 11\G *************************** 1. row *************************** id: 1 select_type: SIMPLE table: sbtest1 partitions: NULL type: index possible_keys: PRIMARY key: PRIMARY key_len: 8 ref: NULL rows: 1000000 filtered: 100.00 Extra: Using where; Using index 1 row in set (0.00 sec)

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.

mysql> explain for connection 9\G *************************** 1. row *************************** id: 1 select_type: SIMPLE table: sbtest1 partitions: NULL type: ALL possible_keys: NULL key: NULL key_len: NULL ref: NULL rows: 1000000 filtered: 100.00 Extra: Using where 1 row in set (0.01 sec)

Why does the optimizer switch from range to index

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

mysql > show warnings limit 1\G *************************** 1. row *************************** Level: Warning Code: 3170 Message: Memory capacity of 8388608 bytes for 'range_optimizer_max_mem_size' exceeded. Range optimization was not done for this query. 1 row in set (0.00 sec)

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.

"range_scan_alternatives": [ { "index": "PRIMARY", "ranges": [ "id = 1", ... "id = 9998", "id = 9999", "id = 10000" ], "index_dives_for_eq_ranges": false, "rowid_ordered": true, "using_mrr": false, "index_only": true, "in_memory": 0.000709723, "rows": 10000, "cost": 11006.7, "chosen": false, "cause": "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.

 

The post Why MySQL OR is slower than IN appeared first on Percona.