DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com;
	h=received:message-id:date:from:reply-to:to:subject:mime-version:content-type:content-transfer-encoding:content-disposition;
	b=LBh8BtXXDBt6pHS7SX2EytQveROsyFSORjVaaIq2dtCOcGrbQObA0ulaZjN1vThSE2e1MuEP1Ia0hILUCxjTh+5k095uArvfjKV8miTsEV3X3L3YkHLbKUoIWgiQYK9jCtlQ50dwidXFcRIRja5ACaC86pHujF7XxlB9GjYVbK0=
Message-ID: <758d5e7f0507220210bfa4978@mail.gmail.com>
Date: Fri, 22 Jul 2005 11:10:05 +0200
From: Dawid Kuroczko <qnex42@gmail.com>
Reply-To: Dawid Kuroczko <qnex42@gmail.com>
To: Postgresql Performance <pgsql-performance@postgresql.org>
Subject: Planner doesn't look at LIMIT?
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

Hello, I have PostgreSQL 8.0.3 running on a "workstation" with 768 MB
of RAM, under FreeBSD.  And I have a 47-milion row table:

qnex=3D# explain select * from log;
                              QUERY PLAN                              =20
-----------------------------------------------------------------------
 Seq Scan on log  (cost=3D0.00..1741852.36 rows=3D47044336 width=3D180)
(1 row)

...which is joined with a few smaller ones, like:

qnex=3D# explain select * from useragents;
                            QUERY PLAN                            =20
-------------------------------------------------------------------
 Seq Scan on useragents  (cost=3D0.00..9475.96 rows=3D364896 width=3D96)
(1 row)

shared_buffers =3D 5000
random_page_cost =3D 3
work_mem =3D 102400
effective_cache_size =3D 60000

Now, if I do a SELECT:

qnex=3D# EXPLAIN SELECT * FROM log NATURAL JOIN useragents LIMIT 1;
                                     QUERY PLAN
---------------------------------------------------------------------------=
----------
 Limit  (cost=3D15912.20..15912.31 rows=3D1 width=3D272)
   ->  Hash Join  (cost=3D15912.20..5328368.96 rows=3D47044336 width=3D272)
         Hash Cond: ("outer".useragent_id =3D "inner".useragent_id)
         ->  Seq Scan on log  (cost=3D0.00..1741852.36 rows=3D47044336 widt=
h=3D180)
         ->  Hash  (cost=3D9475.96..9475.96 rows=3D364896 width=3D96)
               ->  Seq Scan on useragents  (cost=3D0.00..9475.96
rows=3D364896 width=3D96)
(6 rows)

Or:

qnex=3D# EXPLAIN SELECT * FROM log NATURAL LEFT JOIN useragents LIMIT 1;
                                     QUERY PLAN
---------------------------------------------------------------------------=
----------
 Limit  (cost=3D15912.20..15912.31 rows=3D1 width=3D272)
   ->  Hash Left Join  (cost=3D15912.20..5328368.96 rows=3D47044336 width=
=3D272)
         Hash Cond: ("outer".useragent_id =3D "inner".useragent_id)
         ->  Seq Scan on log  (cost=3D0.00..1741852.36 rows=3D47044336 widt=
h=3D180)
         ->  Hash  (cost=3D9475.96..9475.96 rows=3D364896 width=3D96)
               ->  Seq Scan on useragents  (cost=3D0.00..9475.96
rows=3D364896 width=3D96)
(6 rows)

Time: 2.688 ms

...the query seems to last forever (its hashing 47 million rows!)

If I set enable_hashjoin=3Dfalse:

qnex=3D# EXPLAIN ANALYZE SELECT * FROM log NATURAL LEFT JOIN useragents LIM=
IT 1;
                                                                QUERY
PLAN
---------------------------------------------------------------------------=
----------------------------------------------------------------
 Limit  (cost=3D0.00..3.07 rows=3D1 width=3D272) (actual time=3D74.214..74.=
216
rows=3D1 loops=3D1)
   ->  Nested Loop Left Join  (cost=3D0.00..144295895.01 rows=3D47044336
width=3D272) (actual time=3D74.204..74.204 rows=3D1 loops=3D1)
         ->  Seq Scan on log  (cost=3D0.00..1741852.36 rows=3D47044336
width=3D180) (actual time=3D23.270..23.270 rows=3D1 loops=3D1)
         ->  Index Scan using useragents_pkey on useragents=20
(cost=3D0.00..3.02 rows=3D1 width=3D96) (actual time=3D50.867..50.867 rows=
=3D1
loops=3D1)
               Index Cond: ("outer".useragent_id =3D useragents.useragent_i=
d)
 Total runtime: 74.483 ms

...which is way faster.  Of course if I did:

qnex=3D# EXPLAIN ANALYZE SELECT * FROM log NATURAL LEFT JOIN useragents
WHERE logid =3D (SELECT logid FROM log LIMIT 1);
                                                            QUERY PLAN
---------------------------------------------------------------------------=
--------------------------------------------------------
 Nested Loop Left Join  (cost=3D0.04..6.09 rows=3D1 width=3D272) (actual
time=3D61.403..61.419 rows=3D1 loops=3D1)
   InitPlan
     ->  Limit  (cost=3D0.00..0.04 rows=3D1 width=3D4) (actual
time=3D0.029..0.032 rows=3D1 loops=3D1)
           ->  Seq Scan on log  (cost=3D0.00..1741852.36 rows=3D47044336
width=3D4) (actual time=3D0.023..0.023 rows=3D1 loops=3D1)
   ->  Index Scan using log_pkey on log  (cost=3D0.00..3.02 rows=3D1
width=3D180) (actual time=3D61.316..61.319 rows=3D1 loops=3D1)
         Index Cond: (logid =3D $0)
   ->  Index Scan using useragents_pkey on useragents=20
(cost=3D0.00..3.02 rows=3D1 width=3D96) (actual time=3D0.036..0.042 rows=3D=
1
loops=3D1)
         Index Cond: ("outer".useragent_id =3D useragents.useragent_id)
 Total runtime: 61.741 ms
(9 rows)

...I tried tweaking cpu_*, work_mem, effective_cache and so on, but without
any luck.  47 milion table is huge compared to useragents (I actually need
to join the log with 3 similar to useragents tables, and create a view out
of it).  Also tried using LEFT/RIGHT JOINS insead of (inner) JOINs...
Of course the database is freshly vacuum analyzed, and statistics are
set at 50...

My view of the problem is that planner ignores the "LIMIT" part.  It assume=
s
it _needs_ to return all 47 million rows joined with the useragents table, =
so
the hashjoin is the only sane approach.  But chances are that unless I'll
use LIMIT 200000, the nested loop will be much faster.

Any ideas how to make it work (other than rewriting the query to use
subselects, use explicit id-rows, disabling hashjoin completely)?
Or is this a bug?

   Regards,
      Dawid