Here we look at two TPC-H queries whose execution plans are relatively straightforward and look at Virtuoso performance metrics. On one hand; this is an introduction to query plans; on the other hand, a case study in tuning Virtuoso and understanding what goes on. The choke points outlined in TPC-H Analyzed are mentioned where applicable, with some extra commentary.

Q1 -- Scan, I/O, Aggregation

The query is below. The date is a parameter (a value near the end of the l_shipdate range is used), so most of the columns get read.

SELECT                                                               l_returnflag,
          SUM(l_quantity)                                        AS  sum_qty,
          SUM(l_extendedprice)                                   AS  sum_base_price,
          SUM(l_extendedprice * (1 - l_discount))                AS  sum_disc_price,
          SUM(l_extendedprice * (1 - l_discount) * (1 + l_tax))  AS  sum_charge,
          AVG(l_quantity)                                        AS  avg_qty,
          AVG(l_extendedprice)                                   AS  avg_price,
          AVG(l_discount)                                        AS  avg_disc,
          COUNT(*)                                               AS  count_order
    FROM  lineitem
   WHERE  l_shipdate <= dateadd('DAY', -90, CAST ('1998-12-01' AS DATE))
GROUP BY  l_returnflag,
ORDER BY  l_returnflag,

We note that a count of a non-nullable column is the same as COUNT (*) and that AVG of a non-null column is SUM (column) / COUNT (*). So COUNT (*) occurs 4 times, and SUM (l_extendedprice) and SUM (l_quantity) each occur twice. The grouping columns have few distinct values.

TPC-H Analyzed suggests to use an array-based GROUP BY, because there can only be 64K combinations of 2 single-character values. The grouping keys are declared CHAR (1) and non-nullable. The Virtuoso implementation does not do this, though.

This query has been treated in many papers because it cannot be implemented in very many ways, it is easy to understand, and it still illustrates some basic metrics.

One execution on warm cache is between 3.9s and 4.7s. One execution with the data coming from OS disk cache is 11.8s. One execution with the data coming from 2 SSDs is 22s. Five concurrent executions from warm cache are 17.3s for the fastest and 20.5s for the slowest. A single threaded execution from warm cache is 58.4s.

We see that scaling is linear; i.e., 5 times the work takes a little under 5x longer. The parallelism is reasonable, with 14.6 speedup from 24 threads on 12 cores. Splitting the work into 48 software threads, time-sliced on 24 hardware threads, does not affect execution time. The work thus appears to be evenly spread on the threads.

It may be interesting to see how much data is transferred. To see the space consumption per column --

  SELECT  TOP 20 * 
    FROM  sys_index_space_stats 
ORDER BY  iss_pages DESC ;

-- followed by --

  SELECT  coi_column, 
          SUM (coi_pages) / 128 
    FROM  sys_col_info 
GROUP BY  coi_column 

-- gives us the following --

L_COMMENT                        17893
PS_COMMENT                       10371
O_COMMENT                         7824
L_EXTENDEDPRICE                   4771
O_CLERK                           2744
L_PARTKEY                         2432
L_SUPPKEY                         2432
L_COMMITDATE                      1784
L_SHIPDATE                        1551
L_RECEIPTDATE                     1537
O_TOTALPRICE                      1181
C_COMMENT                         1150
L_QUANTITY                         960
O_ORDERKEY                         736
P_NAME                             729
PS_SUPPLYCOST                      647
O_CUSTKEY                          624
C_ADDRESS                          427
L_DISCOUNT                         424
L_TAX                              419
L_SHIPINSTRUCT                     412
L_SHIPMODE                         410
L_LINENUMBER                       394
L_RETURNFLAG                       394
L_LINESTATUS                       394
O_ORDERDATE                        389
P_COMMENT                          341
PS_SUPPKEY                         323
P_TYPE                             293
C_PHONE                            274
L_ORDERKEY                         268
PS_AVAILQTY                        201
P_RETAILPRICE                      161
C_ACCTBAL                          123
O_ORDERPRIORITY                     95
O_ORDERSTATUS                       94
S_COMMENT                           66

The total in allocated pages is 65.6 GB, of which 34.1 GB are accessed by the workload. The comment strings could be stream-compressed, bringing some speedup in load time due to less I/O. Also l_extendedprice, a frequently accessed column, could be represented with 4 bytes instead of 8. The working set could thus be cut down to about 28 GB, which may offer some benefit at larger scales. At any rate, for system sizing, the space utilization report is very useful.

The query execution profile is as below, with comments inline. The profile here is obvious, but we show this as a guide to reading future profiles which will be more interesting.

