Details
Subscribe
Post Categories
Recent Articles
|
In Hoc Signo Vinces (part 8 of n) -- TPC-H: INs, Expressions, ORs
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
|
|