Necessary and Sufficient

The only reason databases store data is so you can later query that data. To query the data you give the database a query, usually in the form of SQL. The database will them examine the query, check to see if it already has a cached query plan that will work for this query, and if not go ahead a create a query plan before executing the query with that plan. There is a small overhead to pay when creating query plans, and the quality of the query plan is influenced by the parameters used in the query. It is for these reasons that there are fanatical arguments over whether it is more performant to use stored procedures (pre-defined queries that have already had a plan created), or free form SQL that has it's query plan recalculated every time using the specific parameters given. I'm not going to open that can of worms but it did get me thinking about query optimisation...

How many plans does the query optimiser need to evaluate and how does it do so?

It is reasonable to assume that the difficultly of optimizing a query is proportional to the solution space for alternative execution plans. Since the solution space is dependent upon the complexity of the input query let us consider a query which joins n tables and examine it formally.

Let J(n) denote the number of different join orderings when joining n tables.

Let T(n) denote the number of different binary tree shapes that can be found for a collection of n leaf nodes.

It should be intuitive that J(n) = T(n) * n! because there are n! ways to organise the leaf nodes of a binary tree, and there are T(n) different tree shapes. But how do we calculate T(n)? First recall that a binary tree has at most 2 branches which are in fact binary sub-trees. Thus, the number of permutations for a binary tree is the product of the number of permutations for each of it's sub-trees summed over all possible leaf node splittings between the left and right sub-trees:

where T(1) = 1 is the base case.

It turns out that T(n) = C(n-1), where C(n) = the n-th Catalan number:

Substituting T(n) = C(n-1), we get:

The table below shows that this equation grows extremely fast!

In other words, if you have, say 7 tables being joined, the query optimiser has 665,280 possible ways of doing this and therefore needs to evaluate quite a large number of possible plans. Of course there are more things to query plan optimisations than just working out table join order,including proper choices of access methods and indexes, but the point is the solution space in this optimisation problem grows extremely quickly as queries become more complex.

Typically, optimisation is performed using dynamic programming since the problem has the classic traits of overlapping sub-problems and optimal substructure but given the explosion of search space shown above it's not feasible to evaluate all possible plans. In other words, the optimiser is sub-optimal but it represents a best guess.

The seminal paper on cost-based query plan optimisation is Access Path Selection in a Relational Database Management System by Pat Selinger et al (pages 103-114 in this excellent manuscript). Be warned - it has the dot matrix printer font that makes it hard not to notice the paper was written in 1979!