A SQL Heuristic: Ors Are Expensive

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

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

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

Query Planners were considered "AI", at least among some folks, back in the day just FYI

ORM often produces horrible queries that are impossible for humans to digest. I think there are two factors. First, queries are constructed incrementally and mechanically. There is no an overview for the generator to understand what developers want to compute, or no channel for developers to specify the intention. I anticipant this will change w/ AI in the near future. Second, ORM models data following the dogmatic data normalization, on which queries are destined to be horrible. I believe that people should take a moment to view their data, think what computations they want to do on top, estimate how expensive they may be, and finally settle on a reasonable model overall. Ask ORM (or maybe AI) to help with constructing and sending queries and assembling results. But do not delegate data modeling out. With right data modeling that fits computations, queries cann't be that bad.

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

https://pages.cs.wisc.edu/~dbbook/ is a great overview, specifically chapters 13 and 14 on query optimization. it is difficult to reason about though, and every compiler is different. it takes time and enough examples to look at a query and have an intuition for what the plan should look like, and if there's something the compiler is not handling well.

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.

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

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

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

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

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.

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

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.

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.

SQLite3 turns ORs into UNIONs.

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

I think creating alternative plans is easy, knowing which one will be the fastest is the hard part.

So add a comment. “X is easier to understand” shouldn’t mean taking a 100x performance hit.

The article is specifically discussing cases where you have predicates on different columns OR'ed together, like col_a = 'foo' OR col_b = 'foo'.

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.

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, if it was then you'd just use UNION instead of UNION ALL, because that often makes the query planner call for a lot of excess work to be done. I once found that wrapping and main kitchen sink in a CTE and applying DISTINCT in the SELECT that calls it has the desired effect, but that is risky as it relies on undefined behaviour that may change at a later date and tank your performance. If the number of rows being returned is never going to be large, and your situation allows multiple statements, a safer option is to pull the data into a temporary table and SELECT from that with DISTINCT. Or you could de-dupe in the next layer instead of the DB, or just accept dupes if exact cardinality isn't important and your users aren't going to care about the occasional double-row (i.e. a simple quick-search feature).

And, of course, sometimes you want the duplicates, again maybe in the case of a quick search feature (where you split the results into categories and each duplicate of a row is likely in a different category, especially if the categories align with the search clauses that are being ORed).

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.

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

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

I've had the same thought. I would be interested in a query language which allows me to write a query plan, including explicitly scanning indexes using specific methods.

I like the "plumbing on the outside" approach of databases like ClickHouse where you have to know the performance characteristics of the query execution engine to design performant schemas and queries.

The challenge here is that query planners are quite good at determining the best access path based on statistical information about the data. For example, "id = 1" should probably use a fast index scan because it's a point query with a single row, but "category = 42" might be have a million rows with the value 42 and would be faster with a sequential scan. But the problem doesn't surface until you have that much data. Query planners adapt to scale, while a hard-coded query plan wouldn't. That's not even getting started on things like joins (where join side order matters a lot) and index scans on multiple columns.

I'm not aware of any systems that are like this. Some of the early database systems (ISAM/VSAM, hierarchical databases like CODASYL) were a bit like this, before the relational model allowed a single unified data paradigm to be expressed as a general-purpose query language.

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.

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

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