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

11–20 of 82 posts

Re: A SQL Heuristic: ORs Are Expensive

#11

Post by galkk »

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 showing plans and/or checking if the database can be guided is just a bad teaching.

It looks like author discovered a trick and tries to hammer everything into it by overgeneralizing.

Re: A SQL Heuristic: ORs Are Expensive

#12

Post by [deleted] »

jalk wrote: post #9
ethanseal wrote: post #7

Earlier quoted context omitted.

Absolutely. Though I don't recall seeing multiple sequential scans without a self-join or subquery. A basic filter within a sequential scan/loop is the most naive/simplest way of performing queries like these, so postgres falls back to that. Also, fwiw, BitmapOr is only used with indexes: https://pganalyze.com/docs/explain/other-nodes/bitmap-or .

That was the extreme case - the multi-scan would be gotten if a casual reader tried your (neat by all means) AND-only query on a non-indexed table (or partially indexed for that matter).

[deleted]

Re: A SQL Heuristic: ORs Are Expensive

#13

Post by ethanseal »

jalk wrote: post #9
ethanseal wrote: post #7

Earlier quoted context omitted.

Absolutely. Though I don't recall seeing multiple sequential scans without a self-join or subquery. A basic filter within a sequential scan/loop is the most naive/simplest way of performing queries like these, so postgres falls back to that. Also, fwiw, BitmapOr is only used with indexes: https://pganalyze.com/docs/explain/other-nodes/bitmap-or .

That was the extreme case - the multi-scan would be gotten if a casual reader tried your (neat by all means) AND-only query on a non-indexed table (or partially indexed for that matter).

Gotcha, I misunderstood your comment. The multiple counts is a definitely very contrived example to demonstrate the overhead of BitmapOr and general risk of sequential scans.

Re: A SQL Heuristic: ORs Are Expensive

#14

Post by to11mtm »

If ORs are expensive you've probably got a poor table design or the ORs are for some form of nasty query that is more UI/Dashboard based.

A good table has the right indexes, and a good API to deal with the table is using the RIGHT indexes in it's criteria to get a good result.

Re: A SQL Heuristic: ORs Are Expensive

#15

Post by Animats »

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?

Re: A SQL Heuristic: ORs Are Expensive

#16

Post by Glyptodon »

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.

Re: A SQL Heuristic: ORs Are Expensive

#17

Post by throwaway81523 »

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?

Some traditional planners try some different plans on random subsets of the data to see which plan works best. Don't need machine learning, just Bayes' rule.

Re: A SQL Heuristic: ORs Are Expensive

#18

Post by ethanseal »

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 optimization that went in the new release of PostgreSQL I'm excited about that may affect this - I'm not sure. See https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit...

Re: A SQL Heuristic: ORs Are Expensive

#19

Post by Sesse__ »

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.

In most cases, the end result is a lot messier than it looks in this minimal example. Consider a case where the query is a 12-way join with a large IN list somewhere (which is essentially an OR); would it still look as attractive to duplicate that 12-way join a thousand times?

There _are_ optimizers that try to represent this kind of AND/OR expression as sets of distinct ranges in order to at least be able to consider whether a thousand different index scans are worth it or not, with rather limited success (it doesn't integrate all that well when you get more than one table, and getting cardinalities for that many index scans can be pretty expensive).

Post reply on HN