In this installment, we look at TPC-H Q7, Q12, Q19, Q21, and Q22. These have complex expressions and require some tricks with OR and IN. Also proper order between JOINs and expressions is tested in Q21.

IN Predicates

One of the choke points mentioned in the TPC-H Analyzed paper is the IN predicate with a list of constants. This occurs in Q12 and Q22. Q12 is the simpler of the two:

  SELECT                                            l_shipmode ,
     SUM ( CASE
           WHEN o_orderpriority = '1-URGENT'
             OR o_orderpriority = '2-HIGH'
           THEN 1
           ELSE 0
           END
         )                                       AS high_line_count,
     SUM ( CASE
           WHEN o_orderpriority <> '1-URGENT'
            AND o_orderpriority <> '2-HIGH'
           THEN 1
           ELSE 0
           END 
         )                                       AS low_line_count
   FROM   orders,
          lineitem
   WHERE  o_orderkey = l_orderkey
     AND  l_shipmode IN ('MAIL', 'SHIP')
     AND  l_commitdate < l_receiptdate
     AND  l_shipdate < l_commitdate
     AND  l_receiptdate >= CAST ('1994-01-01' AS DATE)
     AND  l_receiptdate < DATEADD ('year', 1, CAST ('1994-01-01' AS DATE))
GROUP BY  l_shipmode
ORDER BY  l_shipmode

The execution profile:

