Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A SQL Heuristic: ORs Are Expensive

ethanseal.com

Post reply on HN
Print view View original

31–40 of 82 posts

Re: A SQL Heuristic: ORs Are Expensive

#31

Post by renhanxue »

Glyptodon wrote: post #16

If optimization is really as simple as applying De Morgan's laws, surely it could be done within the query planner if that really is the main optimization switch? Or am I misreading this somehow? Edit: I guess the main difference is that it's just calculating separate sets and then merging them, which isn't really DeMorgan's, but a calculation approach.

The core issue the article is pointing to is that most database indexes are B-trees, so if you have a predicate on the form (col_a = 'foo' OR col_b = 'foo'), then it is impossible to use a single B-tree lookup to find all rows that match the predicate. You'd have to do two lookups and then merge the sets. Some query optimizers can do that, or at least things that are similar in spirit (e.g. Postgres bitmap index scan), but it's much more expensive than a regular index lookup.

Re: A SQL Heuristic: ORs Are Expensive

#32

Post by contravariant »

Glyptodon wrote: post #16

If optimization is really as simple as applying De Morgan's laws, surely it could be done within the query planner if that really is the main optimization switch? Or am I misreading this somehow? Edit: I guess the main difference is that it's just calculating separate sets and then merging them, which isn't really DeMorgan's, but a calculation approach.

I'm not seeing De Morgan. I am seeing inclusion exclusion, which is just a neat trick all round. Highly recommend remembering it.

I imagine negative filters to be a bit inefficient as well, though maybe not for a simple count.

Re: A SQL Heuristic: ORs Are Expensive

#33

Post by cogman10 »

Animats wrote: post #15

The query optimizer knows how many items are in each index, but has no advance idea how many items will be in the result of a JOIN. An "a OR b" query on a table with millions of rows might have three hits on A, or millions of hits. The optimal query strategy for the two cases is very different. Has anyone put machine learning in an SQL query optimizer yet?

> Has anyone put machine learning in an SQL query optimizer yet?

Yes, I think everyone has? At very least I know that MSSQL has because we semi regularly run into problems with it :).

MSSQL keeps track of query statistics and uses those in future planning. SOMETIMES it just so happens that the optimization for the general case makes the outlier 100x slower which kills general performance.

Re: A SQL Heuristic: ORs Are Expensive

#34

Post by sgarland »

renhanxue wrote: post #30
sgarland wrote: post #27

As an aside, MySQL will optimize WHERE IN better than OR, assuming that the predicates are all constants, and not JSON. Specifically, it sorts the IN array and uses binary search. That said, I’m not sure if it would have any impact on this specific query; I’d need to test.

The article is specifically discussing cases where you have predicates on different columns OR'ed together, like col_a = 'foo' OR col_b = 'foo'.

Oof, misread that.

Re: A SQL Heuristic: ORs Are Expensive

#35

Post by jiggawatts »

renhanxue wrote: post #31
Glyptodon wrote: post #16

If optimization is really as simple as applying De Morgan's laws, surely it could be done within the query planner if that really is the main optimization switch? Or am I misreading this somehow? Edit: I guess the main difference is that it's just calculating separate sets and then merging them, which isn't really DeMorgan's, but a calculation approach.

The core issue the article is pointing to is that most database indexes are B-trees, so if you have a predicate on the form (col_a = 'foo' OR col_b = 'foo'), then it is impossible to use a single B-tree lookup to find all rows that match the predicate. You'd have to do two lookups and then merge the sets. Some query optimizers can do that, or at least things that are similar in spirit (e.g. Postgres bitmap index scan…

> but it's much more expensive than a regular index lookup.

It doesn't have to be, it just "is" in some database engines for various historical reasons.

I.e.: PostgreSQL 18 is the first version to support "B-tree Skip Scan" operators: https://neon.com/postgresql/postgresql-18/skip-scan-btree

Other database engines are capable of this kind of thing to various degrees.

Re: A SQL Heuristic: ORs Are Expensive

#36

Post by magicalhippo »

We had a case where a single OR was a massive performance problem on MSSQL, but not at all on Sybase SQLAnywhere we're migrating away from. Which one might consider slightly ironic given the origins of MSSQL...

Anyway, the solution was to manually rewrite the query as a UNION ALL of the two cases which was fast on both. I'm still annoyed though by the fact that MSSQL couldn't just have done that for me.

Re: A SQL Heuristic: ORs Are Expensive

#37

Post by tehjoker »

prein wrote: post #4

This sort of thing is why looking at generated SQL while developing instead of just trusting the ORM to write good queries is so important. I find query planning (and databases in general) to be very difficult to reason about, basically magic. Does anyone have some recommended reading or advice?

Query Planners were considered "AI", at least among some folks, back in the day just FYI

Re: A SQL Heuristic: ORs Are Expensive

#38

Post by jayd16 »

cogman10 wrote: post #33
Animats wrote: post #15

The query optimizer knows how many items are in each index, but has no advance idea how many items will be in the result of a JOIN. An "a OR b" query on a table with millions of rows might have three hits on A, or millions of hits. The optimal query strategy for the two cases is very different. Has anyone put machine learning in an SQL query optimizer yet?

> Has anyone put machine learning in an SQL query optimizer yet? Yes, I think everyone has? At very least I know that MSSQL has because we semi regularly run into problems with it :). MSSQL keeps track of query statistics and uses those in future planning. SOMETIMES it just so happens that the optimization for the general case makes the outlier 100x slower which kills general performance.

At 100x, it seems like you could run both optimal strategies every time, let them race, and still come out way ahead.

Re: A SQL Heuristic: ORs Are Expensive

#39

Post by getnormality »

magicalhippo wrote: post #36

We had a case where a single OR was a massive performance problem on MSSQL, but not at all on Sybase SQLAnywhere we're migrating away from. Which one might consider slightly ironic given the origins of MSSQL... Anyway, the solution was to manually rewrite the query as a UNION ALL of the two cases which was fast on both. I'm still annoyed though by the fact that MSSQL couldn't just have done that for me.

I am very grateful for databases but I have so many stories of having to manhandle them into doing what seems like it should be obvious to a reasonable query optimizer. Writing one must be very hard.

Re: A SQL Heuristic: ORs Are Expensive

#40

Post by cogman10 »

jayd16 wrote: post #38
cogman10 wrote: post #33

Earlier quoted context omitted.

> Has anyone put machine learning in an SQL query optimizer yet? Yes, I think everyone has? At very least I know that MSSQL has because we semi regularly run into problems with it :). MSSQL keeps track of query statistics and uses those in future planning. SOMETIMES it just so happens that the optimization for the general case makes the outlier 100x slower which kills general performance.

At 100x, it seems like you could run both optimal strategies every time, let them race, and still come out way ahead.

You double + the IO and potentially CPU time which is why this isn't done. It's also not always 100x, that just happens often enough. Sometimes it's only 2x or 1.5x. It's impossible to know which situation you are in and the hard thing is the outliers will be slow either way.
Post reply on HN