DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com;
	h=received:message-id:date:from:reply-to:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references;
	b=pWOPRiwqOkO5qXHAKdUUOSISG7INoiC7PyFZzp1QNhVUh8rCDsaR8JHEf8l6PyQQIj5AaYpyU8HYcMtlmXwjFqCltIxLEy485tOHnxPS5YijYa7ZS9xwBt42+yhtSlRKOXQRfVujZ8x/7EFBGEVJAAscPs+ayv+jj2ZOvoQO7nM=
Message-ID: <758d5e7f05072209094156c984@mail.gmail.com>
Date: Fri, 22 Jul 2005 18:09:37 +0200
From: Dawid Kuroczko <qnex42@gmail.com>
Reply-To: Dawid Kuroczko <qnex42@gmail.com>
To: Tom Lane <tgl@sss.pgh.pa.us>
Subject: Re: Planner doesn't look at LIMIT?
Cc: Postgresql Performance <pgsql-performance@postgresql.org>
In-Reply-To: <29473.1122043197@sss.pgh.pa.us>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline
References: <758d5e7f0507220210bfa4978@mail.gmail.com>
	<29473.1122043197@sss.pgh.pa.us>

On 7/22/05, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Dawid Kuroczko <qnex42@gmail.com> writes:
> > qnex=3D# EXPLAIN SELECT * FROM log NATURAL JOIN useragents LIMIT 1;
>=20
> >  Limit  (cost=3D15912.20..15912.31 rows=3D1 width=3D272)
> >    ->  Hash Join  (cost=3D15912.20..5328368.96 rows=3D47044336 width=3D=
272)
>=20
> This is quite strange.  The nestloop plan definitely should be preferred
> in the context of the LIMIT, considering that it has far lower estimated
> cost.  And it is preferred in simple tests for me.  It seems there must
> be something specific to your installation that's causing the planner to
> go wrong.  Can you develop a self-contained test case that behaves this
> way for you?

Why, certainly.  I did test it also on Gentoo Linux PostgreSQL 8.0.1 (yeah,
a bit older one), but the behaviour is the same.  The test looks like this:

-- First lets make a "small" lookup table -- 400000 rows.
CREATE TABLE lookup (
    lookup_id serial PRIMARY KEY,
    value integer NOT NULL
);
INSERT INTO lookup (value) SELECT * FROM generate_series(1, 400000);
VACUUM ANALYZE lookup;
-- Then lets make a huge data table...
CREATE TABLE huge_data (
    huge_data_id serial PRIMARY KEY,
    lookup_id integer NOT NULL
);
INSERT INTO huge_data (lookup_id) SELECT lookup_id FROM lookup;
INSERT INTO huge_data (lookup_id) SELECT lookup_id FROM huge_data; --    80=
0 000
INSERT INTO huge_data (lookup_id) SELECT lookup_id FROM huge_data; --  1 60=
0 000
INSERT INTO huge_data (lookup_id) SELECT lookup_id FROM huge_data; --  3 20=
0 000
INSERT INTO huge_data (lookup_id) SELECT lookup_id FROM huge_data; --  6 40=
0 000
INSERT INTO huge_data (lookup_id) SELECT lookup_id FROM huge_data; -- 12 80=
0 000
-- You may want to put ANALYZE and EXPLAIN between each of these
-- steps.  In my cases, at 12.8 mln rows PostgreSQL seems to go for hashjoi=
n
-- in each case.  YMMV, so you may try to push it up to 1024 mln rows.
INSERT INTO huge_data (lookup_id) SELECT lookup_id FROM huge_data; -- 25 60=
0 000
ANALYZE huge_data;
EXPLAIN SELECT * FROM huge_data NATURAL JOIN lookup LIMIT 1;

My EXPLAIN FROM Linux (SMP P-III box), with PostgreSQL 8.0.1, during making
this test case:

qnex=3D# EXPLAIN SELECT * FROM huge_data NATURAL JOIN lookup LIMIT 1;
                                     QUERY PLAN
---------------------------------------------------------------------------=
---------
Limit  (cost=3D0.00..3.21 rows=3D1 width=3D12)
  ->  Nested Loop  (cost=3D0.00..19557596.04 rows=3D6094777 width=3D12)
        ->  Seq Scan on huge_data  (cost=3D0.00..95372.42 rows=3D6399942 wi=
dth=3D8)
        ->  Index Scan using lookup_pkey on lookup  (cost=3D0.00..3.02
rows=3D1 width=3D8)
              Index Cond: ("outer".lookup_id =3D lookup.lookup_id)
(5 rows)

Time: 4,333 ms
qnex=3D# INSERT INTO huge_data (lookup_id) SELECT lookup_id FROM
huge_data; -- 12 800 000
INSERT 0 6400000
Time: 501014,692 ms
qnex=3D# ANALYZE huge_data;
ANALYZE
Time: 4243,453 ms
qnex=3D# EXPLAIN SELECT * FROM huge_data NATURAL JOIN lookup LIMIT 1;
                                  QUERY PLAN
---------------------------------------------------------------------------=
----
Limit  (cost=3D11719.00..11719.09 rows=3D1 width=3D12)
  ->  Hash Join  (cost=3D11719.00..1212739.73 rows=3D12800185 width=3D12)
        Hash Cond: ("outer".lookup_id =3D "inner".lookup_id)
        ->  Seq Scan on huge_data  (cost=3D0.00..190747.84 rows=3D12800184 =
width=3D8)
        ->  Hash  (cost=3D5961.00..5961.00 rows=3D400000 width=3D8)
              ->  Seq Scan on lookup  (cost=3D0.00..5961.00 rows=3D400000 w=
idth=3D8)
(6 rows)

   Regards,
     Dawid