Message-ID: <4E8AD46F.30003@thl.fi>
Date: Tue, 4 Oct 2011 12:39:59 +0300
From: =?ISO-8859-1?Q?Anssi_K=E4=E4ri=E4inen?= <anssi.kaariainen@thl.fi>
User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US;
	rv:1.9.2.23) Gecko/20110921 Lightning/1.0b2 Thunderbird/3.1.15
MIME-Version: 1.0
To: "pgsql-performance@postgresql.org" <pgsql-performance@postgresql.org>
Subject: Window functions and index usage
Content-Type: text/plain; charset="ISO-8859-1"; format=flowed
Content-Transfer-Encoding: quoted-printable

I have the following setup:

create table test(id integer, seq integer);
insert into test select generate_series(0, 100), generate_series(0, 1000)=
;
create unique index test_idx on test(id, seq);
analyze test;

Now I try to fetch the latest 5 values per id, ordered by seq from the=20
table:

select * from (
select id, seq, row_number() over (partition by id order by seq)
   from test
  where id in (1, 2, 3)
) where row_number() <=3D 5;

This does not use the index on id, seq for sorting the data. It uses a=20
bitmap index scan, and sequential scan when issued SET enable_bitmapscan=20
to false. Tested both on git head and 8.4.8. See end of post for plans.=20
It seems it would be possible to fetch the first values per id using the=20
index, or at least skip the sorting.

If I emulate the behavior I want by using:
  (select id, seq from test where id =3D 1 order by seq limit 5)
union
  (select id, seq from test where id =3D 2 order by seq limit 5)
union
  (select id, seq from test where id =3D 2 order by seq limit 5);
I get two orders of magnitude faster execution.

Is there some other way to run the query so that it would use the index?=20
Is there plans to support the index usage for the above query assuming=20
that it is possible to use the index for that query?

The real world use case would be to fetch latest 5 threads per=20
discussion forum in one query. Or fetch 3 latest comments for all=20
patches in given commit fest in single query.

  - Anssi K=E4=E4ri=E4inen

Normal plan (by the way, note the wildly inaccurate topmost row estimate)=
:

                                                         QUERY PLAN
-------------------------------------------------------------------------=
-------------------------------------------------
Subquery Scan on tmp  (cost=3D711.65..805.05 rows=3D958 width=3D16) (actu=
al=20
time=3D10.543..27.469 rows=3D15 loops=3D1)
    Filter: (tmp.row_number <=3D 5)
    ->  WindowAgg  (cost=3D711.65..769.13 rows=3D2874 width=3D8) (actual=20
time=3D10.537..23.551 rows=3D3003 loops=3D1)
          ->  Sort  (cost=3D711.65..718.83 rows=3D2874 width=3D8) (actual=
=20
time=3D10.528..13.798 rows=3D3003 loops=3D1)
                Sort Key: test.id, test.seq
                Sort Method: quicksort  Memory: 182kB
                ->  Bitmap Heap Scan on test  (cost=3D59.04..546.55=20
rows=3D2874 width=3D8) (actual time=3D0.580..4.750 rows=3D3003 loops=3D1)
                      Recheck Cond: (id =3D ANY ('{1,2,3}'::integer[]))
                      ->  Bitmap Index Scan on test_idx =20
(cost=3D0.00..58.32 rows=3D2874 width=3D0) (actual time=3D0.490..0.490 ro=
ws=3D3003=20
loops=3D1)
                            Index Cond: (id =3D ANY ('{1,2,3}'::integer[]=
))
  Total runtime: 27.531 ms
(11 rows)

Plan with set enable_bitmapscan set to off:

                                                         QUERY PLAN
-------------------------------------------------------------------------=
-------------------------------------------------
  Subquery Scan on tmp  (cost=3D2003.23..2096.64 rows=3D958 width=3D16)=20
(actual time=3D32.907..47.279 rows=3D15 loops=3D1)
    Filter: (tmp.row_number <=3D 5)
    ->  WindowAgg  (cost=3D2003.23..2060.71 rows=3D2874 width=3D8) (actua=
l=20
time=3D32.898..44.053 rows=3D3003 loops=3D1)
          ->  Sort  (cost=3D2003.23..2010.42 rows=3D2874 width=3D8) (actu=
al=20
time=3D32.883..36.067 rows=3D3003 loops=3D1)
                Sort Key: test.id, test.seq
                Sort Method: quicksort  Memory: 182kB
                ->  Seq Scan on test  (cost=3D0.00..1838.14 rows=3D2874=20
width=3D8) (actual time=3D0.017..26.733 rows=3D3003 loops=3D1)
                      Filter: (id =3D ANY ('{1,2,3}'::integer[]))
  Total runtime: 47.334 ms
(9 rows)

The UNION approach:

                                                               QUERY PLAN
-------------------------------------------------------------------------=
-------------------------------------------------------------
  HashAggregate  (cost=3D28.47..28.62 rows=3D15 width=3D8) (actual=20
time=3D0.176..0.194 rows=3D15 loops=3D1)
    ->  Append  (cost=3D0.00..28.40 rows=3D15 width=3D8) (actual=20
time=3D0.026..0.149 rows=3D15 loops=3D1)
          ->  Limit  (cost=3D0.00..9.42 rows=3D5 width=3D8) (actual=20
time=3D0.024..0.045 rows=3D5 loops=3D1)
                ->  Index Scan using test_idx on test =20
(cost=3D0.00..1820.87 rows=3D967 width=3D8) (actual time=3D0.022..0.034 r=
ows=3D5=20
loops=3D1)
                      Index Cond: (id =3D 1)
          ->  Limit  (cost=3D0.00..9.42 rows=3D5 width=3D8) (actual=20
time=3D0.017..0.034 rows=3D5 loops=3D1)
                ->  Index Scan using test_idx on test =20
(cost=3D0.00..1820.87 rows=3D967 width=3D8) (actual time=3D0.015..0.023 r=
ows=3D5=20
loops=3D1)
                      Index Cond: (id =3D 2)
          ->  Limit  (cost=3D0.00..9.42 rows=3D5 width=3D8) (actual=20
time=3D0.021..0.037 rows=3D5 loops=3D1)
                ->  Index Scan using test_idx on test =20
(cost=3D0.00..1820.87 rows=3D967 width=3D8) (actual time=3D0.019..0.026 r=
ows=3D5=20
loops=3D1)
                      Index Cond: (id =3D 3)
  Total runtime: 0.258 ms
(12 rows)