Hacker News Reader

Comment by anarazel | Hacker News Reader

I'd like to see your proposal get a bit more concrete. Your request seems a bit more for "magic" than "AI".

You're not likely to succeed with "here's the query and schema" and have AI somehow figure out what the best plan there is. There's a lot of rules to observe for correctness, and you can't just try to execute arbitrary valid plans, because the initial query plans are going to be really bad. So you again need a model of what valid query plans are, and a cost model to evaluate how efficient a plan is, without having executed it.

I think there's plenty opportunities for ML type improvements, but they're in individual parts, less as a wholesale query planner replacement. I think the most likely beneficiaries are around statics collection and evaluation, incremental improvements to query plans, and some execution time -> plan time feedback loops.

View on HN

> So you again need a model of what valid query plans are, and a cost model to evaluate how efficient a plan is, without having executed it.

Surely query optimizers do this already. What about that sounds like "magic"?

Computers can beat Lee Sedol at Go, it hardly seems like "magic" for a computer to come up with a query plan that is obvious to a trained human.

For example, OP mentioned the case of creating a temporary table with an index instead of emitting a lot of temporary files executing a subquery. Surely you could statically verify that such a transformation was legal, and it seems likely that a cost model could accurately predict that such a transformation would be cheaper. So why doesn't the query optimizer perform this transformation? Presumably because it doesn't yet explore this part of the search space of possible transformations.

EDIT: apparently this post is making some people mad. I'm not saying it's easy or obvious, but with ML being applied to so many problems very successfully, it seems very strange to say it's expecting "magic" to suggest that ML could improve on obviously sub-optimal query plans.

We have a cost function and we have a search space of valid transformations. Sounds like a lot of room to experiment with ML-based approaches to me.

> > So you again need a model of what valid query plans are, and a cost model to evaluate how efficient a plan is, without having executed it.

> Surely query optimizers do this already.

Sure. But not in a form that's applicable for ML / AI.

> What about that sounds like "magic"?

It's naming a buzzword and expecting revolutionary results, without actually suggesting how $buzzword can applied to achieve those results.

I'm asking for concrete proposals because I think it's an interesting field.

> Computers can beat Lee Sedol at Go, it hardly seems like "magic" for a computer to come up with a query plan that is obvious to a trained human.

Just because a technology worked for one field, doesn't mean it's trivially applicable for other fields (not that the original application for go was trivial in the least).

And this is exactly why I hate trendy buzzwords, especially when they involve fields that are large, complex, and been around forever. The Dunning-Kruger effect is running at 11 here.

Assuming that there’s a single “AI” technology that’s used and widely applicable is deeply flawed, as is the idea that all of googles computational power for such a peacock-oriented game can make its way into a query planner. It’s already the case that Postgres is based on genetic algorithms, so it’s already got “AI” baked in.

I’m sure there is plenty of room for improvement with query planners, including new paradigms, but you can’t just throw such a generic buzzword at it and have that be intelligible. You might as well say “it just needs better algorithms.” Well, ya. It has zero substance.

Postgres uses GEQO for really long lists of joins. For lots of workloads, if you turn it off, you'll get better performance because the query planning time is dwarfed by the runtime of a bad plan, so you're happy to wait and brute force it. But even then, the constraints in which that brute forcing applies are pretty limited (by the schema and by potentially suboptimal SQL).

I'm sorry that you think my suggestion has zero substance. If you think that the sub-second query plans that Postgres currently generates for ad-hoc workloads are adequate, I wish you luck. I personally think there are lots of missing heuristics that an ML approach could pick up, either in the general case, or over time in a specific database.

I'm interested in how you think they could best be applied. I know I've pushed the point that it uses the genetic algorithm higher to ensure I got better plans for larger join lists before. But what ways could we use ML to generate optimal plans for different query parameters? An optimal plan for one set of parameters could be totally non optimal for another set. How could we handle that? I'd actually love to see this type of discussion happening on the mailing list.

I don't have the answers - I would honestly like to see training done on real workloads. In at least _some_ situations, it seems like live-calculating statistics would be quicker and I know ML work has been done on estimating statistics more accurately.

I'll be honest, for a lot of stuff I can live without any real intelligence. For my workloads, I'd be happy to wait for the query planner to gain full knowledge of the physical layout of the database before trying anything. My other main annoyance, as mentioned, is WHERE clause pushdowns. I think there is a simple, if not efficient, decision procedure for this stuff and I'm happy to wait for the planner to do the work.

