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

21–30 of 82 posts

Re: A SQL Heuristic: ORs Are Expensive

#21

Post by Sesse__ »

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?

> 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.

Query optimizers definitely try to estimate cardinalities of joins. It's a really, really hard problem, but the typical estimate is _much_ better than “eh, no idea”.

Re: A SQL Heuristic: ORs Are Expensive

#22

Post by Sesse__ »

ethanseal wrote: post #18
galkk wrote: post #11

I strongly dislike the way the polroblem is presented and the “solution” is promoted. Author mentions merge join with count of top, and if th database supports index merges, it can be extremely efficient in described scenario. There are a lot of real optimizations that can be baked in such merges that author chooses to ignore. The generalized guidance without even mentioning database server as a baseline, without sho…

For sure, there's definitely a lot of cool techniques (and I'm not aware of all of them)! And the first example is very much contrived to show a small example. I'm not super familiar with the term index merge - this seems to be the term for a BitmapOr/BitmapAnd? Is there another optimization I'm missing? The article links to my code for my timings here: https://github.com/ethan-seal/ors_expensive There is an optimiza…

> I'm not super familiar with the term index merge - this seems to be the term for a BitmapOr/BitmapAnd?

Different databases will use similar terms for different operations, but I would guess that the comment refers to something similar to MySQL's index merge (which is essentially reading the row IDs of all the relevant ranges, then deduplicating them, then doing the final scan; it's similar to but less flexible than Postgres' BitmapOr).

Re: A SQL Heuristic: ORs Are Expensive

#23

Post by ethanseal »

Sesse__ wrote: post #22
ethanseal wrote: post #18

Earlier quoted context omitted.

For sure, there's definitely a lot of cool techniques (and I'm not aware of all of them)! And the first example is very much contrived to show a small example. I'm not super familiar with the term index merge - this seems to be the term for a BitmapOr/BitmapAnd? Is there another optimization I'm missing? The article links to my code for my timings here: https://github.com/ethan-seal/ors_expensive There is an optimiza…

> I'm not super familiar with the term index merge - this seems to be the term for a BitmapOr/BitmapAnd? Different databases will use similar terms for different operations, but I would guess that the comment refers to something similar to MySQL's index merge (which is essentially reading the row IDs of all the relevant ranges, then deduplicating them, then doing the final scan; it's similar to but less flexible than…

Cool. I'll have to read up on that.

Re: A SQL Heuristic: ORs Are Expensive

#24

Post by ethanseal »

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?

Highly recommend https://use-the-index-luke.com/

It's very readable - I always ask new hires and interns to read it.

Re: A SQL Heuristic: ORs Are Expensive

#25

Post by ethanseal »

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?

I think having a way to build statistics on the join itself would be helpful for this. Similar to how extended statistics^1 can help when column distributions aren't independent of each other.

But this may require some basic materialized views, which postgres doesn't really have.

[1]: https://www.postgresql.org/docs/current/planner-stats.html#P...

Re: A SQL Heuristic: ORs Are Expensive

#27

Post by sgarland »

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.

Re: A SQL Heuristic: ORs Are Expensive

#28

Post by singron »

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?

There are many papers on ML for query planners. You can search for "Learned Query Optimization". Some use ML just for the cardinality estimation.

Re: A SQL Heuristic: ORs Are Expensive

#29

Post by hobs »

jalk wrote: post #8
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?

It's a big help if you know how to retrieve and interpret execution plans for the database you use.

Yes, I was going to say, seeing the generated SQL can be almost useless depending on the execution plan.

When you have a solid view of the schema and data sizes you can start to be more predictive about what your code will actually do, THEN you can layer on the complexity of the ORM hell code.

Re: A SQL Heuristic: ORs Are Expensive

#30

Post by renhanxue »

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'.
Post reply on HN