Hacker News Reader

Comment by onlyrealcuzzo | Hacker News Reader

Does anyone with enough db experience know why the engine can't figure it out? Is it easy to explain?

I'm not a db expert, but this seems like something that should be solvable.

Yeah agreed, at the very least the thing should be able to conceive to switch to this... lets call it "WHERE unrolling" internally when asked for " WHERE id IN (x, y, z)"

I'd be delighted to learn what's going on

Where unrolling is an excellent term, thanks.

The best I can understand is the engines are (or were) just not setup so they can do repeated single key lookups, which is really the right strategy for a where in. As a result, they do some kind of scan, which looks at a lot more data.

The problem is these repeated single key lookups are random io for the database engine. So the database engine has to predict a threshold for when a scan or random io is cheaper which is very hard to get right, and your io layer changes this threshold drastically. A spinning disk may be faster all the time with sequential io, and for flash based systems theres a wide variety of performance profiles.

To tackle this problem postgresql has a setting where you can tune the cost factor for random io.

As an aside, this setting is almost certainly too high for you by default. The default of random_page_cost=4 assumes that random pages are 4 times more expensive to read than sequential pages, but with SSDs this cost is much much lower and chances are you're using an SSD these days.

I managed to speed up queries by about 10x by just adjusting this. One Weird Trick To Speed Up Your PostgreSQL And Put DBAs Out Of a Job!

Thanks for the hint. I wonder where the value of 4 comes from. Is this an old value derived from a (then) fast RAID across many spinning rust disks? As you pointed out, today --- using SSDs -- the cost should be lower; I'd think in some cases (e.g. here a DB used for a catalog of a back-up system) the backing store is exactly one spinning rust drive, where I'd expect a much higher cost for random access (about 80MB/s / (100/s*8KiB)).

Ah, [1] has the answer: they acknowledge that random accesses might be much slower, but expect a good share of accesses to be satisfied by the cache (that'll be a combination of various caches).

[1] https://www.postgresql.org/docs/13/runtime-config-query.html

https://postgresqlco.nf/doc/en/param/ is a pretty good additional resource on these kind of things by the way, e.g. https://postgresqlco.nf/doc/en/param/random_page_cost/

That one is annoying. IN tends to be implemented as a loop. I've spend many queries up by putting an IN into a temporary table, then joining it.

I have actually seen it be a win to combine it like this:

    SELECT ...
    FROM foo
      JOIN (
        select 'a' as value
          union all
        select 'b' as value
          ...
      ) bar

In the tests I've done, WHERE id IN (x,y,z) was unrolled as WHERE id = x OR id = y OR id = z. It is fine if the list is short, I had to find solutions when a developer in my team built a dynamic query where the IN list had ~ 4000 elements. A JOIN solved the problem fast and easy in that particular case.

if you need to do very large "IN" clauses, one option can be a global temporary table where you preload values, so instead of doing an IN you do a join against the GTT.

I'm not a db expert, but this seems like something that should be solvable.

It is very highly database specific. MySQL tends to be terrible. PostgreSQL tends to be quite good. The reasons why it did not figure it out in particular cases tend to be complicated.

Except for MySQL, in which case the problem is simple. There is a tradeoff between time spent optimizing a query and time spent running it. Other databases assume that you prepare a query and then use it many times so can spend time on optimizations. MySQL has an application base of people who prepare and use queries just once. Which means that they use simple heuristics and can't afford the overhead of a complex search for a better plan.

"MySQL has an application base of people who prepare and use queries just once". Is it really likely that mysql is unique in its usage patterns? Isn't it more likely that the devs have decided to keep things simple because that's the historical story for mysql. For example it originally didn't even support foreign key constraints if I recall correctly (that's a while ago now of course).

> "MySQL has an application base of people who prepare and use queries just once". Is it really likely that mysql is unique in its usage patterns?

It's quite plausible that it is distinct in the usage patterns it has chosen to optimize for, and that that design choice has been instrumental in determining what use cases it became popular for and which use cases led people to migrate off of it for a different engine, yes.

To the extent that is at play here it is somewhat of an oversimplification (even if the target audience was a factor in the sewing decision) to describe that as simple unidirectional causation from usage to design, and possibly more accurate (though still oversimplified) the other way around.

Yeah, I'm pretty sure that it is unique to MySQL and SQLite.

Back in the 90s and early 2000s, MySQL told people to just run queries. PHP encouraged the same.

Every other database was competing on ability to run complex queries. And so it became common knowledge that applications written for MySQL didn't port well to, say, Oracle. Exactly because of this issue.

Those applications and more like them are out there. And mostly expect to run on MySQL. So that use case has to be supported.

I agree on MySQL but hard disagree on SQLite because the API makes it rather obvious very quickly to any developer that there is a benefit to preparing beforehand.

I was under the impression that mysql wss smart enough to skip parts of the range that isn't needed. https://dev.mysql.com/doc/refman/8.0/en/range-optimization.h...

> It is very highly database specific.