Are the pushdown problems you're experiencing with postgres, or something else? If with PG, I'd very much welcome you to report them. While we know about some weaknesses of the predicate pushdown logic (some more complicated group bys, lateral + subqueries), it'd be good to know about more of them.

FWIW, to me pushdown doesn't sound at all like a field where ML would be helpful...

Yeah, I'm not really proposing some specialised ML algorithm within Postgres to handle these edge cases, I'm more hoping that someone comes along with an entirely new paradigm for describing data and queries, that allows a platform to evolve on top of that for maximum performance given the described workload.

In a particular case that annoyed me this week, casting an IN clause with a subquery to an array (on a query over a view with a GROUP BY) resulted in wildly better performance, despite setting the statistics target to the maximum value, indexing everything etc. I'm happy to demonstrate a trivial reproduction of this issue, and I'm sure I'm a crap DBA, but every day it's the same fight - SQL is _not_ a declarative language. It is incredibly sensitive to implementation details, in ways that are way less obvious than any other programming language.

Postgres could do a better job in all sorts of situations, but I personally think that finding all these edge cases algorithmically or analytically is futile. A platform built on a paradigm more closely aligned to the logical descriptions of data and queries could, over time, learn to perform better.

> Sure. But not in a form that's applicable for ML / AI.

You have a cost function you want to minimize. That can't form the basis of a search among valid program transformations?

> Just because a technology worked for one field, doesn't mean it's trivially applicable for other fields

I didn't say "trivially." I just pushed back on the idea that it's "magic."

There are precedents for ML-like approaches to optimization for regular compilers. For example, superoptimizers.

Yes; as we all know, superoptimizers were revolutionary and now form the core of compilers.

Also, superoptimizers are stochastic search algorithms, which are only tangentially related to ML, which is again only tangentially related to AI. The relation between AI and superoptimization is close to nil.

I wonder how hard it would be to give Postgres a pluggable query planner, so that extensions can try to improve on its results. Then people could try things out without Postgres committing to something too soon.

I'm still learning what Postgres extensions are capable of. I've written a few but only to define functions & types. It seems like I've seen more "interesting" achievements though, like CitusDB seems able to rewrite queries. Can an extension even add syntax?

EDIT: This seems to be the important part: https://github.com/citusdata/citus/blob/master/src/backend/d...

I wonder what `planner_hook` is about. . . .

> I wonder how hard it would be to give Postgres a pluggable query planner, so that extensions can try to improve on its results. Then people could try things out without Postgres committing to something too soon.

You can quite easily replace the planner, it's just a single hook. Building a replacement's the hard part ;)

> Can an extension even add syntax?

No, not really. There's no good way to achieve extensibility with a bison based parser. At least none that we PG devs know and "believe" in.

What I'm saying is that I, as a human, can spot simple situations under which semantically-correct optimizations are available. I can also create queries where literally cutting and pasting IDs over and over again into a WHERE clause is quicker than joining or using an IN clause. These things are dumb.

I personally think there are massive opportunities for data description languages and query languages that make expressing a single set of semantics simpler. SQL is supposedly a declarative language, but almost always requires you to understand _all_ the underlying implementation details of a database to get good performance.

Beyond that, I'd be more than happy with ML that enhanced, heuristically, some parts of the query optimiser. Hell, I'd be happy with a query optimiser that just went away and optimised, 24 hours a day, or at least didn't just spend 19ms planning a query that is then going to run for 8 hours.

ML with human-in-the-loop (HITL). There is a feedback loop that learns based on human expectation. Peloton[1] is already learning based on data access patterns, but doesn't consider subjective feedback. Maybe there could be a query planner that learns which query plans are better via reinforcement learning (the reward is given by the human).

[1]: https://github.com/cmu-db/peloton

I think named entity recognition may help if detailed labels were used. The parser can already label the where clause, select clause, etc. However a component of a where clause in a given query may be better executed as a join clause. Given enough training data, NER should be able to recognize the join clause within the where clause in that specific context and the resulting labels would give the optimizer a hint on how to rewrite that specific query.

Now I have no idea how much training data you would need or if a single, trained model would work for most use cases. But I think it could work in theory.

Reply on news.ycombinator.com