2 posts tagged with "query-optimizer"

If your queries join five, ten or fifteen tables, CamusDB now plans them better and runs them faster. This post explains what changed in plain terms, so you can see what to expect from your own queries.

A join query names its tables and its conditions. It does not say in which order to join the tables. The database picks the order, and the order decides how much data the query reads. A good order starts from the few rows that survive the filters. A bad order can build millions of rows and then throw most of them away.

The Join Order Benchmark (JOB) is a set of 113 queries from a 2015 paper by Leis and five co-authors. The queries run over a movie database of 21 tables, and each one joins 4 to 17 tables. The paper tested mature databases and found that their estimates of how many rows a join returns were often wrong by orders of magnitude. The error grows with each join, and a wrong estimate leads to a slow plan. The benchmark exists to show that weakness.

One of the most interesting parts of building CamusDB is the query optimizer. It might also be one of the most complex pieces of machinery in the whole database.

At first, a query optimizer sounds simple: receive a SQL query and decide how to run it. But the more features a database supports, the harder that decision becomes. A query can use a table scan, an index lookup, an index range scan, a hash join, a merge join, a nested loop join, a sort, an aggregate, a derived table, or a subquery. Each option can be correct, but not every option is fast.

The optimizer's job is to choose a good plan before the query runs.