I was about to comment the same thing. Every engine has its quirks, and the programmer learns them over time. I went from years on MSSQL to MySQL and it was a bit rough to be generous. But now I know many of the MySQL quirks and it's fine.

I imagine its bad query optimizer doing the wrong thing. Maybe a different db engine would do better.

I dont like it when people who cannot write efficient SQL/design efficient database schema start blaming "bad" query optimizer.

pro SQL developers extremely rarely have a problem with query optimizer, and when they have it is extremely exotic.

it is usually ORM users that have a problem with SQL performance and blame the optimizer

The comment i'm responding to is asking why two equivalent queries have different runtimes. The answer pretty obviously is because the optimizer is smart enough to chose the best query plan in one case and not the other. I think its fairly obvious that in theory a better optimizer could figure out the right plan in both cases.

That's not to say that its impossible to work around or that in a real application that you would ever be "stuck" by this. At the end of the day you deal with the software you have, but the optimizer can still have weaknesses without it totally derailing your app.

the optimizer is constrained, it still has to give you what you asked for. i can't even translate into english what's being asked for in query #2 but it's only a coincidence that it has the same result as the more precise and correct thing being asked for in the final query.

There are two possible cases:

a) with everything known to the database (i.e. ids not null) the two queries produce the same result.

b) for some contents of the schema the results differ, but in the presented case some additional condition (not known to the db) holds that makes them equivalent.

Only in case b) it can be called coincidence. In case a) it’s fair to ask if the optimizer can’t do better. After all it tries to avoid cartesian products for simple joins even though that’s the text book definition.

“Not worth” to improve the optimizer is still a valid answer.

the query in question is definitely case b - it's a group by query with an explicit granularity, there's just no actual aggregates being asked for but the very presence or absence of a row in the results carries some meaning. the explicit grain is something like employee markouts plus customers from stores with at least one employee without markouts.

I agree they shouldn't start there, but you don't necessarily need exotic queries to run into edge cases that work differently across say MySQL, MSSQL, and Oracle. The classic example being exists vs left join null.

There could be a lot of reasons that are highly engine dependent, for this specific case.

A general answer, perhaps... not specific to the case you've specified.

Query optimization is a science with multiple dimensions [1]. I'd wager every problem in computer science plays a role somehow in query optimization.

Query performance is based on a combination of actions you take to optimize the design of your system to get the best performance (e.g. data modelling, index design, hardware, query style, and more), and the patterns the system can recognize based on your inputs and the data itself, with the resources it has available, to optimize your queries.

There are known patterns for optimization that are discovered over the years, many hard learned from practical experience. This is why older "popular" engines sometimes are more mature and more performant - they have optimizations built for the common use cases over long periods of time. That is not to say older engines are always better, just that they have often had more exposure to the variety of problems that occur.

The reason why the engine "can't figure it out" is that most engines, even the best ones, are quite complex - combinations of known rules as well as more fuzzy logic, where the engine uses a combination of information and heuristics to essentially explore a possible solution space, to try to find the optimal execution plan. Making the right decision, well, can be difficult and given the nature of these things, sometimes the optimizer makes the wrong decision (this is why "hints" exist, sometimes, you can force the optimizer to do what you see is obvious - but this is suboptimal for you).

In some cases, finding an optimal execution plan can actually be quite computationally expensive, and/or quite time consuming, or the engine in question may simply have no logic coded to handle the case. Optimization is all about finding the balance between finding the most performant query plan, but in the least amount of time, with the least computational and I/O impact to the overall system, that returns the right result. Optimizers are also highly depending on the capabilities of the engineering teams that build them.

It is not an easy problem, and it is an area which one could liken to almost machine learning/artificial intelligence, in one way. There are so many possible options, the problem space so big, with so many different ways to approach a given scenario, that it can be difficult for the "engine" to decide.

This is why known patterns were created, for example, dimensional data models for analytical queries vs. 3rd normal form. Dimensional data models enable certain optimizations, for example, star schemas [2]. If you take a combination of implementing known patterns, along with optimizers written by engineers that exploit those patterns, you can get to a world of better performance.

However, in a world that is, let's say.. more "open ended" - for example, the world of data in a "data lake", where data models are not optimized, data comes in unpredictable multiple shapes/sizes, then it often comes down to combinations of elegant/complex engines that can interpret the shapes of data, cardinality, and other characteristics, make use of much larger distributed compute and system performance, and in some cases - often brute force to arrive at the best query plan or performance possible.

There are so many levels of optimization.. for example, if you were to look at things like Trino [3], which started its genesis as PrestoDb in Facebook - you will see special CPU optimizations (e.g. SIMD instructions), vectorized/pipelined operations - there are storage engine optimizations, memory optimizations, etc. etc. It truly is a complex and fascinating problem.

Source: I was a technical product manager for a federated query engine.

[1] https://en.wikipedia.org/wiki/Query_optimization

[2] https://en.wikipedia.org/wiki/Star_schema

[3] https://trino.io/

Reply on news.ycombinator.com