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

41–50 of 82 posts

Re: A SQL Heuristic: ORs Are Expensive

#41

Post by johnthescott »

ethanseal wrote: post #25
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...

could you elaborate on pg not really having matviews?

Re: A SQL Heuristic: ORs Are Expensive

#42

Post by swasheck »

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.

disjunctions and stats could be a pretty nasty combination in mssql. i think it got a bit better ca. 2016 with the CE updates, but i’ve had quite a few occurrences where the solutions were the union all approach

Re: A SQL Heuristic: ORs Are Expensive

#43

Post by progmetaldev »

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?

If you are looking to squeeze every ounce of performance from your entire application stack, I'd say you should be looking at everything your ORM produces. The ORM is basically to speed up your developers time to production, but most ORMs will have some cases where they generate terrible SQL, and you can usually run your own SQL in a stored procedure if the generated SQL is sub-optimal. I've done this quite a few times with Microsoft's Entity Framework, but as new versions come out, it's become less common for me to have to do this. Usually I need to drop to a stored procedure for code that allows searching a large number of columns, in addition to sorting on all the columns that display. I also use stored procedures for multi-table joins with a WHERE clause, when using Entity Framework. You still need to look at your generated queries, but the code is nothing like it used to be under Entity Framework under the .NET Framework (at least in my experience - YMMV - you should never just let your ORM create SQL without reviewing what it is coming up with).

Re: A SQL Heuristic: ORs Are Expensive

#44

Post by progmetaldev »

ethanseal wrote: post #24
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.

This website taught me a ton, even after I thought I knew more than enough about performance. Just seeing how different databases generate and execute their SQL is a huge boon (and sometimes extremely surprising when looking at one DBMS to another).

Re: A SQL Heuristic: ORs Are Expensive

#45

Post by cameronh90 »

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.

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. Combined with pessimistic locking, we ended up with far more overnight support calls from the MSSQL backend than from the PGSQL backend. Usually because it suddenly decided to switch query plan at 1AM.

I wonder if there's a trade-off where an optimizer produces better average query plans but worse outliers.

Re: A SQL Heuristic: ORs Are Expensive

#46

Post by ethanseal »

johnthescott wrote: post #41
ethanseal wrote: post #25

Earlier quoted context omitted.

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

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, though I've never used a MSSQL materialized view in production.^3

[1]: https://www.postgresql.org/docs/current/rules-materializedvi... [2]: https://www.scattered-thoughts.net/writing/materialize-decor... [3]: https://learn.microsoft.com/en-us/sql/t-sql/statements/creat...

Re: A SQL Heuristic: ORs Are Expensive

#47

Post by cryptonector »

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.

SQLite3 turns ORs into UNIONs.

Re: A SQL Heuristic: ORs Are Expensive

#48

Post by frollogaston »

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.

Postgres sometimes handles this for you, but I'm not sure exactly when it's able to do that, so I do UNION ALL.

Re: A SQL Heuristic: ORs Are Expensive

#49

Post by magicalhippo »

cameronh90 wrote: post #45
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.

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

Re: A SQL Heuristic: ORs Are Expensive

#50

Post by nasretdinov »

getnormality wrote: post #39
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.

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 :)
Post reply on HN