Re: TPC-R benchmarks - Mailing list pgsql-performance

Tom,

I've found the problem with TPC-R query #19.  And it, unfortunately, appears
to be a problem in the PostgreSQL query planner.

To sum up the below:  it appears that whenever a set of WHERE conditions
exceeds a certain level of complexity, the planner just ignores all
applicable indexes and goes for a seq scan.   While this may be unavoidable
to some degree, it seems to me that we need to raise the threshold of
complexity at which it does this.

tpcr=# select version();
                                                 version
---------------------------------------------------------------------------------------------------------
 PostgreSQL 7.3.4 on i686-pc-linux-gnu, compiled by GCC gcc (GCC) 3.3 20030226
(prerelease) (SuSE Linux)
(1 row)

I've tested a number of indexes on the query, and found the two most efficient
on subsets of the query.  Thus:

explain analyze
select
    sum(l_extendedprice* (1 - l_discount)) as revenue
from
    lineitem,
    part
where
    (
        p_partkey = l_partkey
        and p_brand = 'Brand#33'
        and p_container in ('SM CASE', 'SM BOX', 'SM PACK', 'SM PKG')
        and l_quantity >= 8 and l_quantity <= 8 + 10
        and p_size between 1 and 5
        and l_shipmode in ('AIR', 'AIR REG')
        and l_shipinstruct = 'DELIVER IN PERSON'
    );

