4 ms·

For several days I'm having trouble finding good resources on _implementation_ for query execution/planning (predicates, existing indices <<especially composite

For several days I'm having trouble finding good resources on _implementation_ for query execution/planning (predicates, existing indices <<especially composite ones - how to locate them during planning etc>>, joins etc). Google is spammed with _usage_. Anybody has some recommendations at hand? ps. the only one I found was CMU's Database Group resources, which are great

malfist 3y ago
It seems content farms, farming keywords with just fluff has taken over google. Can't find how to do anything anymore, just pages and pages of people talking about doing something. You could try your query on a different search engine. I've had good luck with kagi.
dattl 3y ago
I find the Advanced Databases Course from CMU an excellent resource. https://15721.courses.cs.cmu.edu/spring2023/schedule.html https://15721.courses.cs.cmu.edu/spring2023/schedule.html You might want to look into academic papers, e.g., T. Neumann, Efficiently Compiling Efficient Query Plans for Modern Hardware, in VLDB, 2011 https://www.vldb.org/pvldb/vol4/p539-neumann.pdf https://www.vldb.org/pvldb/vol4/p539-neumann.pdf
mrkeen 3y ago
I just tried adding 'relational algebra' in front of my 'query planning' query, and at a glance it skews more towards implementation.
aidos 3y ago
My go to pointer for this is to read the Postgres docs (and / or source - which is also super readable). https://www.postgresql.org/docs/current/planner-optimizer.html https://www.postgresql.org/docs/current/planner-optimizer.ht...
skywhopper 3y ago
It’s out of date and probably has less detail than I remember but I got a lot out of “Inside Microsoft SQL Server 7.0” which does deep dives into storage architecture, indices, query planning etc from an MSSQL specific POV. The book was updated for SQL Server 2003 and 2008. Obviously the book also has a ton of stuff about MS specific features and admin functionality that’s not really relevant, and I’m sure there are better resources out there, but I’ve found the background from that book has helped me understand the innards of Oracle, MySQL, and Postgres in the years since.
gavinray 3y ago
There's an entire 700-page book about this you can access for free here: "Building Query Compilers" https://pi3.informatik.uni-mannheim.de/~moer/querycompiler.pdf https://pi3.informatik.uni-mannheim.de/~moer/querycompiler.p... EDIT: You also might get use out of TUM's course "Database Systems on Modern CPU Architectures" The year that contains all the video lectures is 2020: https://db.in.tum.de/teaching/ss20/moderndbs/?lang=en https://db.in.tum.de/teaching/ss20/moderndbs/?lang=en
- hobofan 3y ago
  I'd also recommend "How Query Engines Work" for a good practical exercise in the topic: https://andygrove.io/how-query-engines-work/ https://andygrove.io/how-query-engines-work/ . I think one should go already have a high-level overview of what individual parts make up a query engine and what there purpose is, as it only touches on that lightly.
  - gavinray 3y ago
    I own the book and would agree -- only reason I didn't suggest this is that the areas on query-planning and optimization are a bit thin. IMO it's great if you want a holistic view of building a query engine start-to-finish with just enough detail to build a basic implementation. I probably learned more from the ~100 pages in this book than I did from most other sources.
sobellian 3y ago
I don't know if this has the level of detail you're looking for, but you might want to check https://www.sqlite.org/optoverview.html https://www.sqlite.org/optoverview.html and https://www.sqlite.org/queryplanner.html https://www.sqlite.org/queryplanner.html.
- Sesse__ 3y ago
  The SQLite optimizer is really primitive. You generally don't want to be using it as a template if you can avoid it; it's good for OLTP but can't handle many-way joins well.
