A SQL Heuristic: Ors Are Expensive

A SQL Heuristic: ORs Are Expensive

Query planning is hard. Sometimes.

Queries often have more than one filter (using an and clause).

But the developer can often end up in situations requiring an or clause:

select count(*) from application where submitter_id = :user_id or reviewer_id = :user_id;

But this is slow! With 1,000,000 applications and 1000 users uniformly distributed on both columns, it takes over 100ms.1

If we rewrite it with only and s

select ( select count(*) from application a where a.reviewer_id = :user_id ) + ( select count(*) from application a where a.submitter_id = :user_id ) - ( select count(*) from application a where a.submitter_id = :user_id and a.reviewer_id = :user_id );

This takes less than 1ms; Over 100 times faster! 12

This is surprising — we have indexes on the filtered columns.

... continue reading