time   2.6e-06% fanout         1 input         1 rows
time   1.7e-06% fanout         1 input         1 rows
{ fork
time   2.1e-06% fanout         1 input         1 rows
{ fork

The time xx% line above each operator is the actual percentage of execution time taken by it, followed by the count of rows of output per row of input, followed by the actual rows of input. The below produced 591M rows of output for one row of input --

time        34% fanout 5.91599e+08 input         1 rows
 L_SHIPDATE <= <c 1998-09-02>

Below is the arithmetic of the query, followed by a sort (GROUP BY) operator.

After code:
      0: temp := artm  1  - .L_DISCOUNT
      4: temp := artm .L_EXTENDEDPRICE * temp
      8: temp := artm  1  + .L_TAX
      12: temp := artm temp * temp
      16: BReturn 0

Most of the time is spent below, in the GROUP BY. We notice that each needed aggregation is done once, so the common subexpressions are correctly detected.

time        66% fanout         0 input 5.91599e+08 rows
time     4e-05% fanout         4 input         1 rows
group by read node  
(.L_RETURNFLAG, .L_LINESTATUS, count_order, aggregate, sum_base_price, sum_qty, sum_charge, sum_disc_price)
time   6.2e-05% fanout         0 input         4 rows

The SUMs are divided by the COUNTs, and the rows are sorted.

      0: avg_qty := artm sum_qty / count_order
      4: avg_price := artm sum_base_price / count_order
      8: avg_disc := artm aggregate / count_order
      12: BReturn 0
Sort (.L_RETURNFLAG, .L_LINESTATUS) -> (sum_qty, sum_base_price, sum_disc_price, sum_charge, avg_qty, avg_price, avg_disc, count_order)
time   1.2e-05% fanout         4 input         1 rows
Key from temp (.L_RETURNFLAG, .L_LINESTATUS, sum_qty, sum_base_price, sum_disc_price, sum_charge, avg_qty, avg_price, avg_disc, count_order)

The data is returned to the client.

time   4.4e-06% fanout         0 input         4 rows
Select (.L_RETURNFLAG, .L_LINESTATUS, sum_qty, sum_base_price, sum_disc_price, sum_charge, avg_qty, avg_price, avg_disc, count_order)

Elapsed time and CPU%.

 3947 msec 2365% cpu,         6 rnd 5.99841e+08 seq         0% same seg         0% same pg 
Compilation: 0 msec 0 reads         0% read 0 messages         0% clw

This output is produced by the following sequence on the iSQL command line --

SQL> SET blobs ON;
SQL> PROFILE ('SELECT .... FROM .....');

We will next consider the CPU profile:

704173   33.0087  setp_chash_run
275039   12.8927  gb_aggregate
252751   11.8479  ce_dict_any_sets_decode
178304    8.3581  cha_cmp_2a
170819    8.0073  ce_dict_int64_sets_decode
127827    5.9920  chash_array_0
120994    5.6717  chash_array
60902     2.8548  ce_intd_any_range_lte
47865     2.2437  artm_mpy_double
38634     1.8110  ce_vec_int64_sets_decode
26411     1.2380  artm_sub_double
24794     1.1622  artm_add_double
13600     0.6375  cs_decode

For hardcore aficionados, the code may be found in the Virtuoso develop/7.x branch on The version is not exactly the same but close enough for the parts above. artm_* is arithmetic on typed vectors. As pointed out before, the arithmetic is with DOUBLEs, although users would prefer fixed point. There is, I believe, a MS SQL Server result with DOUBLEs, so using DOUBLEs would not disqualify a 100 GB TPC-H result.

The moral of the story is that an array-based aggregation without the chash_array* and cha_cmp* and only 1/3 of the setp_chash_run function would save upwards of a second of real time. The setp_ and cha_ are aggregation; the ce_* are column decompression and filtering. The arithmetic is not high in the sample but it could be sped up by 2-4x by SIMD, specially since AVX on Sandy Bridge and later does 4 DOUBLEs in a single instruction.

We note that the ce_filter_* function would drop off if the table were stored in date order, as then the top level index would show that all the values in the column matched, thus making it unnecessary to even read the l_shipdate column, except for the last part of the table. However this is a marginal slice of the time even now.

Q1 Conclusions

We have demonstrated good load balance and passed the required common sub-expressions exam. The array-based GROUP BY trick is unused but would save over 1s of real time, hence will be good value for only 100-200 lines of code.

Q3 -- Hash and Merge Joins

Next we look at JOINs by hash and index. Q3 is a relatively straightforward example, so we will go over the basics of JOIN type (i.e., whether by index or hash) and JOIN order. This will also show some scheduling effects.

The definition is:

SELECT TOP 10                                             l_orderkey,
               SUM(l_extendedprice * (1 - l_discount)) AS revenue,
    FROM  customer,
   WHERE  c_mktsegment = 'BUILDING'
     AND  c_custkey = o_custkey
     AND  l_orderkey = o_orderkey
     AND  o_orderdate < CAST ('1995-03-15' AS DATE)
     AND  l_shipdate > CAST ('1995-03-15' AS DATE)
GROUP BY  l_orderkey,
ORDER BY  revenue desc,

The profile, comments inline, is:

time   6.7e-06% fanout         1 input         1 rows

Make a hash table with c_custkey for all customers with c_mktsegment building. For a hash join build side, the time above the hash filler line is the time for making the hash table from the buffered rows. The time above the sort ... hf ... line is the time for buffering the rows that go into the hash table. The other times in the hash filler block are for the operators for getting the data, and are not related to making the hash table.

time      0.72% fanout         1 input         1 rows
{ hash filler

We see that the actual cardinality of customer is close to what was predicted. The actual number is on the line with time; the predicted is on the line with the index name customer.

time      0.63% fanout 3.00019e+06 input         1 rows
CUSTOMER     3e+06 rows(.C_CUSTKEY)
time     0.089% fanout         0 input 3.00019e+06 rows
Sort hf 34 (.C_CUSTKEY)
time   9.2e-06% fanout         1 input         1 rows
{ fork
time   5.2e-06% fanout         1 input         1 rows
{ fork


The below is a merge of a scan of orders and a hash join to customer. The orders table is scanned, first reading o_orderdate and o_custkey, on which there are selections. The o_orderdate is a range check that is true of about 1/2 of the rows. The other condition is an invisible hash join against the customer hash table built above. This selects 1/5 of the rows on the average. So we see that for a total of 150M orders, the fanout is 14.5M, about 1/10, as predicted. The 6.1e7 rows on the line with orders represents the estimate based on the orderdate condition. The card 0.2 on the hash filter line is the prediction for the hash join selectivity.

We note that since no order has more than one customer, the JOIN is always cardinality-restricting, hence can be merged into a scan. Being merged into a scan, it becomes run-time re-orderable with the condition on o_orderdate. The conditions are evaluated and arranged at run time in the order of rows eliminated per unit of time.

The expression "hash partition + bloom" means that the hash join could be partitioned if the hash table did not fit in memory; i.e., there could be several passes over the data. This is not here the case, nor is this generally desirable. The bloom means that the hash is pre-filtered with a Bloom filter, which we will see in the CPU profile.

time        30% fanout 1.45679e+07 input         1 rows
 O_ORDERDATE < <c 1995-03-15>
hash partition+bloom by 41 (tmp)hash join merged always card       0.2 -> ()

The below is the hash join operator that in fact was merged into the table scan above.

time    0.0016% fanout         1 input 1.45679e+07 rows
Hash source 34 merged into ts        0.2 rows(.O_CUSTKEY) -> ()

Below is the index-based access to lineitem. This is a de facto merge-join since the o_orderkeys are generated in order by the scan. One in 10 l_orderkeys is selected. Each of these has an average of 4 lineitems. Of these 4, the cost model predicts that 2.7 will be selected based on the additional condition on l_shipdate. The actual number of rows matched is in fact much lower since the date selection is heavily anti-correlated with the date selection on orders. In other words, an order tends to be shipped soon after the orderdate.

time        16% fanout   0.20508 input 1.45679e+07 rows
After code:
      0: temp := artm  1  - .L_DISCOUNT
      4: temp := artm .L_EXTENDEDPRICE * temp
      8: BReturn 0


The query has a GROUP BY that includes the high cardinality column, l_orderkey, with 150M distinct values. The GROUP BY is therefore partitioned.

This means that the previous part of the query is run on multiple threads, so that each thread gets an approximately equal number of lines of orders. For the GROUP BY, the threads pass each other chunks of data so that each grouping key can only end up in one partition. This means that at the end of the GROUP BY, there are multiple hash tables with grouping results that are guaranteed non-overlapping, hence there is no need to add up (re-aggregate) the per-thread results. The stage operator passes data between the threads. This is also known as an exchange operator.

time         1% fanout         1 input 2.98758e+06 rows
Stage 2
time       1.4% fanout         0 input 2.98758e+06 rows
time       0.4% fanout 1.13104e+06 input         1 rows
group by read node  
(.L_ORDERKEY, .O_ORDERDATE, .O_SHIPPRIORITY, revenue)in each partition slice
time      0.36% fanout         0 input 1.13104e+06 rows
time   3.1e-05% fanout        10 input         1 rows
top order by read (.L_ORDERKEY, revenue, .O_ORDERDATE, .O_SHIPPRIORITY)
time   6.2e-06% fanout         0 input        10 rows

 1189 msec 2042% cpu, 1.45513e+07 rnd 2.08588e+08 seq   98.9053% same seg  0.952364% same pg 
Compilation: 1 msec 0 reads         0% read 0 messages         0% clw

This query also illustrates the meaning of the random and sequential access meters in the profile: For 1/10 of the orders, there is a random lookup from lineitem, hence 14.5M random lookups. The sequential scan is 150M rows of orders plus an average of 3 extra rows for each of the 14M random accesses of lineitem. The locality metric, 98.9% same segment, means that the JOIN has a merge-join pattern, since 99% of lookups fall in the same segment as the previous one. A segment is a column store structure that, in the case of lineitem, corresponds to about 4500 consecutive rows.

This is one of the queries where storing the data in date order would be advantageous. A zone map on date would eliminate half the second half of the orders without even looking at the columns. A zone map is a summary data structure that keeps, for example, a minimum and a maximum value of an attribute for a range of consecutive rows. Also, for all but the lineitems at the end of the range of orders, a zone map would also disqualify the items without looking at the column. VectorWise, for example, profits from this. However, the CPU profile below shows that the time spent in date compares is not very long even now.

On further analysis, we see that the query is run in the order of o_orderkey, so that each o_orderkey is seen once. Hence the partitioned GROUP BY can be changed into an ordered GROUP BY, as all the grouping columns are further functionally dependent on o_orderkey. An ordered GROUP BY is more efficient than a partitioned or re-aggregated one, since it does not have to remember grouping keys: Once a new key comes in, the previous key will not be seen again, and the aggregation for it can be sent onwards in the pipeline.

However, this last transformation has little effect here, as the count of rows passing to the aggregation is small. Use of ordered aggregation has much higher impact in other queries and will be visited there. There is also a chance for late projection, as the o_shippriority is in fact only needed for the top 10 rows returned. The impact is small in this case, though. This too will be visited later.

We now consider the CPU profile:

93087    20.9350  cha_inline_1i_n
63224    14.2189  cha_bloom_unroll
30162     6.7834  cha_insert_1i_n
29178     6.5621  ce_search_rld
28519     6.4139  ce_intd_range_ltgt
17319     3.8950  cs_decode
15848     3.5642  ce_intd_sets_ltgt
11731     2.6383  ce_skip_bits_2
8212      1.8469  ce_vec_int_sets_decode
7946      1.7870  itc_single_row_opt
7886      1.7735  ce_intd_any_sets_decode
7072      1.5905  itc_fetch_col_vec
6474      1.4560  setp_chash_run
5304      1.1929  itc_ce_value_offset
5263      1.1836  itc_col_seg

The top 3 items are for the orders x customer hash join -- the top 2 for the probe, and the 3rd for the build. The 4th item is the index lookup on lineitem. The one below that is the date condition on orders; below this is the condition on the date of lineitem.

The functions working on a compressed column are usually called ce_<compression type>_<sets or range>_<filter or decode>. ce means compression entry; the compression types are rl (run length), rld (run length with delta), bits (densely ascending values as bitmap), intd (16 bit deltas on a base), and dict (dictionary). The sets vs range determines whether the operation works on a set of contiguous values in the entry, or takes a vector of row numbers as context. The first predicate works on a range; the next one on the sets (row numbers) selected by the previous. Filter means selection, and decode means extracting a value for processing by a downstream operator.

We run 5 of these concurrently: the fastest returns in 2.8s; the slowest in 5.4s. The executions are staggered, so that each divides into up to 24 independent fragments which are then multiplexed on 48 worker threads, with each fragment guaranteed at least one thread. The slices of the first query are prioritized, so that when a worker thread has a choice of next unit of work, it will prefer one from an older queue. Each query in this setting has one queue of independently executable fragments. Thus the first to come in gets the most threads and finishes sooner. The rationale for this is that a query may have large transient memory consumption, e.g., GROUP BYs or hash join build sides. The sooner such a query finishes, the less likely it is that there will be many concurrent queries with the high peak-memory demand. This does not block short queries since in any case a runnable query will have one thread which will get scheduled by the OS from time to time.

Q3 Conclusions

The balance is that unused tricks (ordered aggregation, late projection) would gain little. Date order would gain about 0.4s from 1.3s, but would lose in other queries.

We have treated Q1 and Q3 at some length in order to introduce reading of query profiles and the meaning of some meters. For the handful of people who are deep into this sport, the information is rather obvious, but will still give an idea of the specific feature mix of Virtuoso. Column stores are similar to a point, but not all make the exact same choices.

If you are a developer, what, if anything, should you remember of this? Never mind the finesses of column store science -- if you understand join order and join type, then there is the possibility of understanding why some queries are fast and some slow. Most support questions are about this. If you know what the DBMS does or should do you are in control. This is why the metrics and concepts here are also of some interest outside the very small group that actually makes DBMS.

In Hoc Signo Vinces Series