Startup cost of sequential scan

Hi!

Our customer have a bad plan problem, which could be reduced to the
following example.

create table t1 (id int primary key, k int);
create table t2 (id int);

insert into t1 (select i, i from generate_series(1,1000000) i);
insert into t2 (select 0 from generate_series(1,100)i);
insert into t2 values (500000);

For the following query the plan is OK despite number of resulting
rows is very much overestimated.

# explain select * from
t1 join t2 x1 on x1.id = t1.k
join t2 x2  on x2.id = t1.k
join t2 x3  on x3.id = t1.k
join t2 x4  on x4.id = t1.k
join t2 x5  on x5.id = t1.k
join t2 x6  on x6.id = t1.k
join t2 x7  on x7.id = t1.k
join t2 x8  on x8.id = t1.k
join t2 x9  on x9.id = t1.k
where t1.id = 500000;

  QUERY PLAN

------------------------------------------------------------------------------------------------------------------------------------------------------------
 Hash Join  (cost=265.98..104071348014760.11 rows=9240411823550620 width=44)
   Hash Cond: (x1.id = x8.id)
   ->  Hash Join  (cost=22.80..25.20 rows=942425865760 width=36)
         Hash Cond: (x1.id = t1.k)
         ->  Seq Scan on t2 x1  (cost=0.00..2.01 rows=101 width=4)
         ->  Hash  (cost=22.79..22.79 rows=1 width=32)
               ->  Hash Join  (cost=20.39..22.79 rows=1 width=32)
                     Hash Cond: (x7.id = t1.k)
                     ->  Seq Scan on t2 x7  (cost=0.00..2.01 rows=101 width=4)
                     ->  Hash  (cost=20.38..20.38 rows=1 width=28)
                           ->  Hash Join  (cost=17.98..20.38 rows=1 width=28)
                                 Hash Cond: (x6.id = t1.k)
                                 ->  Seq Scan on t2 x6
(cost=0.00..2.01 rows=101 width=4)
                                 ->  Hash  (cost=17.96..17.96 rows=1 width=24)
                                       ->  Hash Join
(cost=15.57..17.96 rows=1 width=24)
                                             Hash Cond: (x5.id = t1.k)
                                             ->  Seq Scan on t2 x5
(cost=0.00..2.01 rows=101 width=4)
                                             ->  Hash
(cost=15.55..15.55 rows=1 width=20)
                                                   ->  Hash Join
(cost=13.15..15.55 rows=1 width=20)
                                                         Hash Cond:
(x4.id = t1.k)
                                                         ->  Seq Scan
on t2 x4  (cost=0.00..2.01 rows=101 width=4)
                                                         ->  Hash
(cost=13.14..13.14 rows=1 width=16)
                                                               ->
Hash Join  (cost=10.74..13.14 rows=1 width=16)

Hash Cond: (x3.id = t1.k)

->  Seq Scan on t2 x3  (cost=0.00..2.01 rows=101 width=4)

->  Hash  (cost=10.73..10.73 rows=1 width=12)

    ->  Hash Join  (cost=8.46..10.73 rows=1 width=12)

          Hash Cond: (x2.id = t1.k)

          ->  Seq Scan on t2 x2  (cost=0.00..2.01 rows=101 width=4)

          ->  Hash  (cost=8.44..8.44 rows=1 width=8)

                ->  Index Scan using t1_pkey on t1  (cost=0.42..8.44
rows=1 width=8)

                      Index Cond: (id = 500000)
   ->  Hash  (cost=118.17..118.17 rows=10001 width=8)
         ->  Hash Join  (cost=3.27..118.17 rows=10001 width=8)
               Hash Cond: (x8.id = x9.id)
               ->  Seq Scan on t2 x8  (cost=0.00..2.01 rows=101 width=4)
               ->  Hash  (cost=2.01..2.01 rows=101 width=4)
                     ->  Seq Scan on t2 x9  (cost=0.00..2.01 rows=101 width=4)
(38 rows)

But when you add LIMIT clause, index scan on t1 turns out into sequential scan.

# explain select * from
t1 join t2 x1 on x1.id = t1.k
join t2 x2  on x2.id = t1.k
join t2 x3  on x3.id = t1.k
join t2 x4  on x4.id = t1.k
join t2 x5  on x5.id = t1.k
join t2 x6  on x6.id = t1.k
join t2 x7  on x7.id = t1.k
join t2 x8  on x8.id = t1.k
join t2 x9  on x9.id = t1.k
where t1.id = 500000 limit 100;
                                                    QUERY PLAN
-------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..1.55 rows=100 width=44)
   ->  Nested Loop  (cost=0.00..142805795187416.44
rows=9240411823550620 width=44)
         Join Filter: (x1.id = x9.id)
         ->  Nested Loop  (cost=0.00..1427775203576.57
rows=93318825071840 width=40)
               Join Filter: (x1.id = x8.id)
               ->  Nested Loop  (cost=0.00..16947.91 rows=942425865760 width=36)
                     Join Filter: (t1.k = x1.id)
                     ->  Nested Loop  (cost=0.00..16944.63 rows=1 width=32)
                           Join Filter: (t1.k = x7.id)
                           ->  Nested Loop  (cost=0.00..16941.36
rows=1 width=28)
                                 Join Filter: (t1.k = x6.id)
                                 ->  Nested Loop  (cost=0.00..16938.09
rows=1 width=24)
                                       Join Filter: (t1.k = x5.id)
                                       ->  Nested Loop
(cost=0.00..16934.82 rows=1 width=20)
                                             Join Filter: (t1.k = x4.id)
                                             ->  Nested Loop
(cost=0.00..16931.54 rows=1 width=16)
                                                   Join Filter: (t1.k = x3.id)
                                                   ->  Nested Loop
(cost=0.00..16928.27 rows=1 width=12)
                                                         Join Filter:
(t1.k = x2.id)
                                                         ->  Seq Scan
on t1  (cost=0.00..16925.00 rows=1 width=8)
                                                               Filter:
(id = 500000)
                                                         ->  Seq Scan
on t2 x2  (cost=0.00..2.01 rows=101 width=4)
                                                   ->  Seq Scan on t2
x3  (cost=0.00..2.01 rows=101 width=4)
                                             ->  Seq Scan on t2 x4
(cost=0.00..2.01 rows=101 width=4)
                                       ->  Seq Scan on t2 x5
(cost=0.00..2.01 rows=101 width=4)
                                 ->  Seq Scan on t2 x6
(cost=0.00..2.01 rows=101 width=4)
                           ->  Seq Scan on t2 x7  (cost=0.00..2.01
rows=101 width=4)
                     ->  Seq Scan on t2 x1  (cost=0.00..2.01 rows=101 width=4)
               ->  Materialize  (cost=0.00..2.51 rows=101 width=4)
                     ->  Seq Scan on t2 x8  (cost=0.00..2.01 rows=101 width=4)
         ->  Materialize  (cost=0.00..2.51 rows=101 width=4)
               ->  Seq Scan on t2 x9  (cost=0.00..2.01 rows=101 width=4)
(32 rows)

Obviously, that happens because selectivity for join with t2 is
overestimated and multiplied many times.  And improvements in this
area seems quite hard for me.

But I think there is another issue in sequential scan cost.  We have
zero startup cost for sequential scan.  But why?  As I get sequential
scan should estimate amount of resources we need to spend in order to
start returning rows.  So, in our example when we expect finding 1 row
from the table, in average we have to scan half of table before find
this row.  Thus, startup_cost should be about half of total cost.
Attached POC patch implements that.  In the given example sequential
scan turns out back to index scan.

Any thoughts?

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company