7 ms·

What Is a Query Planner?

86 points by samlambert 4y ago

qorrect 4y ago
Is this different from 'compiling sql'?
- tester756 4y ago
  I think I'd say yea because AFAIK/IIRC query planners tend to use additional environment informations to make better plan. Maybe it would be closer to JIT?
- maxbond 4y ago
  A query planner will consider the idiosyncratic properties of your data to determine the most efficient way to execute your query, whereas a compiler is generally blind to the data your program will be processing. So if you execute the query "SELECT * FROM (a, b) WHERE a.foo = b.bar", if you have many rows in `a` but few rows in `b`, then it's much for efficient to scan `b` than `a`. The query planner will keep track of properties like this & come up with tricks to speed up execution. But in the sense that "everything is a compiler", yeah you could totally think of a query planner as a compiler that takes in your query's AST and a statistical description of your data and lowers it to a query plan.
  - SigmundA 4y ago
    This seems pretty similar to profile guided optimization that say Java or .Net or Javascript can do since since it has access to runtime data during JIT Compilation.
    - maxbond 4y ago
      I hadn't made that connection but it's an excellent one!
- VWWHFSfQ 4y ago
  I've always thought of it as closer to an optimizing JIT compiler than just a regular translation of instructions to instructions.
  - koolba 4y ago
    Not quite. A query plan is usually represented as a tree of steps to output the desired result. Each node would be a high level operation (e.g. a sort) or source of data (e.g. read rows from table), possibly pulling from other nodes beneath it. The actual compilation of the plan to machine code is possible and a few database systems do exactly that. But most process then nodes themselves or JIT specific node types represent simpler or more tightly defined operations.
    - kaba0 4y ago
      I think they meant it in a more abstract sense; also see relevant sister threads.
    - WJW 4y ago
      Don't most planners also take table and/or index statistics into account? AFAIK for most of the commonly used DBMSes, the same query will result in radically different query plans if the table contents are different enough.
- jeff-davis 4y ago
  Query planners often choose the algorithm based on data statistics (as described in the article). Compilers generally just make a lot of constant-factor improvements without changing the algorithm. One exception might be the tail-call optimization, which changes the space complexity of an algorithm. And that's one of the optimizations where the developer needs to know for sure whether it will br applied or not.
