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

Our previous post about TPC-DS Q03 was pretty straightforward. Just when you thought it was safe to make a cup of tea and celebrate, the TPC-DS council hits you with this:

Where do we start? The key to optimizing this query is to very carefully consider what we can safely say about the Common Table Expression (CTE) that is being used six times here.

The CTE is a UNION ALL of the three sales fact tables used in TPC-DS. We first notice that all three components of the union have this general shape:

Now we can make some observations:

• c_customer_id is practically unique—we can know this because stats tell us that nd(c_customer_id)≈|customer|≈ 12M.
• d_year is going to have a cardinality proportional to the overlap between date_dim and the sales tables. We know from previous queries that this is around nd(d_year) / 40 ≈ 5.
• Because we are grouping by something that is unique (c_customer_sk and d_year), the total size of the grouped result is no larger than around 60 million (5 * 12 million).

Materializing CTE: A very bad idea

Exactly the same expression is used six times in Q04. You might think it would be a good idea to first materialize the CTE expression, grouping all three legs of the UNION ALL and saving the result to memory or disk. 

You would be wrong about that idea.

To see why, consider some of the filters on the CTE. For our example, look at the t_s_firstyearreference to the CTE:

t_s_firstyear.sale_type = 's' AND t_s_firstyear.dyear = 2001

First, we observe that the filter on sale_type has an interesting property: it can apply only to one leg of the union. To see this, let’s look at the rough shape of UNION ALL in the CTE:

We notice that all of six users of the CTE have a filter on sale_type. In other words, they each operate on only a single leg of the union. So, every reference to the CTE is actually a reference to a leg of the union, not to the entire union.

Additionally, each leg of the union is filtered by one of these:

• dyear = 2001
• dyear = 2001 + 1

So, all six users of the CTE are on non-overlapping parts of the space. Materializing the join only to filter it down would be slower than simply operating on each of the six non-overlapping sets. At least, it would be if you could find the matching rows quickly, which we can do in Yellowbrick because of its fast scan engine.

Static elimination and pushdown

Using our previous observations, we can now express the join in this query in a new way:

Here we can see what is really going on in this query: It’s a join across six non-overlapping row fractions of the three fact tables.

JOIN order

With the static elimination, all that remains is to estimate which of the six fractions is larger.

It turns out that not all customers shop online all the time, so the web_sales leg is smaller than that of the rest. However, this is quite difficult to estimate, because every customer in web_sales has, at some point, shopped online—just not every year, and not in the years we care about. Consider this query:

The table below shows the result (for context: nd(ws_bill_customer_sk) ≈ 12M):

Even with multicolumn stats, it is difficult to know that this particular distribution is what we find in the data. From a planner perspective, it looks as if the join order doesn’t matter much.

However, we can say something with a degree of certainty. Consider this filter:

If this filter does anything at all, which it does, we should try to harvest it. The join order should be:

1. t_c_firstyear * t_c_secyear: Calculate (A) and (C) above.
2. t_s_firstyear * t_s_sec_year: Calculate (B) above.
3. Join 1 and 2, harvesting the filter in (A) and (B).
4. Join (t_w_firstyear * t_w_secyear): Calculate (D) above.
5. Join 3 with 4, harvesting the (C) and (D) filters.

Saving memory

When users query data, they often drag needless columns around. Consider the outer query:

However, the CTE itself projects out:

Projecting all these columns out is simply not necessary (although we still have to GROUP BY them for correctness). The planner can carefully prune everything in five of the CTEs, except:

• customer_id
• dyear

For the final CTE (t_s_secyear), we need only project:

• customer_id
• customer_first_name
• customer_last_name
• customer_email_address
• dyear

Pruning in this way saves memory in has tables and speeds up the query.