Does MySQL 'OR' and two SELECT statements have same complexity?

Question

1. "SELECT id, name FROM Customers WHERE id = id1 OR id = id2"

2. "SELECT id, name FROM Customers WHERE id = id1" and again, "SELECT id, name FROM Customers WHERE id = id2"

Does it take same time for the above two cases in the context of MySQL? OR How does OR gets implemented internally?

EDIT:

Assume Customerstable is indexed on id column

score 1 · Answer 1 · answered Apr 29 '19 at 11:35

1

You should phrase this as:

SELECT id, name
FROM Customers
WHERE id IN (@id1, @id2);

Assuming that id1 and id2 are passed into the query, then they would only be similar if you had an index on id (which is reasonable). Of course, running two queries incurs overhead of running two queries. However, the complexity is the same, from the perspective of algorithmic analysis.

Without an index, the two-query version is slower by a factor of two, because it needs to scan the table twice. However, although that is slower, it does not affect complexity.

answered Apr 29 '19 at 11:35

Gordon Linoff

1,242,037
58
646
786

@tezz (topicstarter) Yes it's also a known fact that the Oracle database optimizer (Not MySQL's optimizer i wished it did) rewrites `OR` conditions not 100% sure about the `IN()` and expands it to `SELECT .. WHERE id = UNION ALL SELECT .. WHERE id = ` in most cases when the column is indexed because it's faster.. – Raymond Nijland Apr 29 '19 at 11:48
@RaymondNijland I think this https://stackoverflow.com/a/189399/3881561 is a bit relevant to what you're saying. In 3rd highlighted-point, he/she points out that it's a bad idea to use `UNION ALL`. If so, how come Oracle's optimizer uses that? – tezz Apr 29 '19 at 12:03
We are going a bit to far offtopic now: *"In 3rd highlighted-point ..idea to use UNION ALL"* Yes on unindexed columns it is on indexed column it's fine *"If so, how come Oracle's optimizer uses that? "* @tezz [Slow join behaviour with 'or' in predicate](https://dba.stackexchange.com/questions/51914/slow-join-behaviour-with-or-in-predicate) also notice the link [Optimizer Transformations: OR Expansion](https://blogs.oracle.com/optimizer/entry/or_expansion_transformation) very important`UNION [ALL]` can use parallel queries to fetch the results concurrently in Oracle database – Raymond Nijland Apr 29 '19 at 12:14

score 1 · Accepted Answer · answered May 02 '19 at 01:17

90% of a simple select is overhead (network, parsing, optimizing, etc).

id = 123 OR id = 345 is optimized to id IN (123, 345). If there is an index on id (the PRIMARY KEY is an index), this is 2 probes into the table.

So if fetching one row is 100% of effort, then fetching 2 is about 110% of that (90% overhead, then 2 units of real work).

Meanwhile, 2 separate selects would be 200%.

On the other hand, if you have

WHERE x = 98 OR y = 65

there is no good indexing method for such.

Plan A: A full table scan, checking x and y for every row. Really slow for a big table.

Plan B: Change it to

( SELECT ... WHERE x = 98 )
UNION
( SELECT ... WHERE y = 65 )

This will be more like 200%. That is, making two queries helps in this case.

Plan C is "index merge union", which the Optimizer only occasionally resorts to.

Does MySQL 'OR' and two SELECT statements have same complexity?

2 Answers2