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=R1QoxStqWrghhpk7TOc0/qoVi4LnLpOAqN2FwQ1OVbrYBD9b2o1CbmUi7zddcH3Y376XQY+yQOT3we4BGeYS52Qxbnth+2VK+Dk/UbhC903liHyF85MhyMDJ+edbUgTJzy7TZksuddd1m/g3Iucn4QoxDwhZKV3hZx8rQzlBoE8=
Message-ID: <41b0fe890508051135712a086b@mail.gmail.com>
Date: Fri, 5 Aug 2005 11:35:03 -0700
From: Rhett Garber <rhettg@gmail.com>
Reply-To: Rhett Garber <rhettg@gmail.com>
To: pgsql-performance@postgresql.org
Subject: Why hash join instead of nested loop?
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

I've got similiar queries that I think should be evaluated (as
displayed through 'explain') the same, but don't.
Hopefully this is the rigth place to send such a question and one of
you can help explain this to me.

The Tables:
   Connection  - 1.2 million entries, about 60 megs, 3 integer fields
that link two tables together (i.e. an identifier and two foreign
keys).
                         has an index on the identifier and either of
the foreign keys.
   rtmessagestate - very small, 5 entries
   rtmessage - pretty big, 80,000 entries


The Queries:
  =20
select rtmessagestate.* from rtmessagestate, connection where
connection_registry_id =3D 40105 and obj1 =3D 73582 and obj2 =3D
rtmessagestate.id;
      returns 1 in 13.7 ms
                                                                           =
=20
select rtmessage.id, subject from rtmessage, connection where
connection_registry_id =3D 40003 and obj1 =3D 4666 and obj2 =3D
rtmessage.id;
      returns 12 in 2 ms

Some more possibly important details:
   entries in Connection with connection_registry_id =3D 40105: 30,000
     entries with this id and obj1 =3D 73582: 1
   entries in Connection with connection_registry_id =3D 40003: 6,000
     entries with this id and obj1 =3D 4666: 20
  =20
but as I said before, there is an btree index on (connection_registry_id, o=
bj1)

Explain:
The first query, breaks down as:
Hash Join  (cost=3D5.96..7.04 rows=3D1 width=3D14)
       Hash Cond: ("outer".id =3D "inner".obj2)
          ->  Seq Scan on rtmessagestate  (cost=3D0.00..1.05 rows=3D5 width=
=3D14)
       ->  Hash  (cost=3D5.96..5.96 rows=3D1 width=3D4)
             ->  Index Scan using connection_regid_obj1_index on
connection  (cost=3D0.00..5.96 rows=3D1 width=3D4)
                   Index Cond: ((connection_registry_id =3D 40105) AND
(obj1 =3D 73582))(6 rows)


While the second query is:
 Nested Loop  (cost=3D0.00..11.62 rows=3D2 width=3D38)
       ->  Index Scan using connection_regid_obj1_index on connection=20
(cost=3D0.00..5.96 rows=3D1 width=3D4)
             Index Cond: ((connection_registry_id =3D 40003) AND (obj1 =3D =
4666))
       ->  Index Scan using rtmessage_pkey on rtmessage=20
(cost=3D0.00..5.65 rows=3D1 width=3D38)
             Index Cond: ("outer".obj2 =3D rtmessage.id)
             (5 rows)

Actually running these queries shows that the second one (nested loop)
is much faster than the hash join, presumably because of hash startup
costs. Any ideas how I can make them both use the nested loop. I
assume that this would be the fastest for both.

Oddly enough, running the 1st query (rtmessagestate) as two queries or
with a sub query is way faster than doing the join.

And yes, I realize this schema may not be the most efficient for these
examples, but it seems to be the most flexible. I'm working on some
schema improvements also
but if I could understand why this is slow that woudl probably help also.

Thanks for you help,

Rhett