Sesse__ 3y ago
Generally, this is a specialist topic, so you're unlikely to find e.g. good textbooks. It depends a bit on how deep you want to go and what specific parts you're interested in, though. (Query execution is pretty much entirely separate from planning, for one.) The best join optimizer paper I know of is still the original Selinger paper (https://courses.cs.duke.edu/compsci516/cps216/spring03/papers/selinger-etal-1979.pdf https://courses.cs.duke.edu/compsci516/cps216/spring03/paper...). It doesn't support outer joins and there are more efficient techniques by now, but anyone looking at a System R-like optimizer can read this and feel right at home. (There is also the Volcano/Cascades school of optimizers, which is rather different from System R, but I've found even less information on it.) As others have said, Postgres' source and documentation is good. In particular, src/backend/optimizer/README contains a number of interesting things that you won't find a lot of other places. (The Postgres optimizer doesn't always use the latest fancy designs, but it's generally very polished and pretty easy to read.) I can also echo Andy Pavlo's courses (at CMU), they're pretty much the only ones who will explain this stuff to you online. The “Building Query Compilers” PDF is rather incomplete and there's a lot of stuff I never cared for in there, but it contains several key papers from Moerkotte et al if you actually want to implement the modern stuff (DPhyp etc.). In general, most of the modern System R-like stuff (how to efficiently deal with outer joins, how to deal with interesting orders, how to deal with large queries) comes from the groups of Moerkotte and/or Neumann; all of these things had solutions before them, but less efficient and/or powerful and/or elegant. Finding an applicable index isn't hard (you generally just try to see if it hits a predicate—a so-called “sargable predicate”, for SARG = Search ARGument). Estimating selectivity is hard. Estimating selectivity through joins is perhaps the hardest problem in optimizers, and nobody has truly solved it. This was one of the things I never really got to; there are so many hard subproblems. Like, for something that sounds really simple but isn't, what do you do if you have predicates A=x AND B=y AND C=z and you happen to have indexes on (A,B) and (B,C) (with selectivity/cardinality information) and want a selectivity for all three combined? There are papers that literally require you to build a “second-order cone programming” solver to solve this problem :-)

malfist 3y ago

It seems content farms, farming keywords with just fluff has taken over google. Can't find how to do anything anymore, just pages and pages of people talking about doing something. You could try your query on a different search engine. I've had good luck with kagi.

dattl 3y ago

I find the Advanced Databases Course from CMU an excellent resource. https://15721.courses.cs.cmu.edu/spring2023/schedule.html https://15721.courses.cs.cmu.edu/spring2023/schedule.html You might want to look into academic papers, e.g., T. Neumann, Efficiently Compiling Efficient Query Plans for Modern Hardware, in VLDB, 2011 https://www.vldb.org/pvldb/vol4/p539-neumann.pdf https://www.vldb.org/pvldb/vol4/p539-neumann.pdf

mrkeen 3y ago

I just tried adding 'relational algebra' in front of my 'query planning' query, and at a glance it skews more towards implementation.

aidos 3y ago

My go to pointer for this is to read the Postgres docs (and / or source - which is also super readable). https://www.postgresql.org/docs/current/planner-optimizer.html https://www.postgresql.org/docs/current/planner-optimizer.ht...

skywhopper 3y ago

It’s out of date and probably has less detail than I remember but I got a lot out of “Inside Microsoft SQL Server 7.0” which does deep dives into storage architecture, indices, query planning etc from an MSSQL specific POV. The book was updated for SQL Server 2003 and 2008. Obviously the book also has a ton of stuff about MS specific features and admin functionality that’s not really relevant, and I’m sure there are better resources out there, but I’ve found the background from that book has helped me understand the innards of Oracle, MySQL, and Postgres in the years since.

gavinray 3y ago

There's an entire 700-page book about this you can access for free here: "Building Query Compilers" https://pi3.informatik.uni-mannheim.de/~moer/querycompiler.pdf https://pi3.informatik.uni-mannheim.de/~moer/querycompiler.p... EDIT: You also might get use out of TUM's course "Database Systems on Modern CPU Architectures" The year that contains all the video lectures is 2020: https://db.in.tum.de/teaching/ss20/moderndbs/?lang=en https://db.in.tum.de/teaching/ss20/moderndbs/?lang=en

hobofan 3y ago
I'd also recommend "How Query Engines Work" for a good practical exercise in the topic: https://andygrove.io/how-query-engines-work/ https://andygrove.io/how-query-engines-work/ . I think one should go already have a high-level overview of what individual parts make up a query engine and what there purpose is, as it only touches on that lightly.
- gavinray 3y ago
  I own the book and would agree -- only reason I didn't suggest this is that the areas on query-planning and optimization are a bit thin. IMO it's great if you want a holistic view of building a query engine start-to-finish with just enough detail to build a basic implementation. I probably learned more from the ~100 pages in this book than I did from most other sources.

sobellian 3y ago

I don't know if this has the level of detail you're looking for, but you might want to check https://www.sqlite.org/optoverview.html https://www.sqlite.org/optoverview.html and https://www.sqlite.org/queryplanner.html https://www.sqlite.org/queryplanner.html.

Sesse__ 3y ago
The SQLite optimizer is really primitive. You generally don't want to be using it as a template if you can avoid it; it's good for OLTP but can't handle many-way joins well.

Sesse__ 3y ago

Generally, this is a specialist topic, so you're unlikely to find e.g. good textbooks. It depends a bit on how deep you want to go and what specific parts you're interested in, though. (Query execution is pretty much entirely separate from planning, for one.) The best join optimizer paper I know of is still the original Selinger paper (https://courses.cs.duke.edu/compsci516/cps216/spring03/papers/selinger-etal-1979.pdf https://courses.cs.duke.edu/compsci516/cps216/spring03/paper...). It doesn't support outer joins and there are more efficient techniques by now, but anyone looking at a System R-like optimizer can read this and feel right at home. (There is also the Volcano/Cascades school of optimizers, which is rather different from System R, but I've found even less information on it.) As others have said, Postgres' source and documentation is good. In particular, src/backend/optimizer/README contains a number of interesting things that you won't find a lot of other places. (The Postgres optimizer doesn't always use the latest fancy designs, but it's generally very polished and pretty easy to read.) I can also echo Andy Pavlo's courses (at CMU), they're pretty much the only ones who will explain this stuff to you online. The “Building Query Compilers” PDF is rather incomplete and there's a lot of stuff I never cared for in there, but it contains several key papers from Moerkotte et al if you actually want to implement the modern stuff (DPhyp etc.). In general, most of the modern System R-like stuff (how to efficiently deal with outer joins, how to deal with interesting orders, how to deal with large queries) comes from the groups of Moerkotte and/or Neumann; all of these things had solutions before them, but less efficient and/or powerful and/or elegant. Finding an applicable index isn't hard (you generally just try to see if it hits a predicate—a so-called “sargable predicate”, for SARG = Search ARGument). Estimating selectivity is hard. Estimating selectivity through joins is perhaps the hardest problem in optimizers, and nobody has truly solved it. This was one of the things I never really got to; there are so many hard subproblems. Like, for something that sounds really simple but isn't, what do you do if you have predicates A=x AND B=y AND C=z and you happen to have indexes on (A,B) and (B,C) (with selectivity/cardinality information) and want a selectivity for all three combined? There are papers that literally require you to build a “second-order cone programming” solver to solve this problem :-)