QUERY PLAN

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=10380.70..10380.70 rows=1 width=30) (actual
time=161.61..161.61 rows=1 loops=1)
   ->  Nested Loop  (cost=0.00..10380.67 rows=13 width=30) (actual
time=81.54..161.47 rows=17 loops=1)
         ->  Index Scan using idx_part_1 on part  (cost=0.00..9466.33 rows=62
width=4) (actual time=81.21..137.24 rows=98 loops=1)
               Index Cond: (p_brand = 'Brand#33'::bpchar)
               Filter: (((p_container = 'SM CASE'::bpchar) OR (p_container =
'SM BOX'::bpchar) OR (p_container = 'SM PACK'::bpchar) OR (p_container = 'SM
PKG'::bpchar)) AND (p_size >= 1) AND (p_size <= 5))
         ->  Index Scan using idx_lineitem_3 on lineitem  (cost=0.00..14.84
rows=1 width=26) (actual time=0.22..0.24 rows=0 loops=98)
               Index Cond: (("outer".p_partkey = lineitem.l_partkey) AND
(lineitem.l_quantity >= 8::numeric) AND (lineitem.l_quantity <= 18::numeric))
               Filter: (((l_shipmode = 'AIR'::bpchar) OR (l_shipmode = 'AIR
REG'::bpchar)) AND (l_shipinstruct = 'DELIVER IN PERSON'::bpchar))
 Total runtime: 161.71 msec



This also works for a similar query:

explain analyze
select
    sum(l_extendedprice* (1 - l_discount)) as revenue
from
    lineitem,
    part
where
    (
        p_partkey = l_partkey
        and p_brand = 'Brand#52'
        and p_container in ('MED BAG', 'MED BOX', 'MED PKG', 'MED PACK')
        and l_quantity >= 14 and l_quantity <= 14 + 10
        and p_size between 1 and 10
        and l_shipmode in ('AIR', 'AIR REG')
        and l_shipinstruct = 'DELIVER IN PERSON'
    );

 Aggregate  (cost=11449.36..11449.36 rows=1 width=30) (actual
time=195.72..195.72 rows=1 loops=1)
   ->  Nested Loop  (cost=0.00..11449.29 rows=28 width=30) (actual
time=56.42..195.39 rows=48 loops=1)
         ->  Index Scan using idx_part_1 on part  (cost=0.00..9466.33 rows=139
width=4) (actual time=56.15..153.17 rows=166 loops=1)
               Index Cond: (p_brand = 'Brand#52'::bpchar)
               Filter: (((p_container = 'MED BAG'::bpchar) OR (p_container =
'MED BOX'::bpchar) OR (p_container = 'MED PKG'::bpchar) OR (p_container =
'MED PACK'::bpchar)) AND (p_size >= 1) AND (p_size <= 10))
         ->  Index Scan using idx_lineitem_3 on lineitem  (cost=0.00..14.29
rows=1 width=26) (actual time=0.23..0.25 rows=0 loops=166)
               Index Cond: (("outer".p_partkey = lineitem.l_partkey) AND
(lineitem.l_quantity >= 14::numeric) AND (lineitem.l_quantity <=
24::numeric))
               Filter: (((l_shipmode = 'AIR'::bpchar) OR (l_shipmode = 'AIR
REG'::bpchar)) AND (l_shipinstruct = 'DELIVER IN PERSON'::bpchar))
 Total runtime: 195.82 msec
(9 rows)


If, however, I combine the two where clauses with an OR, the planner gets
confused and insists on loading the entire tables into memory (even though I
don't have that much memory):

explain
select
    sum(l_extendedprice* (1 - l_discount)) as revenue
from
    lineitem,
    part
where
    (
        p_partkey = l_partkey
        and p_brand = 'Brand#33'
        and p_container in ('SM CASE', 'SM BOX', 'SM PACK', 'SM PKG')
        and l_quantity >= 8 and l_quantity <= 8 + 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#52'
        and p_container in ('MED BAG', 'MED BOX', 'MED PKG', 'MED PACK')
        and l_quantity >= 14 and l_quantity <= 14 + 10
        and p_size between 1 and 10
        and l_shipmode in ('AIR', 'AIR REG')
        and l_shipinstruct = 'DELIVER IN PERSON'
    );

 Aggregate  (cost=488301096525.25..488301096525.25 rows=1 width=146)
   ->  Nested Loop  (cost=0.00..488301096525.15 rows=42 width=146)
         Join Filter: ((("outer".l_shipmode = 'AIR'::bpchar) AND
("inner".p_container = 'SM CASE'::bpchar) AND ("inner".p_partkey =
"outer".l_partkey) AND ("inner".p_brand = 'Brand#33'::bpchar) AND
("outer".l_quantity >= 8::numeric) AND ("outer".l_quantity <= 18::numeric)
AND ("inner".p_size >= 1) AND ("inner".p_size <= 5) AND
("outer".l_shipinstruct = 'DELIVER IN PERSON'::bpchar)) OR
(("outer".l_shipmode = 'AIR REG'::bpchar) AND ("inner".p_container = 'SM
CASE'::bpchar) AND ("inner".p_partkey = "outer".l_partkey) AND
("inner".p_brand = 'Brand#33'::bpchar) AND ("outer".l_quantity >= 8::numeric)
AND ("outer".l_quantity <= 18::numeric) AND ("inner".p_size >= 1) AND
("inner".p_size <= 5) AND ("outer".l_shipinstruct = 'DELIVER IN
PERSON'::bpchar)) OR (("outer".l_shipmode = 'AIR'::bpchar) AND
("inner".p_container = 'SM BOX'::bpchar) AND ("inner".p_partkey =
"outer".l_partkey) AND ("inner".p_brand = 'Brand#33'::bpchar) AND
("outer".l_quantity >= 8::numeric) AND ("outer".l_quantity <= 18::numeric)
AND ("inner".p_size >= 1) AND ("inner".p_size <= 5) AND
("outer".l_shipinstruct = 'DELIVER IN PERSON'::bpchar)) OR
(("outer".l_shipmode = 'AIR REG'::bpchar) AND ("inner".p_container = 'SM
BOX'::bpchar) AND ("inner".p_partkey = "outer".l_partkey) AND
("inner".p_brand = 'Brand#33'::bpchar) AND ("outer".l_quantity >= 8::numeric)
AND ("outer".l_quantity <= 18::numeric) AND ("inner".p_size >= 1) AND
("inner".p_size <= 5) AND ("outer".l_shipinstruct = 'DELIVER IN
PERSON'::bpchar)) OR (("outer".l_shipmode = 'AIR'::bpchar) AND
("inner".p_container = 'SM PACK'::bpchar) AND ("inner".p_partkey =
"outer".l_partkey) AND ("inner".p_brand = 'Brand#33'::bpchar) AND
("outer".l_quantity >= 8::numeric) AND ("outer".l_quantity <= 18::numeric)
AND ("inner".p_size >= 1) AND ("inner".p_size <= 5) AND
("outer".l_shipinstruct = 'DELIVER IN PERSON'::bpchar)) OR
(("outer".l_shipmode = 'AIR REG'::bpchar) AND ("inner".p_container = 'SM
PACK'::bpchar) AND ("inner".p_partkey = "outer".l_partkey) AND
("inner".p_brand = 'Brand#33'::bpchar) AND ("outer".l_quantity >= 8::numeric)
AND ("outer".l_quantity <= 18::numeric) AND ("inner".p_size >= 1) AND
("inner".p_size <= 5) AND ("outer".l_shipinstruct = 'DELIVER IN
PERSON'::bpchar)) OR (("outer".l_shipmode = 'AIR'::bpchar) AND
("inner".p_container = 'SM PKG'::bpchar) AND ("inner".p_partkey =
"outer".l_partkey) AND ("inner".p_brand = 'Brand#33'::bpchar) AND
("outer".l_quantity >= 8::numeric) AND ("outer".l_quantity <= 18::numeric)
AND ("inner".p_size >= 1) AND ("inner".p_size <= 5) AND
("outer".l_shipinstruct = 'DELIVER IN PERSON'::bpchar)) OR
(("outer".l_shipmode = 'AIR REG'::bpchar) AND ("inner".p_container = 'SM
PKG'::bpchar) AND ("inner".p_partkey = "outer".l_partkey) AND
("inner".p_brand = 'Brand#33'::bpchar) AND ("outer".l_quantity >= 8::numeric)
AND ("outer".l_quantity <= 18::numeric) AND ("inner".p_size >= 1) AND
("inner".p_size <= 5) AND ("outer".l_shipinstruct = 'DELIVER IN
PERSON'::bpchar)) OR (("outer".l_shipmode = 'AIR'::bpchar) AND
("inner".p_container = 'MED BAG'::bpchar) AND ("inner".p_partkey =
"outer".l_partkey) AND ("inner".p_brand = 'Brand#52'::bpchar) AND
("outer".l_quantity >= 14::numeric) AND ("outer".l_quantity <= 24::numeric)
AND ("inner".p_size >= 1) AND ("inner".p_size <= 10) AND
("outer".l_shipinstruct = 'DELIVER IN PERSON'::bpchar)) OR
(("outer".l_shipmode = 'AIR REG'::bpchar) AND ("inner".p_container = 'MED
BAG'::bpchar) AND ("inner".p_partkey = "outer".l_partkey) AND
("inner".p_brand = 'Brand#52'::bpchar) AND ("outer".l_quantity >=
14::numeric) AND ("outer".l_quantity <= 24::numeric) AND ("inner".p_size >=
1) AND ("inner".p_size <= 10) AND ("outer".l_shipinstruct = 'DELIVER IN
PERSON'::bpchar)) OR (("outer".l_shipmode = 'AIR'::bpchar) AND
("inner".p_container = 'MED BOX'::bpchar) AND ("inner".p_partkey =
"outer".l_partkey) AND ("inner".p_brand = 'Brand#52'::bpchar) AND
("outer".l_quantity >= 14::numeric) AND ("outer".l_quantity <= 24::numeric)
AND ("inner".p_size >= 1) AND ("inner".p_size <= 10) AND
("outer".l_shipinstruct = 'DELIVER IN PERSON'::bpchar)) OR
(("outer".l_shipmode = 'AIR REG'::bpchar) AND ("inner".p_container = 'MED
BOX'::bpchar) AND ("inner".p_partkey = "outer".l_partkey) AND
("inner".p_brand = 'Brand#52'::bpchar) AND ("outer".l_quantity >=
14::numeric) AND ("outer".l_quantity <= 24::numeric) AND ("inner".p_size >=
1) AND ("inner".p_size <= 10) AND ("outer".l_shipinstruct = 'DELIVER IN
PERSON'::bpchar)) OR (("outer".l_shipmode = 'AIR'::bpchar) AND
("inner".p_container = 'MED PKG'::bpchar) AND ("inner".p_partkey =
"outer".l_partkey) AND ("inner".p_brand = 'Brand#52'::bpchar) AND
("outer".l_quantity >= 14::numeric) AND ("outer".l_quantity <= 24::numeric)
AND ("inner".p_size >= 1) AND ("inner".p_size <= 10) AND
("outer".l_shipinstruct = 'DELIVER IN PERSON'::bpchar)) OR
(("outer".l_shipmode = 'AIR REG'::bpchar) AND ("inner".p_container = 'MED
PKG'::bpchar) AND ("inner".p_partkey = "outer".l_partkey) AND
("inner".p_brand = 'Brand#52'::bpchar) AND ("outer".l_quantity >=
14::numeric) AND ("outer".l_quantity <= 24::numeric) AND ("inner".p_size >=
1) AND ("inner".p_size <= 10) AND ("outer".l_shipinstruct = 'DELIVER IN
PERSON'::bpchar)) OR (("outer".l_shipmode = 'AIR'::bpchar) AND
("inner".p_container = 'MED PACK'::bpchar) AND ("inner".p_partkey =
"outer".l_partkey) AND ("inner".p_brand = 'Brand#52'::bpchar) AND
("outer".l_quantity >= 14::numeric) AND ("outer".l_quantity <= 24::numeric)
AND ("inner".p_size >= 1) AND ("inner".p_size <= 10) AND
("outer".l_shipinstruct = 'DELIVER IN PERSON'::bpchar)) OR
(("outer".l_shipmode = 'AIR REG'::bpchar) AND ("inner".p_container = 'MED
PACK'::bpchar) AND ("inner".p_partkey = "outer".l_partkey) AND
("inner".p_brand = 'Brand#52'::bpchar) AND ("outer".l_quantity >=
14::numeric) AND ("outer".l_quantity <= 24::numeric) AND ("inner".p_size >=
1) AND ("inner".p_size <= 10) AND ("outer".l_shipinstruct = 'DELIVER IN
PERSON'::bpchar)))
         ->  Seq Scan on lineitem  (cost=0.00..235620.15 rows=6001215
width=95)
         ->  Seq Scan on part  (cost=0.00..7367.00 rows=200000 width=51)


You'll pardon me for not doing an "ANALYZE", but I didn't want to wait
overnight.   Manually disabling Seqscan and Nestloop did nothing to affect
this query plan; neither did removing the aggregate.

Tommorrow I will test 7.4 Beta 4.

How can we fix this?

--
-Josh Berkus
 Aglio Database Solutions
 San Francisco