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

In our previous post about using TPC-DS queries to illustrate how the Yellowbrick query optimizer works, we introduced TPC-DS Query 1 (Q01). This post tackles Query 2 (Q02), focusing on the subtle tricks required to handle the fact tables in TPC-DS.

TPC-DS splits its sales information into three different fact tables, an approach typical in the real/non-benchmark world, too. In TPC-DS, these tables are

• web_sales
• catalog_sales—twice the size of web_sales
• store_sales—twice the size of catalog_sales (obviously, the schema was designed pre COVID-19)

Many queries in TPC-DS will UNION these tables together in various ways. Q02 is the first example:

Estimating UNION ALL

Consider this part of the query:

Here, we construct a Common Table Expression (CTE) we will later join to date_dim. But how should we estimate the cardinality of this join?

With statistics, it’s easy to estimate the cardinality of the UNION ALL. However, to estimate the cardinality of the join itself, we have a few choices.

• We know the number of distinct sold_date_sk in each of the union branches. But even with very advanced statistics information, it is difficult to say how many distinct values the UNION ALL of them has and what the overlap with the date_dim actually is.
• We know there is a foreign key from ws_sold_date_sk to d_date_sk and another foreign key from cs_sold_date_sk to d_date_sk. Because of this, we can know that the join to date_dim of the UNIONmust yield:
  • The SUM of the two inputs
  • MINUS the null rows on either ws_sold_date_sk and cs_sold_date_sk

The second choice obviously provides the superior estimation method. Using primary/foreign key relationships such as this one is a key (pardon the pun) optimization for query planners: It rewards database designers who build good schemas and properly declare keys with a better query plan. This is why proper database design is very important for getting the most out of relational databases.

Estimating GROUP BY

From an estimation perspective, this join is of particular interest:

Here, we are joining on something that is not a key (d_week_seq)—which in general means there is plenty of opportunity to get the estimate wrong.

How well we estimate this join depends a lot on what we can say about the following construct:

Estimating aggregation is generally a difficult problem (because the cardinality of the output depends on the correlation of the input columns). However, for this particular join, we can be very confident that the cardinality is likely to be the same as the cardinality of d_week_seq, because we are grouping on only a single column.

The second part of the join requires us to reason about the cardinality of d_week_seq within date_dim, given the filter of d_year = 2001. Here, a two-dimensional histogram of (d_week_seq, d_year) would be a great help. Unfortunately, the number of possible histograms you’d have maintain in this manner would grow so fast that you’d often run out of memory/disk to hold them. However, we can say that the number of distinct values can’t possibly exceed the number of rows estimated for d_year = 2001—i.e., 365. That gives us a reasonable cap.

CTE materialization

In Q01, we saw that although the same CTE is used multiple times in a query, it may not be a good idea to materialize the result. However, for Q02, we are looking at some very significant savings. Consider the following construct:

The output size of something grouped by d_week_seq is obviously a tiny fraction of the input size of wcsc (which you may recall is the UNION of catalog_sales and web_sales). Even with a high-speed column store, there is a bit to be gained by materializing this intermediate result, particularly because expressions such as the following are very expensive to evaluate:

Human beings really like strings; we find it easy to remember and work with them. However, machines pay a significant price when comparing strings. For a CPU, it’s orders of magnitude faster to compare integers than it is to compare strings. There are seven of these string compares for every row in wcsc—which becomes billions of compares during query execution. So, it’s worthwhile to save the overhead of calculating these multiple times by materializing the intermediate result.

JOIN order

In this query, we don’t have a lot of choices with regard to join ordering. The dependencies between the joins force an order. The order is:

• Join wscs to date_dim—materialize the result of wswscs
• Join the two copies of wswscs (for 2001 and 2002)
• Join the two above copies with each other on d_week_seq