{ 
time   2.2e-05% fanout         1 input         1 rows
time   0.00023% fanout         1 input         1 rows
 
Precode:
      0: chash_in_init := Call chash_in_init ( 182 , $29 "chash_in_tree",  0 ,  0 , <c MAIL>, <c SHIP>)
      5: BReturn 0
{ fork
time   1.2e-05% fanout         1 input         1 rows
{ fork
time        86% fanout 2.60039e+07 input         1 rows
LINEITEM   2.4e+06 rows(.L_COMMITDATE, .L_RECEIPTDATE, .L_SHIPDATE, .L_ORDERKEY, .L_SHIPMODE)
 L_RECEIPTDATE >= <c 1994-01-01> < <c 1995-01-01>
hash partition+bloom by 0 ()
time       4.4% fanout  0.119803 input 2.60039e+07 rows
END Node
After test:
      0: if (.L_COMMITDATE < .L_RECEIPTDATE) then 4 else 9 unkn 9
      4: if (.L_SHIPDATE < .L_COMMITDATE) then 8 else 9 unkn 9
      8: BReturn 1
      9: BReturn 0
time       7.9% fanout         1 input 3.11534e+06 rows
ORDERS unq         1 rows (.O_ORDERPRIORITY)
 inlined  O_ORDERKEY = k_.L_ORDERKEY
 
After code:
      0: if (.O_ORDERPRIORITY = <c 1-URGENT>) then 13 else 4 unkn 13
      4: if (.O_ORDERPRIORITY = <c 2-HIGH>) then 13 else 8 unkn 13
      8: callretSearchedCASE :=  := artm  1 
      12: Jump 17 (level=0)
      13: callretSearchedCASE :=  := artm  0 
      17: if (.O_ORDERPRIORITY = <c 1-URGENT>) then 25 else 21 unkn 21
      21: if (.O_ORDERPRIORITY = <c 2-HIGH>) then 25 else 30 unkn 30
      25: callretSearchedCASE :=  := artm  1 
      29: Jump 34 (level=0)
      30: callretSearchedCASE :=  := artm  0 
      34: BReturn 0
time       1.3% fanout         0 input 3.11534e+06 rows
Sort (.L_SHIPMODE) -> (callretSearchedCASE, callretSearchedCASE)
 
}

-- rest left out

 1077 msec 2014% cpu, 3.11419e+06 rnd 5.99896e+08 seq   97.9872% same seg   1.74106% same pg 

The top item in the profile is the predicate on l_receiptdate. TPC-H Analyzed correctly points out that a lineitem table in date order is best here, because zone maps will work on l_receiptdate since this is correlated with l_shipdate, which is the best date ordering column, as it is the most used. The date compare is done first in the scan, as it selects 1/7 and is fast, whereas the IN selects 2/7 and has more instructions on the execution path.

Q22

  SELECT                     cntrycode,
                 COUNT(*) AS numcust,
           SUM(c_acctbal) AS totacctbal
    FROM
          ( SELECT  SUBSTRING(c_phone, 1, 2) AS cntrycode,
                                                c_acctbal
              FROM  customer
             WHERE  SUBSTRING(c_phone, 1, 2) 
                      IN ('13', '31', '23', '29', '30', '18', '17')
               AND  c_acctbal > ( SELECT  AVG(c_acctbal)
                                       FROM  customer
                                      WHERE  c_acctbal > 0.00
                                        AND  SUBSTRING(c_phone, 1, 2) 
                                               IN ('13', '31', '23', '29', '30', '18', '17')
                                   )
               AND  NOT EXISTS ( SELECT  *
                                   FROM  orders
                                  WHERE  o_custkey = c_custkey
                               )
          ) AS custsale
GROUP BY  cntrycode
ORDER BY  cntrycode

Q22 has a condition on a substring of a string column. This merits a separate trick, namely merging the substring extraction into the scan, so the invisible hash-join predicate reads the column, cuts the substring in place, calculates a hash number, Bloom filters this against the IN set, then finally outputs the row numbers which match. This operation is run-time re-orderable with other conditions, like the test on c_acctbal. TPC-DS has a similar pattern in some queries.

The profile follows.

Q22 is one of the rare queries that clearly benefit from having an index on a foreign key column. The NOT EXISTS with orders could be done by hash, but then the hash would have to have every DISTINCT o_custkey and the hash build could be filtered by a JOIN on customer with the conditions on c_acctbal and c_phone repeated. Being inside an existence, the number of orders would not have to be retained, so the hash table would not end up larger than the probe side.

The payoff in Q22 makes it worthwhile to maintain an index on o_custkey in the refresh functions.

{ 
time   1.4e-05% fanout         1 input         1 rows
time       1.2% fanout         1 input         1 rows
 
Precode:
      0: $27 "chash_in_init" := Call chash_in_init ( 182 , $29 "chash_in_tree",  0 ,  0 , <c 13>, <c 31>, <c 23>, <c 29>, <c 30>, <c 18>, <c 17>)
      5: { 
time   7.9e-06% fanout         1 input         1 rows
time   6.7e-05% fanout         1 input         1 rows
{ fork

-- Read customer once, filter with the IN predicate, and add up c_acctbal and count for the average.

time        26% fanout         0 input         1 rows
CUSTOMER   1.4e+07 rows(t4.C_ACCTBAL)
 C_ACCTBAL >  0 
hash partition+bloom by 0 ()
 
After code:
      0:  sum count 1 
      5:  sum sumt4.C_ACCTBAL
      10: BReturn 0
}
 
After code:
      0: temp := artm sum / count
      4: aggregate :=  := artm temp
      8: BReturn 0
time   2.6e-05% fanout         0 input         1 rows
Subquery Select(aggregate)
}
 
      13: BReturn 0
{ fork
time   1.9e-05% fanout         1 input         1 rows
{ fork

-- second scan of customer with the test on c_acctbal > average and the same in predicate.

time        26% fanout 1.90967e+06 input         1 rows
CUSTOMER   2.7e+05 rows(t2.C_CUSTKEY, t2.C_PHONE, t2.C_ACCTBAL)
 C_ACCTBAL > k_scalar
hash partition+bloom by 0 ()
time         7% fanout  0.333434 input 1.90967e+06 rows
END Node
After test:
      0: if ({ 
time      0.26% fanout         1 input 1.90967e+06 rows

-- See if the customer has orders. The index lookup is very fast since the keys come in order from the scan of customer.

time         5% fanout    9.9955 input 1.90967e+06 rows
O_CK       9.9 rows()
 inlined  O_CUSTKEY = k_t2.C_CUSTKEY
time       1.6% fanout         0 input 1.90881e+07 rows
Subquery Select( <none> )
}
) then 5 else 4 unkn 5
      4: BReturn 1
      5: BReturn 0
time       3.1% fanout         1 input    636749 rows
 
Precode:
      0: cntrycode := Call substring (t2.C_PHONE,  1 ,  2 )
      5: BReturn 0
Stage 2
time       0.5% fanout         0 input    636749 rows
Sort (q_cntrycode) -> (t2.C_ACCTBAL, inc)
 
}
time     0.011% fanout         7 input         1 rows
group by read node  
(cntrycode, totacctbal, numcust)in each partition slice
time    0.0013% fanout         0 input         7 rows
Sort (cntrycode) -> (numcust, totacctbal)
 
}
time   0.00016% fanout         7 input         1 rows
Key from temp (cntrycode, numcust, totacctbal)
 
time   1.4e-05% fanout         0 input         7 rows
Select (cntrycode, numcust, totacctbal)
}

 306 msec 2107% cpu, 1.90678e+06 rnd 4.77961e+07 seq   99.5612% same seg  0.419137% same pg 

Q21 - Join Order and complex tests

This identifies suppliers from a given country that have kept orders waiting, i.e., they supply a delayed lineitem and nobody else in the order supplies a delayed lineitem.

  SELECT TOP 100             s_name,
                 COUNT(*) AS numwait
    FROM            supplier,
          lineitem  l1,
                    orders,
                    nation
   WHERE  s_suppkey = l1.l_suppkey
     AND o_orderkey = l1.l_orderkey
     AND o_orderstatus = 'F'
     AND l1.l_receiptdate > l1.l_commitdate
     AND EXISTS ( SELECT  *
                    FROM  lineitem l2 
                   WHERE  l2.l_orderkey = l1.l_orderkey
                     AND  l2.l_suppkey <> l1.l_suppkey
                )
     AND NOT EXISTS ( SELECT  *
                        FROM  lineitem l3 
                       WHERE  l3.l_orderkey = l1.l_orderkey
                         AND  l3.l_suppkey <> l1.l_suppkey
                         AND  l3.l_receiptdate > l3.l_commitdate
                    )
     AND s_nationkey = n_nationkey
     AND n_name = 'SAUDI ARABIA'
GROUP BY  s_name
ORDER BY  numwait desc,
          s_name
;

The crucial thing the optimizer must realize is that conditions that depend on a table should not always be placed right after the table because there could be a selective join that costs less. In this case, the plan comes out as a scan of orders selecting 1/2; then an index lookup on lineitem which is very efficient because the keys come in order and are tightly local; then the selective hash join with suppliers from the country is merged into the index lookup. After this, 1/50 of lineitems are left. Only for these does the system actually fetch the dates. After this comes the series of tests, ordered similarly to how joins are ordered. First the cheap date comparison, then the subqueries. The lineitems can be fetched by their primary key, which again comes in order. Doing this by hash would duplicate most of the query on the build side and would be a lot of trouble.

Another join order would be lineitem first, selecting 1/25 with the merged hash-join with supplier, then orders by index, selecting 1/2, then the existences. Experiment shows there is no great difference.

{ 
time   4.5e-06% fanout         1 input         1 rows
time    0.0036% fanout         1 input         1 rows
{ hash filler
Subquery 27 
{ 
time   3.8e-05% fanout         1 input         1 rows
NATION         1 rows(t4.N_NATIONKEY)
 N_NAME = <c SAUDI ARABIA>
time      0.01% fanout     39953 input         1 rows
SUPPLIER   4.2e+04 rows(t1.S_SUPPKEY, t1.S_NAME)
 S_NATIONKEY = t4.N_NATIONKEY
 
After code:
      0: t1.S_SUPPKEY :=  := artm t1.S_SUPPKEY
      4: t1.S_NAME :=  := artm t1.S_NAME
      8: BReturn 0
time    0.0019% fanout         0 input     39953 rows
Sort hf 48 (t1.S_SUPPKEY) -> (t1.S_NAME)
 
}
}
time   2.8e-06% fanout         1 input         1 rows
{ fork
time   2.6e-06% fanout         1 input         1 rows
{ fork
time       6.2% fanout 7.30725e+07 input         1 rows
ORDERS   7.3e+07 rows(.O_ORDERKEY)
 O_ORDERSTATUS = <c F>
time        33% fanout  0.142002 input 7.30725e+07 rows
LINEITEM      0.49 rows(l1.L_RECEIPTDATE, l1.L_COMMITDATE, l1.L_ORDERKEY, l1.L_SUPPKEY)
 inlined  L_ORDERKEY = .O_ORDERKEY
hash partition+bloom by 58 (tmp)hash join merged always card      0.04 -> (.S_NAME)
time       9.7% fanout 0.0341517 input 1.03764e+07 rows
END Node
After test:
      0: if (l1.L_RECEIPTDATE > l1.L_COMMITDATE) then 4 else 13 unkn 13
      4: if ({ 
time      0.18% fanout  0.630264 input 1.03764e+07 rows
time       6.4% fanout   4.99133 input 6.53989e+06 rows
LINEITEM       1.1 rows(l3.L_SUPPKEY, l3.L_RECEIPTDATE, l3.L_COMMITDATE)
 inlined  L_ORDERKEY = k_l1.L_ORDERKEY
time       1.4% fanout  0.504963 input 3.26427e+07 rows
END Node
After test:
      0: if (l3.L_RECEIPTDATE > l3.L_COMMITDATE) then 4 else 9 unkn 9
      4: if (l3.L_SUPPKEY = l1.L_SUPPKEY) then 9 else 8 unkn 9
      8: BReturn 1
      9: BReturn 0
time      0.17% fanout         0 input 1.64834e+07 rows
Subquery Select( <none> )
}
) then 13 else 8 unkn 13
      8: if ({ 
time     0.052% fanout 0.0570441 input 1.03764e+07 rows
time       1.1% fanout   2.13264 input    591914 rows
LINEITEM       3.7 rows(l2.L_SUPPKEY)
 inlined  L_ORDERKEY = k_l1.L_ORDERKEY
time     0.047% fanout  0.531095 input 1.26234e+06 rows
END Node
After test:
      0: if (l2.L_SUPPKEY = l1.L_SUPPKEY) then 5 else 4 unkn 5
      4: BReturn 1
      5: BReturn 0
time     0.013% fanout         0 input    670421 rows
Subquery Select( <none> )
}
) then 12 else 13 unkn 13
      12: BReturn 1
      13: BReturn 0
time    0.0086% fanout         1 input    354373 rows
Hash source 48 merged into ts       0.04 rows(k_l1.L_SUPPKEY) -> (.S_NAME)
time       1.5% fanout         1 input    354373 rows
Stage 2
time      0.18% fanout         0 input    354373 rows
Sort (q_.S_NAME) -> (inc)
 
}

-- rest left out

 2301 msec 2092% cpu, 8.01116e+07 rnd 3.95017e+08 seq   99.4284% same seg  0.475267% same pg 
Compilation: 2 msec 0 reads         0% read 0 messages         0% clw

Q19 Complex Expressions

SELECT  SUM(l_extendedprice* (1 - l_discount)) AS revenue
  FROM  lineitem,
        part
 WHERE  (          p_partkey = l_partkey
          AND        p_brand = 'Brand#12'
          AND    p_container IN ('SM CASE', 'SM BOX', 'SM PACK', 'SM PKG')
          AND     l_quantity >= 1 
          AND     l_quantity <= 1 + 10
          AND         p_size BETWEEN 1 AND 5
          AND     l_shipmode IN ('AIR', 'AIR REG')
          AND l_shipinstruct = 'DELIVER IN PERSON'
        )
    OR
        (
                   p_partkey = l_partkey
          AND        p_brand = 'Brand#23'
          AND    p_container IN ('MED BAG', 'MED BOX', 'MED PKG', 'MED PACK')
          AND     l_quantity >= 10 
          AND     l_quantity <= 10 + 10
          AND         p_size BETWEEN 1 AND 10
          AND     l_shipmode IN ('AIR', 'AIR REG')
          AND l_shipinstruct = 'DELIVER IN PERSON'
        )
    OR
        (
                   p_partkey = l_partkey
          AND        p_brand = 'Brand#34'
          AND    p_container IN ('LG CASE', 'LG BOX', 'LG PACK', 'LG PKG')
          AND     l_quantity >= 20 
          AND     l_quantity <= 20 + 10
          AND         p_size BETWEEN 1 AND 15
          AND     l_shipmode in ('AIR', 'AIR REG')
          AND l_shipinstruct = 'DELIVER IN PERSON'
        )

The essential trick is to recognize that each of the terms of the OR have the join condition between lineitem and part and the l_shipmode and l_shipinstruct conditions in common. After extracting these, the OR is split into two more ORs, one with conditions on part and the other with conditions on lineitem only. A hash is made of the matching parts where parts that correspond to none of the 3 ORed ANDs are left out. Then there is a scan of lineitem with the hash lookup merged. The merged hash lookup does in this case produce result columns, which are further tested later in the query.

{ time 1.7e-05% fanout 1 input 1 rows time 0.018% fanout 1 input 1 rows
 
Precode:
      0: chash_in_init := Call chash_in_init ( 182 , $29 "chash_in_tree",  0 ,  0 , <c AIR>, <c AIR REG>)
      5: temp := artm  1  +  10 
      9: temp := artm  10  +  10 
      13: temp := artm  20  +  10 
      17: BReturn 0
{ hash filler
time       4.5% fanout     2e+07 input         1 rows
PART   7.2e+04 rows(.P_BRAND, .P_CONTAINER, .P_SIZE, .P_PARTKEY)
 P_SIZE >=  1 
time        16% fanout 0.00240925 input     2e+07 rows
END Node
After test:
      0: if (.P_BRAND = <c Brand#12>) then 4 else 17 unkn 17
      4: if (.P_SIZE <=  5 ) then 8 else 17 unkn 17
      8: one_of_these := Call one_of_these (.P_CONTAINER, <c SM CASE>, <c SM BOX>, <c SM PACK>, <c SM PKG>)
      13: if ( 0  < one_of_these) then 51 else 17 unkn 17
      17: if (.P_BRAND = <c Brand#23>) then 21 else 34 unkn 34
      21: if (.P_SIZE <=  10 ) then 25 else 34 unkn 34
      25: one_of_these := Call one_of_these (.P_CONTAINER, <c MED BAG>, <c MED BOX>, <c MED PKG>, <c MED PACK>)
      30: if ( 0  < one_of_these) then 51 else 34 unkn 34
      34: if (.P_BRAND = <c Brand#34>) then 38 else 52 unkn 52
      38: if (.P_SIZE <=  15 ) then 42 else 52 unkn 52
      42: one_of_these := Call one_of_these (.P_CONTAINER, <c LG CASE>, <c LG BOX>, <c LG PACK>, <c LG PKG>)
      47: if ( 0  < one_of_these) then 51 else 52 unkn 52
      51: BReturn 1
      52: BReturn 0
time     0.058% fanout         0 input     48185 rows
Sort hf 52 (.P_PARTKEY) -> (.P_SIZE, .P_CONTAINER, .P_BRAND)
 
}
time   2.4e-05% fanout         1 input         1 rows
{ fork
time        79% fanout     46004 input         1 rows
LINEITEM   1.1e+07 rows(.L_QUANTITY, .L_PARTKEY, .L_EXTENDEDPRICE, .L_DISCOUNT, .L_SHIPMODE)
 L_SHIPINSTRUCT = <c DELIVER IN PERSON>
hash partition+bloom by 0 ()
hash partition+bloom by 59 (tmp)hash join merged always card   0.00032 -> (.P_SIZE, .P_CONTAINER, .P_BRAND)
time     0.011% fanout  0.599796 input     46004 rows
END Node
After test:
      0: if (.L_QUANTITY <= temp) then 4 else 8 unkn 8
      4: if (.L_QUANTITY >=  1 ) then 24 else 8 unkn 8
      8: if (.L_QUANTITY <= temp) then 12 else 16 unkn 16
      12: if ( 10  <= .L_QUANTITY) then 24 else 16 unkn 16
      16: if (temp >= .L_QUANTITY) then 20 else 25 unkn 25
      20: if (.L_QUANTITY >=  20 ) then 24 else 25 unkn 25
      24: BReturn 1
      25: BReturn 0
time     0.002% fanout         1 input     27593 rows
 
Precode:
      0: temp := artm  1  - .L_DISCOUNT
      4: temp := artm .L_EXTENDEDPRICE * temp
      8: BReturn 0
Hash source 52 merged into ts    0.00032 rows(k_.L_PARTKEY) -> (.P_SIZE, .P_CONTAINER, .P_BRAND)
time     0.053% fanout         0 input     27593 rows
END Node
After test:
      0: if (.P_BRAND = <c Brand#12>) then 4 else 25 unkn 25
      4: if (.L_QUANTITY >=  1 ) then 8 else 25 unkn 25
      8: if (.L_QUANTITY <= temp) then 12 else 25 unkn 25
      12: if (.P_SIZE <=  5 ) then 16 else 25 unkn 25
      16: one_of_these := Call one_of_these (.P_CONTAINER, <c SM CASE>, <c SM BOX>, <c SM PACK>, <c SM PKG>)
      21: if ( 0  < one_of_these) then 75 else 25 unkn 25
      25: if (.P_BRAND = <c Brand#23>) then 29 else 50 unkn 50
      29: if ( 10  <= .L_QUANTITY) then 33 else 50 unkn 50
      33: if (.L_QUANTITY <= temp) then 37 else 50 unkn 50
      37: if (.P_SIZE <=  10 ) then 41 else 50 unkn 50
      41: one_of_these := Call one_of_these (.P_CONTAINER, <c MED BAG>, <c MED BOX>, <c MED PKG>, <c MED PACK>)
      46: if ( 0  < one_of_these) then 75 else 50 unkn 50
      50: if (.P_BRAND = <c Brand#34>) then 54 else 76 unkn 76
      54: if (.L_QUANTITY >=  20 ) then 58 else 76 unkn 76
      58: if (temp >= .L_QUANTITY) then 62 else 76 unkn 76
      62: if (.P_SIZE <=  15 ) then 66 else 76 unkn 76
      66: one_of_these := Call one_of_these (.P_CONTAINER, <c LG CASE>, <c LG BOX>, <c LG PACK>, <c LG PKG>)
      71: if ( 0  < one_of_these) then 75 else 76 unkn 76
      75: BReturn 1
      76: BReturn 0
 
After code:
      0:  sum revenuetemp
      5: BReturn 0
}
time   8.7e-06% fanout         0 input         1 rows
Select (revenue)
}


 1315 msec 1889% cpu,         2 rnd 1.62319e+08 seq         0% same seg         0% same pg 

Q7 More ORs

We find a similar pattern in Q7, where an implementation is expected to extract conditions from an OR and to restrict hash build sides with these. For

SELECT                 supp_nation,
                       cust_nation,
                       l_year,
        SUM(volume) AS revenue
  FROM
   (  SELECT
                                       n1.n_name AS supp_nation,
                                       n2.n_name AS cust_nation,
                   extract(year FROM l_shipdate) AS l_year,
              l_extendedprice * (1 - l_discount) AS volume
        FROM         supplier,
                     lineitem, 
                     orders,
                     customer,
              nation n1,
              nation n2
       WHERE  s_suppkey = l_suppkey
         AND  o_orderkey = l_orderkey
         AND  c_custkey = o_custkey
         AND  s_nationkey = n1.n_nationkey
         AND  c_nationkey = n2.n_nationkey
         AND  (    (     n1.n_name = 'FRANCE' 
                     AND n2.n_name = 'GERMANY'
                   )
                OR (     n1.n_name = 'GERMANY' 
                     AND n2.n_name = 'FRANCE'
                   )
              )
         AND  l_shipdate BETWEEN CAST ('1995-01-01' AS DATE) AND CAST ('1996-12-31' AS DATE)
   ) AS shipping
GROUP BY  supp_nation,
          cust_nation,
          l_year
ORDER BY  supp_nation,
          cust_nation,
          l_year

The plan builds a hash with customers from either France or Germany, then of suppliers from either France or Germany. Then it scans lineitem for 2/7 years and selects 2/25 based on the supplier. The name of the supplier country is also returned from the merged hash lookup. Then the corresponding order is fetched by primary key, which is fast since the lineitem produces keys in order. A similar hash condition is on the customer. Finally, there is code to check that the countries are different between supplier and customer. We leave out the plan in the interest of space. A single execution is between 1.7 and 1.9s; 5 concurrent executions are 7.5s for the slowest.

To be continued...

In Hoc Signo Vinces Series