didgetmaster 4y ago
> Anyone that has worked with large databases can testify how slow queries can get. This is often due to the necessary indexes not being there, or something in the query that stops the database system from using the index. Choosing the right indexes to use, and the right order to fetch data in, proves to be the difference between a 10ms and 5s query. This seems incredibly intuitive. Anyone reading it would get the impression that query speed is very important for database users and that they would be eager to investigate any new technology that promised a substantial improvement in query performance. Yet, I have found the opposite. I created a new kind of database that shows incredible performance gains when compared with mainstream databases like SQLite (https://www.youtube.com/watch?v=Va5ZqfwQXWI https://www.youtube.com/watch?v=Va5ZqfwQXWI) for simple and complex queries against tables of all sizes. It is able to do this without needing to create separate indexes on all the columns in the WHERE clause. The software is in open beta and available for free download at (https://www.Didgets.com https://www.Didgets.com) but it is like pulling teeth to get people to try it out. If I post something like this on HN, I usually get lots of comments about how my claims are impossible (or at least improbable) but few are willing to actually test it themselves on their own machine with their own data set. I have several videos that demonstrate how quick and easy it is to load and analyze data, but interest has been minimal so far. I feel like the inventor of a new kind of car engine that claims to get 2x the MPG while delivering the same horsepower, but can't get anyone to take the free test drive and prove me right (or wrong).
- nawgz 4y ago
  Well, I can find exactly 0 information on how you've implemented this on your very own website. It's natural to be skeptical of someone who is afraid to share their implementation details but claims best-in-class results, isn't it?
  - didgetmaster 4y ago
    Didgets is a little startup trying to get some traction. I am definitely not 'afraid to share implementation details', but I have not done a great job so far of prominently posting a lot of technical specifications and details on the website. So...are you promising to try it out if I tell you how I did it?

86 points by samlambert 4y ago

qorrect 4y ago

Is this different from 'compiling sql'?

tester756 4y ago
I think I'd say yea because AFAIK/IIRC query planners tend to use additional environment informations to make better plan. Maybe it would be closer to JIT?
maxbond 4y ago
A query planner will consider the idiosyncratic properties of your data to determine the most efficient way to execute your query, whereas a compiler is generally blind to the data your program will be processing. So if you execute the query "SELECT * FROM (a, b) WHERE a.foo = b.bar", if you have many rows in `a` but few rows in `b`, then it's much for efficient to scan `b` than `a`. The query planner will keep track of properties like this & come up with tricks to speed up execution. But in the sense that "everything is a compiler", yeah you could totally think of a query planner as a compiler that takes in your query's AST and a statistical description of your data and lowers it to a query plan.
- SigmundA 4y ago
  This seems pretty similar to profile guided optimization that say Java or .Net or Javascript can do since since it has access to runtime data during JIT Compilation.
  - maxbond 4y ago
    I hadn't made that connection but it's an excellent one!
VWWHFSfQ 4y ago
I've always thought of it as closer to an optimizing JIT compiler than just a regular translation of instructions to instructions.
- koolba 4y ago
  Not quite. A query plan is usually represented as a tree of steps to output the desired result. Each node would be a high level operation (e.g. a sort) or source of data (e.g. read rows from table), possibly pulling from other nodes beneath it. The actual compilation of the plan to machine code is possible and a few database systems do exactly that. But most process then nodes themselves or JIT specific node types represent simpler or more tightly defined operations.
  - kaba0 4y ago
    I think they meant it in a more abstract sense; also see relevant sister threads.
  - WJW 4y ago
    Don't most planners also take table and/or index statistics into account? AFAIK for most of the commonly used DBMSes, the same query will result in radically different query plans if the table contents are different enough.
jeff-davis 4y ago
Query planners often choose the algorithm based on data statistics (as described in the article). Compilers generally just make a lot of constant-factor improvements without changing the algorithm. One exception might be the tail-call optimization, which changes the space complexity of an algorithm. And that's one of the optimizations where the developer needs to know for sure whether it will br applied or not.

didgetmaster 4y ago

> Anyone that has worked with large databases can testify how slow queries can get. This is often due to the necessary indexes not being there, or something in the query that stops the database system from using the index. Choosing the right indexes to use, and the right order to fetch data in, proves to be the difference between a 10ms and 5s query. This seems incredibly intuitive. Anyone reading it would get the impression that query speed is very important for database users and that they would be eager to investigate any new technology that promised a substantial improvement in query performance. Yet, I have found the opposite. I created a new kind of database that shows incredible performance gains when compared with mainstream databases like SQLite (https://www.youtube.com/watch?v=Va5ZqfwQXWI https://www.youtube.com/watch?v=Va5ZqfwQXWI) for simple and complex queries against tables of all sizes. It is able to do this without needing to create separate indexes on all the columns in the WHERE clause. The software is in open beta and available for free download at (https://www.Didgets.com https://www.Didgets.com) but it is like pulling teeth to get people to try it out. If I post something like this on HN, I usually get lots of comments about how my claims are impossible (or at least improbable) but few are willing to actually test it themselves on their own machine with their own data set. I have several videos that demonstrate how quick and easy it is to load and analyze data, but interest has been minimal so far. I feel like the inventor of a new kind of car engine that claims to get 2x the MPG while delivering the same horsepower, but can't get anyone to take the free test drive and prove me right (or wrong).

nawgz 4y ago
Well, I can find exactly 0 information on how you've implemented this on your very own website. It's natural to be skeptical of someone who is afraid to share their implementation details but claims best-in-class results, isn't it?
- didgetmaster 4y ago
  Didgets is a little startup trying to get some traction. I am definitely not 'afraid to share implementation details', but I have not done a great job so far of prominently posting a lot of technical specifications and details on the website. So...are you promising to try it out if I tell you how I did it?