TPC-DS And The Yellowbrick Query Optimizer (TPC-DS Q05)

In our previous post about TPC-DS Q04, we discussed options for using the common table expression (CTE). This post covers Query 5 (Q05), the first query to introduce ROLLUP. It is a query that looks at sales from each of the three channels (web, store, and catalog) and compares them with returns from that same channel.

Because sales and returns for each channel are captured in their own fact tables, the query has to perform a lot of UNION operators to bring the data from each channel into approximately the same form.

Join order

First, let’s consider join ordering. Each of the three channels has very similar subqueries, so we can look at just one and generalize to the others. For example, consider the store_sales and store_returnssubquery:

When considering join order, we always want to reduce the stream as much a possible with each join. In this case, the order is obvious:

• Join the UNION of store_sales with store_returns to date_dim, harvesting the filter on d_date
• Join to store, expecting no filtering at all

In the case of the wsr subquery, there is an additional LEFT JOIN:

Because we know there is a key on the item/order_number combination, this join must preserve row count, which means we should join it after store and date_dim.

ROLLUP

The rollup aggregation can be expressed in several ways. The most straightforward is perhaps this: 

1. Calculate the standard grouping of columns without the rollup values
2. Write this into a temporary table
3. Query this table with one or more subqueries combined with a UNION ALL, each subquery rolling up the totals as per the user’s request

This approach turns out to be suboptimal. First, it passes over the data several times, resulting in a several scans of the input. Second, Step 2 can require a very significant amount of temporary storage. Finally, this approach cannot reuse previous aggregates to calculate the higher-level rollup values.

The new (as of version 5.3) ROLLUP operator in Yellowbrick uses a different approach. Instead of writing a temporary value, it calculates all rollup values for each input row while that row is still in cache in the GROUP BY node. It does so internally by performing a loop join with a special input expression the query optimizer generates as part of the query. This turns out to be an effective approach to calculating ROLLUP and other forms of GROUPING sets. It is also an example of how the optimizer can often rewrite a user query into something that can be expressed in the execution engine by using only existing operators instead of introducing new engine logic. In this case, the optimizer can reuse the existing GROUP BY and LOOP JOIN operators to perform ROLLUP (and all the other variants of GROUPING set).

Click here to read the next blog in this series where we examine TPC-DS Q06.