As someone who has worked with Postgres for 15 years and also has spent most of my career modeling and solving mathematical optimization problems, I have so much to say on this topic, but I'll leave it at these three points:
* Every optimization problem needs data on costs, and the more and better the data is, the better. Postgres has made some improvements here, especially with cross column statistics, but there are still massive improvements left on the table. The most glaring omission is data on syscall latencies. Reading a page from disk has dramatically different latencies from system to system, and postgres still relies on configuration values for these costs, when it could very easily be measuring them. Another omission is foreign key statistics. Joins along foreign keys should never have a bad plan, but they still occasionally do.
* Deferred or alternative scenario planning should be adopted, especially for large and expensive queries. As it is today, your plan is finalized before it is executed, even though earlier stages of execution could provide information (like rowcounts or cardinality estimates) that could dramatically improve later stage plans.
* Machine learning most definitely could be an area where improvements could be made, but I've been unimpressed with the efforts that Ive seen. Don't use machine learning for planning, use machine learning for cost discovery and estimation. Build better cost models, and then let the optimization engine work with that data.
I'm curious to hear a bit more of your opinion. For example, I'm surprised that syscall latency is something near the top of your list. I think the usual wisdom in the DB community is that the cost models are mostly fine, but the cardinality estimation is really bad.
In terms of the deferred / alternative planning, do you think adaptive query execution is a reasonable way to achieve this? It certainly allows for information early in the query execution to impact later plans. My worry with these approaches is that if you get the first couple of joins wrong (which is not uncommon), unless you have something like Yannakakis/SIPs, you still can't recover.
I am obviously biased on the whole "ML for query optimization" thing. One thing I would note is that every "ML for planning" approach I've seen does, under the hood, use ML for cost discovery/estimation. These approaches are just trying to balance the data they collect (exploration) with the quality of the plans they produce (exploitation). Interestingly, if you use ML in a way that is completely removed from planning, you actually get worse query plans despite more accurate estimates: https://people.csail.mit.edu/tatbul/publications/flowloss_vl... (again, I've got a horse in this race, so my opinion should come with a side of salt :D)
As a DBA I have a very hard time properly tuning parameters like random_page_cost and the default of 4.0 is no longer applicable for most database servers.
I don't want to be tuning this, it takes a lot of time to do it properly and I haven't retested this in a long time. I just set something that has worked in the past which is probably bad.
I completely agree that Postgres should be able to figure this out on its own. This is just an example, there are more such parameters which should be adjusted to the hardware but most people will leave the defaults.
Syscall latency was a much bigger deal back when we had spinning disks, but it still matters today (you can get dramatically different plans depending on slightly different costs of pulling a page from disk) and I find it silly that we've never even measured our those costs. A bigger impact might be for SQL functions...all of the Postgres SQL functions have configured cost values, but they could easily be measured. Also a simple cost model for functions can be a dramatic oversimplification. For example, some PostGIS functions have O(n) or O(n^x) behavior depending on the size and complexity of the input geometry. If we could measure exact costs, or model costs with statistical distributions, or possibly predict with ML, that would be a huge improvement.
My opinion on ML is that there is nothing in the execution planning side that couldn't be modeled and solved as a linear program, with extremely fast and mathematically-optimal results. By trying to use ML for the planning part, you're really just using ML to reverse engineer LP solvers, and it is a poor use of the compute resources.
The reason why some ML planners might have better results than typical SQL query planners is because typical SQL engines are optimized towards OLTP workloads that require small transactions executed very quickly. In order to do that, they purposefully don't explore the true planning space...they might explore 3-10 alternative ways of executing, whereas there might be hundreds or thousands of ways to do the same thing. While Postgres has explicitly chosen to not implement planning pragmas to override planner behavior, it would be really cool if you could have multiple planners optimized for different types of workloads, and be able to explicitly choose a query planner that takes 3 seconds to plan for a query that takes 1hr to execute and for which a better plan could save several minutes. I would even love a fairly naive query planner which does index scans for a deterministic and exact cardinality before planning joins.
BTW, I really like your blog and your research focuses. You're working on exceptionally hard problems that have a huge impact on computing.
Where I think ML would be much better than what we (postgres) do, is iteratively improving selectivity estimation. In today's postgres there's zero feedback from noticing at runtime that the collected statistics lead to bad estimates. In a better world we'd use that knowledge to improve future selectivity estimates.
> In order to do that, they purposefully don't explore the true planning space...they might explore 3-10 alternative ways of executing, whereas there might be hundreds or thousands of ways to do the same thing.
FWIW, often postgres' planner explores many more plan shapes than that (although not as complete plans, different subproblems are compared on a cost basis).
> While Postgres has explicitly chosen to not implement planning pragmas to override planner behavior, it would be really cool if you could have multiple planners optimized for different types of workloads,
FWIW, it's fully customizable by extensions. There's a hook to take over planning, and that can still invoke postgres' normal planner if the query isn't applicable. Obviously that's not the same as actually providing pragmas.
My guess is that the reason for putting syscall latency high is that it should be easy to fix. Cardinality tracking is a hard problem, but running a loop on install that measures the cost of a couple dozen syscalls really could be done automatically.
> Deferred or alternative scenario planning should be adopted, especially for large and expensive queries. As it is today, your plan is finalized before it is executed, even though earlier stages of execution could provide information (like rowcounts or cardinality estimates) that could dramatically improve later stage plans.
Alternative planning sounds awesome. I saw a query plan the other day where it expected about 1000 rows from some subquery so did a nested loop to an index scan. In reality there’s about a billion rows. I’m not sure yet why the estimate was so bad, but being able to pivot from a nested loop to a hash join if the row count crossed some threshold would be great at avoiding some catastrophic plans.
Having a foreign key should probably be a hint to the planner that it should create a cross-table correlation estimate on the source and destination columns. This is about join cardinality estimation, not having an index.
It's not about indexing, though most casual users don't know that FKs are not indexed automatically. Postgres should be smart enough to know when an index is appropriate for a foreign key, but I respect the fact that the core team wants people to make explicit well-reasoned decisions to index instead of doing it automatically.
Regardless of indexing, what actually matters is cardinality estimates. Foreign keys are almost always a reasonable hint to the SQL engine that there will be a large number of joins along foreign keys, and thus should be able to provide cross-table cardinality estimates.
* Every optimization problem needs data on costs, and the more and better the data is, the better. Postgres has made some improvements here, especially with cross column statistics, but there are still massive improvements left on the table. The most glaring omission is data on syscall latencies. Reading a page from disk has dramatically different latencies from system to system, and postgres still relies on configuration values for these costs, when it could very easily be measuring them. Another omission is foreign key statistics. Joins along foreign keys should never have a bad plan, but they still occasionally do.
* Deferred or alternative scenario planning should be adopted, especially for large and expensive queries. As it is today, your plan is finalized before it is executed, even though earlier stages of execution could provide information (like rowcounts or cardinality estimates) that could dramatically improve later stage plans.
* Machine learning most definitely could be an area where improvements could be made, but I've been unimpressed with the efforts that Ive seen. Don't use machine learning for planning, use machine learning for cost discovery and estimation. Build better cost models, and then let the optimization engine work with that data.