From: Ben <midfield@gmail.com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: quoted-printable
Subject: incorrect row estimates for primary key join
Date: Mon, 24 Jun 2013 15:18:11 -0700
Message-Id: <7D0DD8B1-D23C-4BBC-9AB2-20D81F0B4BB8@gmail.com>
To: pgsql-performance@postgresql.org
Mime-Version: 1.0 (Apple Message framework v1283)
Precedence: bulk
Sender: pgsql-performance-owner@postgresql.org

hello postgresql experts --

i have a strange row estimate problem, which unfortunately i have trouble r=
eproducing for anything but very large tables which makes boiling down to a=
 simple example hard.  i'm using version 9.1.1, all tables have had analyze=
 run on them.

here's the example : i have a large table (billions of rows) with a five co=
lumn primary key and a sixth value column.  for confidentiality purposes i =
can't reproduce the exact schema here, but it is essentially

create table bigtable (
  id1 integer not null,
  id2 date not null,
  id3 integer not null,
  id4 time not null,
  id5 integer not null,
  value real not null,
  primary key (id1, id2, id3, id4, id5)
);

for various reasons there is only one id1 in the table right now, though in=
 the future there will be more; also the primary key was added after table =
creation with alter table, though that shouldn't matter.

i need to select out a somewhat arbitrary collection of rows out of bigtabl=
e.  to do so i generate a temporary table=20

create table jointable (
  id1 integer not null,
  id2 date not null,
  id3 integer not null,
  id4 time not null,
  id5 integer not null
);

and then perform a join against this table.

if jointable doesn't have many rows, the planner picks a nested loop over j=
ointable and a primary key lookup on bigtable.  in the following, for expos=
itory purposes, jointable has 10 rows.  we can see the planner knows this.

explain select * from bigtable join jointable using (id1, id2, id3, id4, id=
5);

 Nested Loop  (cost=3D0.00..6321.03 rows=3D145 width=3D28)
   ->  Seq Scan on jointable  (cost=3D0.00..1.10 rows=3D10 width=3D24)
   ->  Index Scan using bigtable_pkey on bigtable  (cost=3D0.00..631.97 row=
s=3D1 width=3D28)
         Index Cond: ((id1 =3D jointable.id1) AND (id2 =3D jointable.id2) A=
ND (id3 =3D jointable.id3) AND (id4 =3D jointable.id4) AND (vid =3D foo.vid=
))
(4 rows)

as you increase the number of rows in jointable, the planner switches to a =
sort + merge.  in this case jointable has roughly 2 million rows.

 Merge Join  (cost=3D727807979.29..765482193.16 rows=3D18212633 width=3D28)
  Merge Cond: ((bigtable.id1 =3D jointabe.id1) AND (bigtable.id2 =3D jointa=
ble.id2) AND (bigtable.id3 =3D jointable.id3) AND (bigtable.id4 =3D bigtabl=
e.id4) AND (bigtable.id5 =3D bigtable.id5))
   ->  Sort  (cost=3D727511795.16..735430711.00 rows=3D3167566336 width=3D2=
8)
         Sort Key: bigtable.id3, bigtable.id1, bigtable.id2, bigtable.id4, =
bigtable.id5
         ->  Seq Scan on bigtable  (cost=3D0.00..76085300.36 rows=3D3167566=
336 width=3D28)
   ->  Materialize  (cost=3D295064.70..305399.26 rows=3D2066911 width=3D24)
         ->  Sort  (cost=3D295064.70..300231.98 rows=3D2066911 width=3D24)
               Sort Key: jointable.id3, jointable.id1, jointable.id2, joint=
able.id4, jointable.id5
               ->  Seq Scan on jointable  (cost=3D0.00..35867.11 rows=3D206=
6911 width=3D24)
(9 rows)

the choice of sort + merge is really bad here, given the size of bigtable (=
3 billion rows and counting.)

some questions :

1 - first off, why isn't the sort happening on the primary key, so that big=
table does not have to be sorted?

2 - more importantly, since we are joining on the primary key, shouldn't th=
e row estimate coming out of the join be limited by the number of rows in j=
ointable?

for example, it is strange to see that if i put in a non-limiting limit sta=
tement (something bigger than the number of rows in jointable) it switches =
back to a nested loop + index scan :

explain select * from bigtable join jointable using (id1, id2, id3, id4, id=
5) limit 2500000;

 Limit  (cost=3D0.00..178452647.11 rows=3D2500000 width=3D28)
   ->  Nested Loop  (cost=3D0.00..1306127545.35 rows=3D18297957 width=3D28)
         ->  Seq Scan on jointable  (cost=3D0.00..35867.11 rows=3D2066911 w=
idth=3D24)
         ->  Index Scan using bigtable_pkey on bigtable  (cost=3D0.00..631.=
88 rows=3D1 width=3D28)
               Index Cond: ((id1 =3D jointable.id1) AND (id2 =3D jointable.=
id2) AND (id3 =3D jointable.id3) AND (id4 =3D jointable.id4) AND (id5 =3D j=
ointable.id5))
(5 rows)

am i not understanding the query planner, or is this a known issue in the q=
uery planner, or have i stumbled onto something amiss?  unfortunately any s=
ynthetic examples i was able to make (up to 10 million rows) did not exhibi=
t this behavior, which makes it hard to test.

best regards, ben


--=20
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance