7 ms·

It's 2017, and despite all this parallel stuff, query planners are still dumb as bricks. Every day I get annoyed at various obvious-to-the-eye WHERE clause push

by thom 9y ago

It's 2017, and despite all this parallel stuff, query planners are still dumb as bricks. Every day I get annoyed at various obvious-to-the-eye WHERE clause pushdown opportunities, or situations where I can manually copy a view to a table, add indexes, and build a query on top of that quicker than letting the database fill up the entire disk with temporary files trying to do it as a subquery. It's utterly maddening if you spend your life on ad-hoc analytics/reporting workloads. I strongly believe there are huge opportunities for AI to come along and, given a logical description of the data and query, do a better job of physically organising and serving the data. I realise some database management systems do this to an extent, but it's pretty weak sauce in my experience.

jeffdavis 9y ago
There's a fair amount of research in that area and at PGCon there is usually at least one talk about how to make it work in postgres. But it's a ways off and can take many different forms.
jaltekruse 9y ago
If you want to take part in a community effort to fix this problem, consider contributing the to Apache Calcite project. It has relational algebra that spans across many different databases and dialects, including NoSQL databases like MongoDB and Elasticsearch. I haven't been very involved with the project directly, but I've worked on several projects that heavily depended on it, and have written extensions for those projects.
- xyzzy_plugh 9y ago
  I took a peek into calcite some time ago and was disappointed. The project seems to be overly bureaucratic, and the code quality quite low. (Side note, I've noticed a steady decline in quality of Apache projects for at least the past decade or so.) I wanted to perform some introspection on queries in-flight, and potentially re-write them, but this seemed like an awful chore with calcite. One, calcite didn't implement my dialect -- it looked non-trivial to add new dialects. Two, going from query to parse tree (with metadata) back to query doesn't seem to be something that's intended to be supported. Calcite is really a replacement frontend with its own SQL dialect that you can tweak the compiled output (SQL, CQL, etc.). It has its own worts and is not generally applicable to other projects. It works well within the Apache ecosystem but I don't envision much adoption outside of it (especially non-Java, like Postgres). If you were writing a Tableau replacement, you might consider using Calcite to generate your queries. I don't see many other use cases.
  - derefr 9y ago
    > Side note, I've noticed a steady decline in quality of Apache projects for at least the past decade or so. That's a weird trend to notice, given that none of the same developers are working on "Apache projects" generally. The ASF isn't like e.g. Mozilla; it isn't a monolithic org with its own devs. It's a meta-bureaucracy that takes ownership of projects for legal (copyright + patent assignment) reasons, and then offers project-management charters to member projects, giving them process and structure for contribution without a canonical owner. An ASF project is sort of like a "working group" (e.g. Khronos, WHATWG), except that it's usually one or two large corporations and a bunch of FOSS devs, rather than being exclusively a bunch of corporations. --- On the other hand, if there is a trend, it might be because of the increasing reliance on the "open core" strategy for corporate FOSS contributors to make money. My own experience is with Cloudant, who contribute to Apache CouchDB, but also have their own private fork of CouchDB running on their SaaS. Originally, Cloudant did what they liked in their own fork, and then tried to push the results upstream. The ASF didn't like this very much, since these contributions weren't planned in the open, so Cloudant increasingly tried instead to mirror its internal issues as ASF Bugzilla issues and get public-member sign-off before going forward on private solutions. Which is kind of a shadow play, since many of the founding members of the CouchDB ASF project either have always worked for Cloudant, or have since been hired by Cloudant, so it's Cloudant employees (in their roles as ASF project members) signing off on these Cloudant issues. But it still slows things down. A good comparison that people might be familiar with, with the same dynamics, is WebKit. The WebKit project has its own separate development organization, but most of the developers happen to also work for Apple. Previously, WebKit was Apple and Google, but even two corporate contributors were too big for the small pond. Which, to me, shows that they were each there expecting to dominate the decision-making process, rather than find consensus with the FOSS contributors; and having an equally-powerful player that they had to form consensus with was too much for them.
    - anarazel 9y ago
      How's that dispositive of a declining average code quality? ASF has influence over which projects get incubated, and even some over how projects are managed.
fatbird 9y ago
This is interesting. When you see these 'obvious to the eye' opportunities, do you stop and treat them as an exercise in generalizing the optimization for a query planner? I'm curious how much query planners have to make tradeoffs between effective optimizations and not overloading the analysis phase.
- anarazel 9y ago
  > I'm curious how much query planners have to make tradeoffs between effective optimizations and not overloading the analysis phase. In case of PostgreSQL: constantly. Pretty much every planner improvement has to argue that it's not likely to unduly increase plan time.
  - kuschku 9y ago
    What about pre-compiling plans? With server-side prepared statements it would make sense to use entirely different planning time tradeoffs.
    - anarazel 9y ago
      It's not that simple. Server side prepared statements are used to great effect in OLTPish scenarios too. A serviceable approach would be to perform additional optimizations based on the query's cost - but that's hard to do without incurring a complete replan, because of the bottom up dynamic programming approach of a good chunk of the planning.
      - kuschku 9y ago
        Well, I’d love to see a way to set such a query planning cost target. There’s a few statements which I never change, but run thousands of times a day, and which are extremely expensive.
- thom 9y ago
  I care about the total amount of time until I get to do real work with the data returned. Subsecond query plans for ad-hoc workloads are pointless for me if I then wait 10 hours for results. Here's a concrete example: a view with a GROUP BY. Give it a concrete ID to filter by, and it will push it down to the underlying table and return quick results. I can then script a loop to do this to get the full dataset for a list of IDs. However, if I supply a `WHERE id IN (...)` or a JOIN, the query plan will be totally different and will take forever. This is dumb, and this is with up-to-date statistics etc. I'm happy to accept I'm probably not the target market, but just having the option to leave the query planner running for minutes instead of milliseconds would be great (if it indeed has work to _do_ in those minutes).
alexnewman 9y ago
Agreed. You following the cmu research on ml planned dB?
jalayir 9y ago
Have your run ANALYZE? ;)
lobster_johnson 9y ago
A lower-hanging fruit may be a dynamic profiler that continuously analyzes query patterns, and automatically reorganizes indexes, table clustering, partitioning, and query planning based on the actual database activity. This could even be something that operates as a layer on top of Postgres, although it would probably need more precise data than what is currently available through stats tables, and since Postgres doesn't have query hints there's no way to modify query plans. It would also need the look at logs to see what the most frequent queries are, and possibly require a dedicated slave to "test run" queries on to gauge whether it has found an optimal solution (or maybe do it on the actual database during quiet hours). AI would definitely be interesting, though.
- derefr 9y ago
  I've always wondered why there doesn't exist something like this, but architected like Apache's mod_security: something you run for a while in "training" mode to let it learn your usage patterns, which then spits out a hints file (in mod_security's case, a behaviour whitelist; in this case, a migration to add a set of indexes + views). As a bonus, it could (like mod-security) also have a "production mode" where the DB consumes that hints file and applies the instructions in it as an overlay, rather than as a permanent patch to your schema; that way, you'd be able to re-train after changes and then swap out the hints in production by just swapping out the file and HUPping the DB server (which would hopefully do the least-time migration to turn the old indexes into the new indexes), rather than needing to scrub out all the old indexes before building new ones.
  - Drdrdrq 9y ago
    It exists for MongoDB (Dex).
  - tatersolid 9y ago
    This is also exactly what Microsoft SQL Server has done _since 2005_ with dynamic managements views. It shows on a running system what indexes would be optimal for an actual workload.
- dantiberian 9y ago
anarazel 9y ago
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.
- haberman 9y ago
  > 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.
  - anarazel 9y ago
    > > 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).
qaq 9y ago
It's not a big problem to make query planner that generates close to perfect plans. The problem is the amount of time it would take for that query planner to generate a plan.
- thom 9y ago
  Let me decide the amount of time, then. If I can cut and paste a bunch of queries together to make them faster than the current planner, I'd be happy to let the query planner run for tens of minutes.
  - qaq 9y ago
    Well that would be a reasonable strategy for analytics queries
silvestrov 9y ago
I would prefer they worked on something much simpler for now: the ability to mark a table as "log all full table scans on this table unless the SQL query contains the string xxxxx". This would make it easy to catch missing indexes without logging all queries and without the nightly batch updates which are expected to do full table scans.
- thom 9y ago
  I'm sure you're aware of this, but apart from the filtering, you _can_ get a count of sequential scans for a table from pg_stat_all_tables.
macdice 9y ago
You might be interested in the AQO project that was presented at PGCon 2017: https://www.pgcon.org/2017/schedule/events/1086.en.html https://www.pgcon.org/2017/schedule/events/1086.en.html It's using machine learning techniques to improve cardinality estimates.
TheCondor 9y ago
Are the statistics wrong on your data? Or is it that the subqueries modify the data set such that the statistics are unknown for the outer query? Arbitrary ad hoc query support is hard, it feels like you want indices on everything but then data insertion is dog slow. Then even with perfect stats I’ve seen vertica and PostgreSQL order aspects of queries wrong, I know the pain you speak of. I’ve not convinced myself that it’s always solvable or obvious until you do it wrong though, I never spent much time explaining queries before executing them or explaining “fast” queries though.

by thom 9y ago

jeffdavis 9y ago

There's a fair amount of research in that area and at PGCon there is usually at least one talk about how to make it work in postgres. But it's a ways off and can take many different forms.

jaltekruse 9y ago

If you want to take part in a community effort to fix this problem, consider contributing the to Apache Calcite project. It has relational algebra that spans across many different databases and dialects, including NoSQL databases like MongoDB and Elasticsearch. I haven't been very involved with the project directly, but I've worked on several projects that heavily depended on it, and have written extensions for those projects.

xyzzy_plugh 9y ago
I took a peek into calcite some time ago and was disappointed. The project seems to be overly bureaucratic, and the code quality quite low. (Side note, I've noticed a steady decline in quality of Apache projects for at least the past decade or so.) I wanted to perform some introspection on queries in-flight, and potentially re-write them, but this seemed like an awful chore with calcite. One, calcite didn't implement my dialect -- it looked non-trivial to add new dialects. Two, going from query to parse tree (with metadata) back to query doesn't seem to be something that's intended to be supported. Calcite is really a replacement frontend with its own SQL dialect that you can tweak the compiled output (SQL, CQL, etc.). It has its own worts and is not generally applicable to other projects. It works well within the Apache ecosystem but I don't envision much adoption outside of it (especially non-Java, like Postgres). If you were writing a Tableau replacement, you might consider using Calcite to generate your queries. I don't see many other use cases.
- derefr 9y ago
  > Side note, I've noticed a steady decline in quality of Apache projects for at least the past decade or so. That's a weird trend to notice, given that none of the same developers are working on "Apache projects" generally. The ASF isn't like e.g. Mozilla; it isn't a monolithic org with its own devs. It's a meta-bureaucracy that takes ownership of projects for legal (copyright + patent assignment) reasons, and then offers project-management charters to member projects, giving them process and structure for contribution without a canonical owner. An ASF project is sort of like a "working group" (e.g. Khronos, WHATWG), except that it's usually one or two large corporations and a bunch of FOSS devs, rather than being exclusively a bunch of corporations. --- On the other hand, if there is a trend, it might be because of the increasing reliance on the "open core" strategy for corporate FOSS contributors to make money. My own experience is with Cloudant, who contribute to Apache CouchDB, but also have their own private fork of CouchDB running on their SaaS. Originally, Cloudant did what they liked in their own fork, and then tried to push the results upstream. The ASF didn't like this very much, since these contributions weren't planned in the open, so Cloudant increasingly tried instead to mirror its internal issues as ASF Bugzilla issues and get public-member sign-off before going forward on private solutions. Which is kind of a shadow play, since many of the founding members of the CouchDB ASF project either have always worked for Cloudant, or have since been hired by Cloudant, so it's Cloudant employees (in their roles as ASF project members) signing off on these Cloudant issues. But it still slows things down. A good comparison that people might be familiar with, with the same dynamics, is WebKit. The WebKit project has its own separate development organization, but most of the developers happen to also work for Apple. Previously, WebKit was Apple and Google, but even two corporate contributors were too big for the small pond. Which, to me, shows that they were each there expecting to dominate the decision-making process, rather than find consensus with the FOSS contributors; and having an equally-powerful player that they had to form consensus with was too much for them.
  - anarazel 9y ago
    How's that dispositive of a declining average code quality? ASF has influence over which projects get incubated, and even some over how projects are managed.

fatbird 9y ago

This is interesting. When you see these 'obvious to the eye' opportunities, do you stop and treat them as an exercise in generalizing the optimization for a query planner? I'm curious how much query planners have to make tradeoffs between effective optimizations and not overloading the analysis phase.

anarazel 9y ago
> I'm curious how much query planners have to make tradeoffs between effective optimizations and not overloading the analysis phase. In case of PostgreSQL: constantly. Pretty much every planner improvement has to argue that it's not likely to unduly increase plan time.
- kuschku 9y ago
  What about pre-compiling plans? With server-side prepared statements it would make sense to use entirely different planning time tradeoffs.
  - anarazel 9y ago
    It's not that simple. Server side prepared statements are used to great effect in OLTPish scenarios too. A serviceable approach would be to perform additional optimizations based on the query's cost - but that's hard to do without incurring a complete replan, because of the bottom up dynamic programming approach of a good chunk of the planning.
    - kuschku 9y ago
      Well, I’d love to see a way to set such a query planning cost target. There’s a few statements which I never change, but run thousands of times a day, and which are extremely expensive.
thom 9y ago
I care about the total amount of time until I get to do real work with the data returned. Subsecond query plans for ad-hoc workloads are pointless for me if I then wait 10 hours for results. Here's a concrete example: a view with a GROUP BY. Give it a concrete ID to filter by, and it will push it down to the underlying table and return quick results. I can then script a loop to do this to get the full dataset for a list of IDs. However, if I supply a `WHERE id IN (...)` or a JOIN, the query plan will be totally different and will take forever. This is dumb, and this is with up-to-date statistics etc. I'm happy to accept I'm probably not the target market, but just having the option to leave the query planner running for minutes instead of milliseconds would be great (if it indeed has work to _do_ in those minutes).

alexnewman 9y ago

Agreed. You following the cmu research on ml planned dB?

jalayir 9y ago

Have your run ANALYZE? ;)

lobster_johnson 9y ago

A lower-hanging fruit may be a dynamic profiler that continuously analyzes query patterns, and automatically reorganizes indexes, table clustering, partitioning, and query planning based on the actual database activity. This could even be something that operates as a layer on top of Postgres, although it would probably need more precise data than what is currently available through stats tables, and since Postgres doesn't have query hints there's no way to modify query plans. It would also need the look at logs to see what the most frequent queries are, and possibly require a dedicated slave to "test run" queries on to gauge whether it has found an optimal solution (or maybe do it on the actual database during quiet hours). AI would definitely be interesting, though.

derefr 9y ago
I've always wondered why there doesn't exist something like this, but architected like Apache's mod_security: something you run for a while in "training" mode to let it learn your usage patterns, which then spits out a hints file (in mod_security's case, a behaviour whitelist; in this case, a migration to add a set of indexes + views). As a bonus, it could (like mod-security) also have a "production mode" where the DB consumes that hints file and applies the instructions in it as an overlay, rather than as a permanent patch to your schema; that way, you'd be able to re-train after changes and then swap out the hints in production by just swapping out the file and HUPping the DB server (which would hopefully do the least-time migration to turn the old indexes into the new indexes), rather than needing to scrub out all the old indexes before building new ones.
- Drdrdrq 9y ago
  It exists for MongoDB (Dex).
- tatersolid 9y ago
  This is also exactly what Microsoft SQL Server has done _since 2005_ with dynamic managements views. It shows on a running system what indexes would be optimal for an actual workload.
dantiberian 9y ago

anarazel 9y ago

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.

haberman 9y ago
> 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.
- anarazel 9y ago
  > > 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).

qaq 9y ago

It's not a big problem to make query planner that generates close to perfect plans. The problem is the amount of time it would take for that query planner to generate a plan.

thom 9y ago
Let me decide the amount of time, then. If I can cut and paste a bunch of queries together to make them faster than the current planner, I'd be happy to let the query planner run for tens of minutes.
- qaq 9y ago
  Well that would be a reasonable strategy for analytics queries

silvestrov 9y ago

I would prefer they worked on something much simpler for now: the ability to mark a table as "log all full table scans on this table unless the SQL query contains the string xxxxx". This would make it easy to catch missing indexes without logging all queries and without the nightly batch updates which are expected to do full table scans.

thom 9y ago
I'm sure you're aware of this, but apart from the filtering, you _can_ get a count of sequential scans for a table from pg_stat_all_tables.

macdice 9y ago

You might be interested in the AQO project that was presented at PGCon 2017: https://www.pgcon.org/2017/schedule/events/1086.en.html https://www.pgcon.org/2017/schedule/events/1086.en.html It's using machine learning techniques to improve cardinality estimates.

TheCondor 9y ago

Are the statistics wrong on your data? Or is it that the subqueries modify the data set such that the statistics are unknown for the outer query? Arbitrary ad hoc query support is hard, it feels like you want indices on everything but then data insertion is dog slow. Then even with perfect stats I’ve seen vertica and PostgreSQL order aspects of queries wrong, I know the pain you speak of. I’ve not convinced myself that it’s always solvable or obvious until you do it wrong though, I never spent much time explaining queries before executing them or explaining “fast” queries though.