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

71–80 of 82 posts

Re: A SQL Heuristic: ORs Are Expensive

#71

Post by magicalhippo »

dspillett wrote: post #56
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.

One thing to be careful of with the UNION ALL method, is that if you have some rows that match more than one of the clauses in your set of ORs then you will have duplicate results to screen out. This won't happen if you are checking for multiple values in one field, obviously, but is something to be wary of when using this method to optimise kitchen sink queries more generally. Slapping a DISTINCT in isn't the answer…

Good point. In the described case the OR terms were guaranteed to be disjoint, in a way the query planner could easily figure out. Which Sybase's planner did.

However for cases like described in the article, you'd need to handle that.

While I like CTEs, I've had more consistent luck with subqueries. They also compose more easily.

Re: A SQL Heuristic: ORs Are Expensive

#72

Post by alterom »

contravariant wrote: post #32
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.

Inclusion-exclusion is just the generalization of De Morgan's law for more than 2 sets.

And the example shows exactly two sets.

So it's exactly De Morgan's law.

Re: A SQL Heuristic: ORs Are Expensive

#73

Post by datadrivenangel »

VladVladikoff wrote: post #64

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.

And the nice thing about this is that a SQL query can easily be tested to see if optimizations change the outputs!

Re: A SQL Heuristic: ORs Are Expensive

#74

Post by nitwit005 »

ulrikrasmussen wrote: post #53

I am split on SQL. On one hand I love the declarative approach and the fact that I can improve the run-time complexity of my queries just by adding an index and leaving the queries as is. On the other hand, I hate how the run-time complexity of my queries can suddenly go from linear to quadratic if the statistics are not up to date and my query planner misjudges the amount of rows returned by a complex sub-query so i…

That's less a SQL issue, than a general issue with attempting to optimize based off of heuristics. Generally when "hints" are supported that's what'll happen every time (baring the hint not being executable).

But, remember that a lot of users wanting to query things aren't going to be app developers. They'll be wanting to do a one off query or run some report. You'll tend to need an optimizer no matter what.

Re: A SQL Heuristic: ORs Are Expensive

#76

Post by Tostino »

ethanseal wrote: post #46
johnthescott wrote: post #41

Earlier quoted context omitted.

could you elaborate on pg not really having matviews?

Materialized views in Postgres don't update incrementally as the data in the relevant tables updates.^1 In order to keep it up to date, the developer has to tell postgres to refresh the data and postgres will do all the work from scratch. Incremental Materialized views are _hard_. This^2 article goes through how Materialize does it. MSSQL does it really well from what I understand. They only have a few restrictions,…

As somebody who implemented manual incremental materialized tables using triggers, yeah it's pretty dang hard to make sure you get all the edge cases in which the data can mutate.

Re: A SQL Heuristic: ORs Are Expensive

#77

Post by jiggawatts »

zbentley wrote: post #62
jiggawatts wrote: post #35

Earlier quoted context omitted.

> 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 beg…

Skip-scan or similar code can solve the problem if you have a compound index on both columns.

The query planner can include the entire matching range for the 'A' column and check the 'B' column for matches via skip-scan.

This is possible in principle, but I don't believe most (any?) database engines use this specific approach.

It could be optimal if the results are required in A,B sorted order.

Re: A SQL Heuristic: ORs Are Expensive

#78

Post by magicalhippo »

hans_castorp wrote: post #65
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.

Ah that makes sense, thanks for the correction. I first heard it from my colleague, and probably mixed it up due to the anywhere name when checking out Wikipedia later.

Re: A SQL Heuristic: ORs Are Expensive

#79

Post by ulrikrasmussen »

nitwit005 wrote: post #74
ulrikrasmussen wrote: post #53

I am split on SQL. On one hand I love the declarative approach and the fact that I can improve the run-time complexity of my queries just by adding an index and leaving the queries as is. On the other hand, I hate how the run-time complexity of my queries can suddenly go from linear to quadratic if the statistics are not up to date and my query planner misjudges the amount of rows returned by a complex sub-query so i…

That's less a SQL issue, than a general issue with attempting to optimize based off of heuristics. Generally when "hints" are supported that's what'll happen every time (baring the hint not being executable). But, remember that a lot of users wanting to query things aren't going to be app developers. They'll be wanting to do a one off query or run some report. You'll tend to need an optimizer no matter what.

That's true, and you probably want both. You want a general purpose query planner for any user-generated one-off queries, but for the hot application code paths where you execute the same fixed queries again and again, you may be interested in stronger guarantees about your run time complexity.

Re: A SQL Heuristic: ORs Are Expensive

#80

Post by jononor »

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…

This highlights that there is space for an offline automated query omptimizer/rewriter, to compliment the online query planning?
Post reply on HN