Re: huge execution time difference with almost same plan

Sorry for the delay. I was out of town last night.

> What can you tell us about the physical ordering of the tables involved?
> The only way I can think of to explain these results is that "orders"
> is more or less physically in order by its primary key, and "lineitem"
> is also more or less ordered by the orders primary key (which might or
> might not be the same as l_orderkey; I forget the schema of that
> database).

Yes, it seems orders table is in phsysically in order by
o_orderkey(primary key) and lineitem is in same order as o_orderkey.

BTW ere is the schema for orders and lineitem:

Table "public.orders"
Column | Type | Modifiers
-----------------+-----------------------+-----------
o_orderkey | numeric(10,0) | not null
o_custkey | numeric(10,0) |
o_orderstatus | character(1) |
o_totalprice | numeric(12,2) |
o_orderdate | date |
o_orderpriority | character(15) |
o_clerk | character(15) |
o_shippriority | numeric(10,0) |
o_comment | character varying(79) |
Indexes:
"orders_pkey" primary key, btree (o_orderkey)
"i_o_custkey" btree (o_custkey)
"i_o_orderdate" btree (o_orderdate)

Table "public.lineitem"
Column | Type | Modifiers
-----------------+-----------------------+-----------
l_orderkey | numeric(10,0) | not null
l_partkey | numeric(10,0) |
l_suppkey | numeric(10,0) |
l_linenumber | numeric(10,0) | not null
l_quantity | numeric(12,2) |
l_extendedprice | numeric(12,2) |
l_discount | numeric(12,2) |
l_tax | numeric(12,2) |
l_returnflag | character(1) |
l_linestatus | character(1) |
l_shipdate | date |
l_commitdate | date |
l_receiptdate | date |
l_shipinstruct | character(25) |
l_shipmode | character(10) |
l_comment | character varying(44) |
Indexes:
"lineitem_pkey" primary key, btree (l_orderkey, l_linenumber)
"i_l_orderkey" btree (l_orderkey)
"i_l_orderkey_quantity" btree (l_orderkey, l_quantity)
"i_l_partkey" btree (l_partkey)
"i_l_receiptdate" btree (l_receiptdate)
"i_l_shipdate" btree (l_shipdate)
"i_l_suppkey" btree (l_suppkey)
"i_l_suppkey_partkey" btree (l_partkey, l_suppkey)

> You have
>
> > -> Index Scan using orders_pkey on orders (cost=0.00..65387.00 rows=53357 width=30) (actual time=44.687..36364.312 rows=57306 loops=1)
> > Filter: ((o_orderdate >= '1997-10-01'::date) AND (o_orderdate < '1998-01-01'::date))
>
> versus
>
> > -> Index Scan using i_o_orderdate on orders (cost=0.00..46100.56 rows=53357 width=30) (actual time=215.502..650031.049 rows=57306 loops=1)
> > Index Cond: ((o_orderdate >= '1997-10-01'::date) AND (o_orderdate < '1998-01-01'::date))
>
> Now in the first case that's going to be a full-table scan because
> there are no index constraints. The second one actually is being
> selective and so should visit less than all the table rows. The
> only way the first one can be twenty times faster is if it's doing
> nearly sequential access to the table while the other one is jumping
> all over the place.
>
> (BTW, what happens if you take your thumb off the scales and allow
> the planner to use a seqscan like it wanted to? Seems like that
> should be faster than a full-table index scan.)

Yes, it was 278438.037 ms, about 7-8% faster than the 1st case.

> The costs for the other table are striking too:
>
> > -> Index Scan using i_l_orderkey on lineitem (cost=0.00..3.14 rows=3 width=11) (actual time=4.628..4.628 rows=1 loops=57306)
> > Index Cond: ("outer".o_orderkey = lineitem.l_orderkey)
> > Filter: (l_commitdate < l_receiptdate)
>
> versus
>
> > -> Index Scan using i_l_orderkey on lineitem (cost=0.00..3.14 rows=3 width=11) (actual time=22.064..22.064 rows=1 loops=57306)
> > Index Cond: ("outer".o_orderkey = lineitem.l_orderkey)
> > Filter: (l_commitdate < l_receiptdate)
>
> These are the identical plan but the second case is five times slower
> (which adds up to a lot, over 57000+ iterations). Again, I think the
> only possible explanation is that the first plan is benefiting from
> locality of access while the second is not. That would have to be due
> to the order of the probes in the first case being well-matched to the
> physical table order whereas in the second case not.
>
> Can you look at the data and see whether the pkey is correlated to
> physical order while the orderdate is not? (That seems a bit weird
> but it's the only explanation I can see.)

Your guess was correct. The pkey is physically in the same order as
orders, but o_orderdate seems in very random order.

> BTW, the planner is aware of physical order considerations; it would
> not be smart enough to realize the correlation between physical order of
> two different tables, but it would have accounted for this in its
> preference of pkey over orderdate for scanning the orders table.
> That's why you had to knock random_page_cost down so far in order
> to mislead it into choosing the slower scan...

I think statistics for orders shows too that your guess is correct.

DBT3=# select attname,correlation from pg_stats where tablename = 'orders';
attname | correlation
-----------------+-------------
o_orderkey | 1
o_custkey | 0.028476
o_orderstatus | 0.469662
o_totalprice | -0.0439993
o_orderdate | -0.0133034
o_orderpriority | 0.197801
o_clerk | -0.0169652
o_shippriority | 1
o_comment | 0.00423846
(9 rows)

BTW, in 8.0 table spaces allow a table and an index to be placed on
different disk devices, which may improve the performance. Is it
possible that planner accounts for this in the future. Do existing
commercial DBMSs already do this?
--
Tatsuo Ishii