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

61–70 of 82 posts

Re: A SQL Heuristic: ORs Are Expensive

#61

Post by renhanxue »

jiggawatts wrote: post #35
renhanxue wrote: post #31

Earlier quoted context omitted.

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.

B-tree skip scan does not address the problem in the article at all.

Re: A SQL Heuristic: ORs Are Expensive

#62

Post by zbentley »

jiggawatts wrote: post #35
renhanxue wrote: post #31

Earlier quoted context omitted.

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.

The linked article’s optimization applies to compound index queries, not “OR” condition optimization.

Unrelated or not, skip-scan will be useful in some cases. However, the cases where it adds noticeable benefit are the cases where a separate index should have been used for leading columns anyway (and in memory-constrained/frequently-cold-cache situations, a separate index might even be faster). If you can’t even begin to guess at the order of magnitude of cardinality, or if your leading-column-lacking queries are quite rare and not that perf-sensitive on a big table exerting index cache pressure, then skip scans make sense.

Re: A SQL Heuristic: ORs Are Expensive

#63

Post by zbentley »

magicalhippo wrote: post #49
cameronh90 wrote: post #45

Earlier quoted context omitted.

For a while I was maintaining software that supported both MSSQL and PGSQL, and I found that, when comparing like-for-like without DB-specific tuning, MSSQL produced better query plans on average. On a database without write contention, I'd often see 30% better performance on MSSQL. However, it was also much more likely to hit an AWFUL pathological case which completely wrecked the performance as you describe. Combin…

We're experiencing the same with MSSQL, and for our most important queries have started adding a constant-valued dummy column to the SELECT section which value changes every few minutes. Essentially an integer equal to UNIX time divided by 600 or similar. That way a cached bad plan can't cause issues for more than a few minutes, which is acceptable for our use-case. It's a sledgehammer but it was easy to add and it w…

In Oracle many years ago, we did the same thing by prepending a SQL comment to the query string. You’d think that the plan cacher normalizes queries first, but I guess not.

That might work in your case as well, without requiring modifications in logic to support the dummy field?

Re: A SQL Heuristic: ORs Are Expensive

#64

Post by VladVladikoff »

I absolutely adore LLMs for SQL help. I’m no spring chicken with SQL but so many times now I’ve taken a poorly optimized query, run it with ‘explain’ in front of it, and dumped it into an LLM asking to improve performance, and the results are really great! Performance vastly improved and I have yet seen it make a single mistake.

Re: A SQL Heuristic: ORs Are Expensive

#65

Post by hans_castorp »

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.

SQL Anywhere doesn't really have "Sybase" roots.

It started out as Watcom SQL, then after Watcom was acquired by PowerSoft, it was renamed to "SQL Anywhere".

After Sybase acquired PowerSoft it was later renamed to "Adaptive Server Anywhere". I think SAP renamed it back to "SQL Anywhere" after they acquired Sybase.

Re: A SQL Heuristic: ORs Are Expensive

#66

Post by hans_castorp »

Not sure on which Postgres version this was tested with, but the first example runs in about 2ms with my Postgres 17 installation ("cold cache"). It uses a BitmapOr on the two defined indexes.

https://notebin.de/?5ff1d00b292e1cd5#AU4Gg8hnY6RAmS9LoZ18xWn...

This used the setup.sql from the linked GitHub repository.

Re: A SQL Heuristic: ORs Are Expensive

#67

Post by ethanseal »

hans_castorp wrote: post #66

Not sure on which Postgres version this was tested with, but the first example runs in about 2ms with my Postgres 17 installation ("cold cache"). It uses a BitmapOr on the two defined indexes. https://notebin.de/?5ff1d00b292e1cd5#AU4Gg8hnY6RAmS9LoZ18xWn... This used the setup.sql from the linked GitHub repository.

When you say cold cache, did you clear the os page cache as well as the postgres buffercaches? After setup.sql, the cache will be warmish - I get 4ms on the first run. I'm using postgres 17.5

See https://github.com/ethan-seal/ors_expensive/blob/main/benchm... where I use dd to clear the os page cache.

This article by pganalyze talks about it: https://pganalyze.com/blog/5mins-postgres-17-pg-buffercache-...

Re: A SQL Heuristic: ORs Are Expensive

#68

Post by nasretdinov »

dspillett wrote: post #58
nasretdinov wrote: post #50

Earlier quoted context omitted.

If an optimiser was as smart as a human it would take potentially minutes to come up with a (reasonably good) SQL execution plan for any non-trivial query :)

> it would take potentially minutes This is a key part of the problem, and something that people don't realise about query planners. The goal of the planner is not to find the best query plan no matter what, or even to find the best plan at all, it is instead to try to find a good enough plan quickly . The QPs two constraints (find something good enough, do so very quickly) are often diametrically opposed. It must be…

Yeah, exactly. You need to optimise for the overall query duration, including the optimiser itself, and obviously everyone's workload is different, so the right balance may as well not exist at all

Re: A SQL Heuristic: ORs Are Expensive

#69

Post by hans_castorp »

ethanseal wrote: post #67
hans_castorp wrote: post #66

Not sure on which Postgres version this was tested with, but the first example runs in about 2ms with my Postgres 17 installation ("cold cache"). It uses a BitmapOr on the two defined indexes. https://notebin.de/?5ff1d00b292e1cd5#AU4Gg8hnY6RAmS9LoZ18xWn... This used the setup.sql from the linked GitHub repository.

When you say cold cache, did you clear the os page cache as well as the postgres buffercaches? After setup.sql, the cache will be warmish - I get 4ms on the first run. I'm using postgres 17.5 See https://github.com/ethan-seal/ors_expensive/blob/main/benchm... where I use dd to clear the os page cache. This article by pganalyze talks about it: https://pganalyze.com/blog/5mins-postgres-17-pg-buffercache-...

I did not explicitly evict the Postgres buffer cache, but using pg_buffercache to evict all buffers for the table, yields a runtime of 23ms for me (still going for the BitmapOr).

https://notebin.de/?ac3fcf55e6850f47#ERXndRrqp3X4zEWX5EC3dZU...

Which plan does Postgres choose in your case that results 100ms?

Re: A SQL Heuristic: ORs Are Expensive

#70

Post by ethanseal »

hans_castorp wrote: post #69
ethanseal wrote: post #67

Earlier quoted context omitted.

When you say cold cache, did you clear the os page cache as well as the postgres buffercaches? After setup.sql, the cache will be warmish - I get 4ms on the first run. I'm using postgres 17.5 See https://github.com/ethan-seal/ors_expensive/blob/main/benchm... where I use dd to clear the os page cache. This article by pganalyze talks about it: https://pganalyze.com/blog/5mins-postgres-17-pg-buffercache-...

I did not explicitly evict the Postgres buffer cache, but using pg_buffercache to evict all buffers for the table, yields a runtime of 23ms for me (still going for the BitmapOr). https://notebin.de/?ac3fcf55e6850f47#ERXndRrqp3X4zEWX5EC3dZU... Which plan does Postgres choose in your case that results 100ms?

Exactly the same one from what I see: https://github.com/ethan-seal/ors_expensive/blob/main/explai...

Given the buffer reads seem close to yours, I believe it's page cache.

Post reply on HN