I would like to think that pg_hint_plan is designed in such a way that any hint it accepts must be a valid plan for the query. I’m quite confident that schemes with this property that can also express high quality plans are possible and not even excessively complicated.
This is not to say that it’s possible to genetically verify that a proposed algorithm does what you want it to — that would be undecidable or NP-hard or co-NP-hard depending on how you formulate the question.
I wouldn't be very excited about adding a 4B param model to my database deployment, but using this kind of approach while testing an app to identify query plans where Postgres is leaving performance on the table seems valuable without much risk.
Because P!=NP (very probably IMHO) there's a huge class of problem for which LLMs are useful on the expensive and heuristic-y generation side because the verification is relatively inexpensive.
You're misunderstanding the setup here. The LLM doesn't modify the query, just some details about how to choose between different ways to break the query into basic operations on the tables. The SQL doesn't change. It's still up to postgres to guarantee that the results match the query. If the proposed plan were nonsense that didn't amount to carrying out the query, postgres would ignore it.
It's not unusual for us to end up with bad query plans because the shape of our data can vary pretty greatly. In many cases, a Foo has 1 Bar. But in some cases, a Foo has a million Bars. That can cause the query optimizer to treat lookups on the bar table as if there are few elements there (causing a scan instead of a seek).
For the general case, the optimizer gets it right. However, the fringe case is one that causes the entire system to crash. It's a bit akin to how an insertion sort can be faster than quick sort when n is small. The optimizer might make a bad assumption about the size of n which makes it pick an expensive n lookup when log(n) is available (but slower for small n).
I'd like to contribute my amateur hour entry into this thread, although I did administer and develop mssql stuff for awhile.
sure optimizations based on stats, but the stats are the wildcard, in my experience query plans can change suddenly.
Queries are translated into plans according to statistics. However the transforms will be deterministic and should only change one valid plan to another. I could very easily see a neural network manipulate transforms the same way the current programming does, its just that the neural networks are by nature really nicely suitable because the "decisions" are based on training, and this training can be closed world type things like the ai assists that chess engines are now getting. Obviously ai still can't play chess but apparently its very good at ranking board positions just by developing that much statistical info because its training comes not from reading the web, but playing a gazzilian games against itself in a "closed" chess world of its own.
I'm thinking that the ai does "this legal transform of the query plan should be applied to this pattern of data (statistics, cardinality, etc)" simply because the ai encountered it in closed world training, much like the chess thing.
I don't believe that a pure neural network can currently abide by the rules of chess, even with unreasonable amounts of training. Do you have a counter example? I never mind having beliefs challenged with facts lol
edit: I think you could provide an AI with a service or skill that asks "is this move legal" but given all the overhead for llms or whatever to call a "legal move" service external to its process, well then you aren't really searching the tree very efficiently lol.
However if you just let a neural network score boards and the neural network is in the same process well then I think thats the working solution for using neural networks in chess. The net does not need to score all boards either, simple value based heuristics can obviously provide a preliminary list of good boards (moves) at a certain depth or ply and then select the move that produces the board that the neural net scores highest. I kinda sorta think thats whats done today but as usual I could be full of it lol
I paid ~$800 to rent a 2x H100 SXM node from Lambda for ~95 hours, and ~$400 in OpenAI API fees to generate the Astra trajectory demonstrations.
a tiny 4B model went from not being able to understand the harness it was wrapped in, to achieving a 1.81x geometric mean speedup and a summed latency decrease of 44.7% across a workload of join-heavy SQL queries
I can’t find it in the article (may have skimmed it too much), but I suspect they didn’t include those ~95 hours in the benchmark numbers.
I think all database vendors know their query optimizers could do much better if they could afford to spend lots of time to derive query plans.
⇒ this may be useful for some workloads, but even then, can you afford to spend hours every now and then to update your 4B model to ensure it still picks a good query plan?
⇒ this may be useful for some workloads, but even then, can you afford to spend hours every now and then to update your 4B model to ensure it still picks a good query plan?
I think this would be likely comparable to a scheduled backup, so I think it would be an acceptable maintenance window. However, deterministic algorithms would likely beat re-training (or re-fine-tuning) the model. For example, one could analyze actual distributions or whatever (instead of assuming uniform), and then some plans would automatically be eliminated.
Imo a good thought experiment is to look at places that are hyper-optimized, like compilers. Would LLMs bring anything to the table (architecturally or performance-wise) to a piece of software that has been carefully crafted for decades? (Methinks no.)
The Postgres query planner has had to operate, for those same decades, in a much more realtime-sensitive and restricted environment than compilers. It can only draw its conclusions from summary statistics on tables in isolation, not on their relationships with each other (and even less so when filters are involved). For many cases this is fine! For many others it isn't.
I don't think anybody's denying that small models are doing distillation, the issue at hand is frontier lab vs frontier lab when it comes to big models.
You'd be shocked at some of the punishments handed out from various empires over history for offences as minor as stealing an apple. Whether they can claim the moral high ground is not question of ethics but a question of power.
On the flip side, its important to know just how much we would be sacrificing if big frontier gets their way in convincing the courts that distillation is a bad thing
I’ve played with it already. I don’t think this is the use case. I think Jev’s use case is fast, cheap and somewhat easy classification. It’s not trainable in the way you would want here. Even though it’s fast it wont be faster than pgs query optimizer.
At least as I understand things.
How did you plan to use Jev for query optimization?
I am still struggling to understand a use-case for Jev. Isn't what was explained in this article a classification problem? I.e. find and aggregate data?
The number of options has to be small and bounded. The query planning is more of a search/optimization problem than a classification problem since the number of options increases wildly based on query size.
“81% faster query plans than Postgres”…on an 8 GB dataset that fits entirely in memory, with shared_buffers constrained to a fraction of that, queries warmed before measuring, and read-only SELECTs.
I would be cautious about over fitting, it’s tough to say if those query plans would really be more optimal than Postgres heuristics at scale and with a bit more realistic OLTP workloads.
In any case, such is life with profile guided optimization. Many of us appreciate how database workloads can drift over time and with scale.
Kudos to the author for getting their hands dirty and writing up their experiments.
I would think it's possible to make it so that the 4B model only needs to be called during an initial phase, and then the same queries it constructed can just be re-used with values replaced, unless you're generating a lot of unique on-the-fly query shapes.
Optimal plan construction is math-heavy, algorithm-heavy and vary even by workload. There are options like creating just-in-time indexes, so solution space grows even faster than article presents. Sometimes it is the query planner which is the slow part of total execution time.
LLM is kind of blunt weapon to use here. I am waiting rather for alphago style neural net heuristic.
Only in the worst case when the plans are equivalent: If one plan is significantly faster, then it'll finish first, and the loser can get canceled before it finishes.
Good and bad plans can have orders of magnitude performance difference. The bad one can easily do enough damage cutting the performance in half before it is canceled.
Engineer: "HELP, our production DB is frozen on this query that worked fine before!"
Infra: "Hmm, let's check... Well would you look at that, it seems like your LLM query planner usually works and produces fast queries, but this time when you changed a variable name to trigger query rebuild, it happened to hallucinate and miss an index, would you mind re-running the LLM a few times until you get a faster query?"
This was a thoroughly enjoyable read, both the writing and presentation. I really liked the level of writing as it's basically introducing a whole lot of advanced topics but at just the right level for a non-AI researcher type of engineer like myself to be able to understand what's going on, and I felt it made some elements of LLMs actually something I could understand rather than wizardry done by maths PhDs. Probably because it's more like applied engineering rather than hard mathematics here. Thank you for a delightful post.
But how will you know that the query plan actually does what your query asked for?
"... make no mistakes" :)
I imagine you can perform operations on query plans to transform them and determine equivalence?
`pg_hint_plan` has a debug log so you can verify Postgres actually used the hint or not! Used this during evaluations
I would like to think that pg_hint_plan is designed in such a way that any hint it accepts must be a valid plan for the query. I’m quite confident that schemes with this property that can also express high quality plans are possible and not even excessively complicated.
This is not to say that it’s possible to genetically verify that a proposed algorithm does what you want it to — that would be undecidable or NP-hard or co-NP-hard depending on how you formulate the question.
I wouldn't be very excited about adding a 4B param model to my database deployment, but using this kind of approach while testing an app to identify query plans where Postgres is leaving performance on the table seems valuable without much risk.
Given the approach from the article, you can commit the hints to git and run tests for verification. The model would be used during coding.
Because P!=NP (very probably IMHO) there's a huge class of problem for which LLMs are useful on the expensive and heuristic-y generation side because the verification is relatively inexpensive.
you'll have to prove equivalence through some Lean4 code perhaps? or some weird clause tree comparisons... good question indeed.
You're misunderstanding the setup here. The LLM doesn't modify the query, just some details about how to choose between different ways to break the query into basic operations on the tables. The SQL doesn't change. It's still up to postgres to guarantee that the results match the query. If the proposed plan were nonsense that didn't amount to carrying out the query, postgres would ignore it.
Aren't optimizations suppose to be deterministic?
They are not. Choice among several query plans depends on various summary statistics about the data, which might not be the most recent.
Including the input parameters.
It's not unusual for us to end up with bad query plans because the shape of our data can vary pretty greatly. In many cases, a Foo has 1 Bar. But in some cases, a Foo has a million Bars. That can cause the query optimizer to treat lookups on the bar table as if there are few elements there (causing a scan instead of a seek).
For the general case, the optimizer gets it right. However, the fringe case is one that causes the entire system to crash. It's a bit akin to how an insertion sort can be faster than quick sort when n is small. The optimizer might make a bad assumption about the size of n which makes it pick an expensive n lookup when log(n) is available (but slower for small n).
I'd like to contribute my amateur hour entry into this thread, although I did administer and develop mssql stuff for awhile.
sure optimizations based on stats, but the stats are the wildcard, in my experience query plans can change suddenly.
Queries are translated into plans according to statistics. However the transforms will be deterministic and should only change one valid plan to another. I could very easily see a neural network manipulate transforms the same way the current programming does, its just that the neural networks are by nature really nicely suitable because the "decisions" are based on training, and this training can be closed world type things like the ai assists that chess engines are now getting. Obviously ai still can't play chess but apparently its very good at ranking board positions just by developing that much statistical info because its training comes not from reading the web, but playing a gazzilian games against itself in a "closed" chess world of its own.
I'm thinking that the ai does "this legal transform of the query plan should be applied to this pattern of data (statistics, cardinality, etc)" simply because the ai encountered it in closed world training, much like the chess thing.
Just a theory tho feel free to correct!
I believe you are wrong on that. Do you mean large language models can’t play chess?
I don't believe that a pure neural network can currently abide by the rules of chess, even with unreasonable amounts of training. Do you have a counter example? I never mind having beliefs challenged with facts lol
edit: I think you could provide an AI with a service or skill that asks "is this move legal" but given all the overhead for llms or whatever to call a "legal move" service external to its process, well then you aren't really searching the tree very efficiently lol.
However if you just let a neural network score boards and the neural network is in the same process well then I think thats the working solution for using neural networks in chess. The net does not need to score all boards either, simple value based heuristics can obviously provide a preliminary list of good boards (moves) at a certain depth or ply and then select the move that produces the board that the neural net scores highest. I kinda sorta think thats whats done today but as usual I could be full of it lol
I can’t find it in the article (may have skimmed it too much), but I suspect they didn’t include those ~95 hours in the benchmark numbers.
I think all database vendors know their query optimizers could do much better if they could afford to spend lots of time to derive query plans.
⇒ this may be useful for some workloads, but even then, can you afford to spend hours every now and then to update your 4B model to ensure it still picks a good query plan?
I think this would be likely comparable to a scheduled backup, so I think it would be an acceptable maintenance window. However, deterministic algorithms would likely beat re-training (or re-fine-tuning) the model. For example, one could analyze actual distributions or whatever (instead of assuming uniform), and then some plans would automatically be eliminated.
Imo a good thought experiment is to look at places that are hyper-optimized, like compilers. Would LLMs bring anything to the table (architecturally or performance-wise) to a piece of software that has been carefully crafted for decades? (Methinks no.)
The Postgres query planner has had to operate, for those same decades, in a much more realtime-sensitive and restricted environment than compilers. It can only draw its conclusions from summary statistics on tables in isolation, not on their relationships with each other (and even less so when filters are involved). For many cases this is fine! For many others it isn't.
I think the idea would be making a frontier model that does this. One that is trained on multiple queries
Could you stitch a specific query plan to your view?
‘create plan llm_optimized …’
‘create view foo (select x, y, z from table bar) with plan llm_optimized’
Wouldn't admitting this invite trouble due to accusations of distillation flying around between closed and open models.
I don't think anybody's denying that small models are doing distillation, the issue at hand is frontier lab vs frontier lab when it comes to big models.
Frontier model trainers stole almost all the data they've trained on (the whole internet, all copyrighted).
It's very hard for them to claim the moral high ground here.
It's like stealing an apple from the British Colonial Empire.
Having the moral high ground matters less than having a big warchest of money to spend on lawyers.
Does it matter if they companies doing are not in the jurisdiction or even if they are, maybe the can't prove it?
They can't prove it but can force you to spend time and money to disprove it.
The only thing they're going to try to do is ban Chinese models, and that's not going to fly outside the US, so Americans would be the only losers.
You'd be shocked at some of the punishments handed out from various empires over history for offences as minor as stealing an apple. Whether they can claim the moral high ground is not question of ethics but a question of power.
On the flip side, its important to know just how much we would be sacrificing if big frontier gets their way in convincing the courts that distillation is a bad thing
Yeah don't steal my stolen stuff.
why is this write-up so long?
Need 5 days just to go through it.
They forgot to run a (same) model to optimize article for reading speed
Think of it like a paper. You wouldn't ask why a paper was so long.
Also you can now ask AI to summarise it for you and even probe with questions pertaining to your specific interests.
Why wouldn't you ask that? That's exactly why papers have supplementary material
Funny enough I was thinking about something very similar to this based on the Jev model posted yesterday.
I’ve played with it already. I don’t think this is the use case. I think Jev’s use case is fast, cheap and somewhat easy classification. It’s not trainable in the way you would want here. Even though it’s fast it wont be faster than pgs query optimizer.
At least as I understand things.
How did you plan to use Jev for query optimization?
I am still struggling to understand a use-case for Jev. Isn't what was explained in this article a classification problem? I.e. find and aggregate data?
The number of options has to be small and bounded. The query planning is more of a search/optimization problem than a classification problem since the number of options increases wildly based on query size.
“81% faster query plans than Postgres”…on an 8 GB dataset that fits entirely in memory, with shared_buffers constrained to a fraction of that, queries warmed before measuring, and read-only SELECTs.
I would be cautious about over fitting, it’s tough to say if those query plans would really be more optimal than Postgres heuristics at scale and with a bit more realistic OLTP workloads.
In any case, such is life with profile guided optimization. Many of us appreciate how database workloads can drift over time and with scale.
Kudos to the author for getting their hands dirty and writing up their experiments.
With a 4B parameter model that probably ran through 8GBs of RAM multiple times to run.
At a certain point we should seriously talk about CUDA accelerating Postgres instead.
I would think it's possible to make it so that the 4B model only needs to be called during an initial phase, and then the same queries it constructed can just be re-used with values replaced, unless you're generating a lot of unique on-the-fly query shapes.
Optimal plan construction is math-heavy, algorithm-heavy and vary even by workload. There are options like creating just-in-time indexes, so solution space grows even faster than article presents. Sometimes it is the query planner which is the slow part of total execution time.
LLM is kind of blunt weapon to use here. I am waiting rather for alphago style neural net heuristic.
What if we use a hybrid model of using both query optimizer and LLM? Whichever produces better result, the database can use?
- a question from someone with lack of DB depth, me.
The immediate problem: How do you know which one is better without running them?
Not someone familiar with DB internals, but could you run in parallel, at least for reads?
This immediately halves your throughput.
Only in the worst case when the plans are equivalent: If one plan is significantly faster, then it'll finish first, and the loser can get canceled before it finishes.
Good and bad plans can have orders of magnitude performance difference. The bad one can easily do enough damage cutting the performance in half before it is canceled.
Could you A/B at random, use that to collect data and eventually feed that back in to prefer A or B depending on the shape of the query?
This is about to bake your noodle:
https://www.postgresql.org/docs/current/geqo-pg-intro.html
such a (visually) beautiful blogpost.
Engineer: "HELP, our production DB is frozen on this query that worked fine before!"
Infra: "Hmm, let's check... Well would you look at that, it seems like your LLM query planner usually works and produces fast queries, but this time when you changed a variable name to trigger query rebuild, it happened to hallucinate and miss an index, would you mind re-running the LLM a few times until you get a faster query?"
TL:DR; for people. Index your data properly.
This was a thoroughly enjoyable read, both the writing and presentation. I really liked the level of writing as it's basically introducing a whole lot of advanced topics but at just the right level for a non-AI researcher type of engineer like myself to be able to understand what's going on, and I felt it made some elements of LLMs actually something I could understand rather than wizardry done by maths PhDs. Probably because it's more like applied engineering rather than hard mathematics here. Thank you for a delightful post.