Training a 4B model to produce 81% faster query plans than Postgres
rohanbansal.com
rohanbansal.com
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.
At a certain point we should seriously talk about CUDA accelerating Postgres instead.
8GB isn't even CPU RAM these days. That's GPU super-mega-awesome ram. Ordinary Server CPUs are regularly pushing 2TB capacities.
GPUs are in the 8GB to 32GB typically, at least for smaller and more regular GPUs. This GPU RAM is also well known to be at least 10x the bandwidth of CPU RAM.
GPUs are simply faster at fundamental algorithms like sorting (which has huge parallelism), and hashing. This is because both sorting and hashing benefit from endless growth of parallelism, offering enough "work" for these 10,000 SIMD-core systems to crunch work upon.
And because of modern algorithms/libraries with 'Mergepath sort' (a GPU-SIMD parallel sorting algorithm), its not even that difficult to implement anymore.
Naturally, this then leads to parallel Sort Merge Join, as well as parallel Hash-Join (two ways to implement left or right joins in a GPU that benefit from significant parallelism).
So yeah, Joins. https://www.kenchoi.dev/papers/gpu-joins.pdf (This paper also has a description of "Mergepath sort", a GPU parallel way of sorting)
---------
Even if GPUs weren't fundamentally faster at these kinds of operations... the RAM is simply 10x higher bandwidth and we all know its a RAM-constrained problem.
Your typical SQL query is going to need multiple joins, probably a sort and possibly some "group" operations. As long as you have more than 10,000 elements or so (IE: can saturate all 10,000+ SIMD-units of a GPU), you'll be able to at least benefit from the faster RAM.
If you have a LOT of joins (a recursive join or some other kind of deeply nested computationally complex query), you probably benefit even more from the greater compute-power offered by GPUs. These operations (joins really) are nominally over the entire set of data, and cleanly break down into obvious parallelism.
It can be. That was the big new innovation in video game load times
That is the responsibility of whoever thought it would be a good idea to write this article. It's their responsibility to show that their idea has merit, and that their results are significant. I mean, don't they have a vested interest in manipulating and cherry-picking their results to inflate their relevance?
This is why academic papers are peer reviewed.
Couple things that I found interesting
1. Inefficiencies/limitations of the query planner in certain cases are known for a long time, its a trade off. This is the reason why hints exists and one can provide their own plan too. DBAs have been doing that for a while now.
2. A SQL database by design is a resilient unit in itself just dependent on CPU and memory/disk. The availability for the DB is heavily dependent on this factor. Everything built on the top derives their availability and reliability from this. Adding an LLM in between is more cost for sure, question is if its really brining the benefits which are worth the trade off
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?"
By people with a specific skill set. LLMs generation can also be fixed and verified by people with a certain skill set, and non-deterministic computing doesn't automatically mean unpredictable. When people say that the LLMs are a black box, it means unpredictability in unknown situations.
You do structured output, input validation, output validation, lower temperature, limit decisions, RL, etc. to increase predictability to near certainty. It's just statistics after all. Or you can as well generate the code to do the job.
It's just that the required skill set is a different one to do those things, and unusual in the context of DB administration.
I just find the "all llms are non dererministic and therefore unreliable" narrative a bit backwards. All software that has more than 0 users needs to deal with non-determinism anyway :)
From a completely technical perspective, we have a rough idea how the LLMs work, and improving a system requires measuring outcomes and you don't necessarily need to understand the mechanism.
EXPLAIN ANALYZE against data that's similar in size to prod checks a query written by an LLM as good as anything we can write... but, yes, you're right, we still didn't solve the halting problem - neither the LLMs.
Query planner feels pretty LLM-esque already
A bad query plan is not your typical kind of bug. I would definitely not call it fixable. Query planners are inherently dealing with estimations and approximations. If the query planners estimation is off, you're screwed.
Unless you come up with a way to cheaply determine exactly how many rows a query will return, bad query plans will still exist.
I've literally been saying "I can't believe the date is X and we still have to put up with this" for around 25 years now.
Stored procedures in this context are just a clumsy workaround to control the planner so your comment about API layer is irrelevant. But if you like, you can write stored procedures in a ton of different languages. And if you do not have source control for your database artifacts, you are doing it wrong. A common reason for stored procedures is to not have a bunch network roundtrips in the middle of your transaction logic while you are holding onto locks / have an open conflict window.
Stored procedures are essentially a crude, database-bound API layer. For serious application development, a proper service layer provides stronger contracts, authentication, testing, versioning, observability and source control in a sane general-purpose language, ideally the same one you’re already manipulating the data with elsewhere.
I guess we agree on them being an API that gets deployed on the database, but I disagree that it needs to be crude. It's exactly as crude as you make it. If you don't have authentication, testing, versioning, observability and source control for your database you are doing it wrong.
LLM is kind of blunt weapon to use here. I am waiting rather for alphago style neural net heuristic.
- a question from someone with lack of DB depth, me.
That's the key question.
I think LLMs allow people with no context or background or know-how to dive into projects and see some results being presented to them, but they don't have the context or skillset to tell what they see before them.
This paves the way to people laying grand claims about achievements because of LLMs. Their claim is that LLMs know best primarily because LLMs knew more than them, not that the output is good or desirable.
Because one could be in that state where they are trying to use a tech they know preciously little about to solve a problem they know nothing about.
This reminds me of a request we got from our "AI Department": if you build us a proper shares market simulator, we will build you an awesome agent that can trade shares. They seemed quite confused when I pointed out that if we could build such a simulator, we wouldn't need them anymore.
And yes, large joins is definitely for OLAP use. If you have 20-way joins for OLTP, you're either crazy or you're using an ORM.
Wouldn't admitting this invite trouble due to accusations of distillation flying around between closed and open models.
It's very hard for them to claim the moral high ground here.
It's like stealing an apple from the British Colonial Empire.
A big reason the initial plan isn't guaranteed to be optimal, even with all the right indexes, is that table statistics aren't perfect. For example, you might track a column's correlation (how closely the column's logical ordering matches its physical ordering in the heap), but that won't be broken down at a per value level. Postal code X might be very correlated, while postal code Y that is used in your query is completely uncorrelated.
The ideal solution is to pick one plan initially, and then update a temporary query-specific statistic model based on the data you actually read while executing the query. Then periodically re-evaluate if an alternative plan would be faster, switching to it in a way that doesn't throw away the current partial result.
Of course switching plans mid flight is very complicated, but Oracle and SQL server both support this feature, so hopefully it lands in Postgres at some point.
Nearly every time I’ve seen someone resorting to hints for a query, it’s because their statistics are incorrect. Adding hints is papering over the problem, and can backfire later if the data shape changes.
> 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?
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.)
As an example, register allocation is graph colouring, and thus NP complete; a model for producing an allocation plan is learning heuristics that might look at more features in combination than the ones hand-crafted into the compiler. An LLM for the job might do better than a more focused model like a GNN, due to sheer size, the effectiveness of transformers, or magic. But it probably won't do an overall better job than the handcrafted heuristics, because those handcrafted heuristics also tend to compile very, very fast with a small memory footprint, and can be debugged (more) easily when they go wrong.
Postgres keeps histograms (including N most common values) for all columns; it does not blindly assume uniform distributions. (Presumably an LLM would have access to the same histograms.)
‘create plan llm_optimized …’
‘create view foo (select x, y, z from table bar) with plan llm_optimized’
> Favorite settings The model regularly used enable_sort=off and random_page_cost=1.1
If random_page_cost wasn't set correctly for the default cases postgres's query planner can generate terrible plans (unless you're running on a spinning disk).
That could easily explain the difference by itself.
This is the most important part. Most queries are either quick transactions that can run thousands of times per second, or complex but predictable scheduled analytics.
One off queries are pretty rare and optimizing for them instead of the common ones is a massive own goal almost every database is repeating. I don't think you need a LLM to beat Postgres.
[1] https://github.com/datalevin/datalevin/tree/master/benchmark...
Second. How would that LLM-based query optimizer work in a real-world 10,000 qps ERP system with very large shape of queries? I'm not saying it's useless, it just won't replace a real query planner soon. Latencies would skyrocket.
At least as I understand things.
How did you plan to use Jev for query optimization?
Let’s talk when you are looking at double digit TB at a minimum.
> As it turns out: enormously hard.
This exactly tracks me learning everything
However, it misses the whole point of database query planning. You can't just ignore the planning time itself, as if the database query were a static entity to be optimized once at a leisurely pace.
The real constraint on live query planners is quite different: they must improve the combined time - planning + query - based on live database statistics. You can amortize the planning with prepared statements, but that too is fraught since optimal plans can change quite frequently and based on input parameters. "Live" and "faster than the queries themselves" are the hard requirements to be considered a viable database query planner. This project does neither.
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).
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?
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
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.
(Indexes would be nice though)
Need 5 days just to go through it.
Also you can now ask AI to summarise it for you and even probe with questions pertaining to your specific interests.
I've asked myself that question a whole bunch of times