Monthly Archives: March 2011

Hope is not a strategy

Imagine a carpenter who needs to cut a piece of wood in half but does not know what tools are available for the job until he looks inside his tool bag to find out. With luck, he will find a wood saw – but he might only find a chisel – or worse yet, just a screwdriver…

In much the same way, the query optimizer in a relational database has a lousy tool bag and is left to make the best of a bad job. The available tools are unsatisfactory for all of the following reasons

  • Any indexes that do exist are unlikely to be the best possible for the specific query
  • It is quite possible that one or more of the required indexes are missing altogether
  • The data distribution statistics used to decide on the best query plan are at best imprecise
  • These table statistics may not be up to date and may be wholly wrong
  • The statistics about a table immediately become junk following a join with another table
  • The number of possible combinations of table joins is often so immense that not all of them can be evaluated

In general, the choice of an execution plan is based on heuristics and assumptions which make the process less like a deterministic optimisation and more like a lottery – where hope is all there is.

All join together

In this post we will look at the common join strategies in use today to see why they struggle to perform well.

Let us assume that we are joining the following tables together by an equi-join between the first column in each table.

To understand the virtuous characteristics of a join strategy it helps to consider a particularly poor strategy first and the most naive strategy for a join is to initially perform a cross-join, where every row in table B is repeated for every row in table A,  and then scan the cross-join result to filter out rows where the join conditions (and any other predicates) are false.

The cross join of these tables would be

And subsequent filtering by an equi-join on column A1=B1 would give

Intuitively, this feels like a very poor strategy because there are two very striking aspects about it

  • The final result returns very few rows; yet the cross-join generated a significant  number of irrelevant rows which increased the load on the subsequent filtering stage. We would describe this characteristic as Late Attenuation – where irrelevant rows are retained until late into the join process.
  • Whole rows were processed from the very beginning of the process and this increased the load on both the cross-join and the filtering stage. We would describe this is as Early Materialization – where whole rows are visited or materialised very early within the join process.

Late attenuation is particularly troublesome in the context of a selective OLTP query where fast response times are sought. For example, if selecting only the employees that work within a single department, it would be unfortunate to have to inspect  all of the employees to ascertain this.

Early materialization is especially unfortunate in the context of an OLAP query where the majority of rows need to be evaluated by the join, yet only a few columns contribute to the final result. For example, if summing employee salaries by department, it would be an unnecessary overhead to process all of the other employee attributes as part of the join process.

Both late attenuation and early materialization will increase the volume of data transferred between memory and CPU cache; between storage and memory; and over the network between server nodes. Both behaviours will tend to saturate transfer bandwidth and this can become particularly acute in joins distributed across a network. Joins across networks typically do not scale well precisely because of these specific characteristics.

Both of these behaviours are clearly undesirable and an efficient join process will promote the following for all tables involved in a join.

  • Early Attenuation – discard irrelevant rows as early as possible.  In particular, discard irrelevant rows without  having to visit them.
  • Late Materialization – materialise relevant rows as late as possible. In particular, materialise only the rows relevant to the final join result.

Therefore we would expect a good join strategy to execute these phases in the following order

  • Attenuate
  • Correlate
  • Materialise

Where correlation involves the association of respective rows between the joined tables.

Simply stated, it is inefficient to materialise rows that will not appear in the final join result and it is inefficient to attempt to correlate rows that cannot have any correspondence with each other.

Now that we know what a good join strategy looks like, let’s look at how typical join strategies fare in these respects…

Nested Loop Join. A nested loop join iteratively steps through rows from an outer (independent) table and references rows from an inner (dependent) table that join with the current outer row.  Ideally, the inner table will be small or will contain a suitable index to reduce the cost of accessing each inner row. If indexes are missing on either table then a full table scan will lead to early materialization in that table. Regardless of the indexes available,  there will always be late attenuation of the outer table because each candidate row in the outer table must be iterated before it can be eliminated by the join with the inner table.

Sort Merge Join. A sort merge join merges both join columns after they have been sorted.  The sort may be achieved by a scanning a suitable index in the required sort order; but without an index available, a table must be scanned and then sorted and this clearly leads to early materialization. For both tables, every join candidate must be visited before it can be eliminated by a merge operation and therefore there is always late attenuation of both tables.

Hash Join. A hash join assigns rows from both tables to corresponding hash buckets.  If there are no suitable indexes available, then a full table scan will lead to early materialization of that table. Even with a suitable index in place, all of the candidate index entries from that table must be scanned to populate the hash buckets and again there is late attenuation of both tables.

The indexed nested loop join is commonly used in selective query joins because the inner table is attenuated early and materialised late; but the cost of correlation is high because it requires a random index lookup for each outer row and hence this strategy is rarely chosen for large joins where many rows must be correlated. Sort merge and hash joins are used in non selective joins because their cost of correlation is much lower; while their late attenuation characteristic make them both unsuitable for selective queries that demand a fast response time.

The join strategies above exhibit performance crippling characteristics which become even more acute when indexes are missing. A conventional workaround to the overall join performance problem is to create specific join indexes across the tables and columns being joined; but these indexes also require the inclusion of the predicated columns in the query to avoid full index scans. So yet again, this solution requires a-priori knowledge of the queries expected and exerts a huge overhead on the inserts and updates to the tables being indexed – particularly where a single row insert results in multiple join index inserts because of the corresponding join cardinality.

It is understandable why many designers opt for de-normalisation as a better bet.