DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma;
	h=mime-version:in-reply-to:references:date:message-id:subject:from:to
	:cc:content-type:content-transfer-encoding;
	b=cP68LUVk0rqidHAxqFXoI6P2EI90soVvt7R9MRGYyP1ofbhxvYW7ax2OCLgvDGoJ7n
	8et9u2p7IMKTj3y2OVtqxK64P2FxcuLanknb2AcaggcBdMppwRYuuhgokUmYP1s55q6I
	WYIaoXc3kBe7Qh8ZpvsgFEJ3ajwaYtOoCEenU=
MIME-Version: 1.0
In-Reply-To: <D7BE02F0-7D03-400B-800F-43778243941B@gmail.com>
References: <75F42287-42D3-4FD5-AFFA-64B1CE3C0195@gmail.com>
	<AANLkTikDbBT69mmGW=2uq9Jzbbeki44ZsXPnsMXqXApt@mail.gmail.com>
	<D7BE02F0-7D03-400B-800F-43778243941B@gmail.com>
Date: Mon, 18 Apr 2011 14:27:27 -0400
Message-ID: <BANLkTimX_2b1p80TA7bcyAsugiwUB6-Bfg@mail.gmail.com>
Subject: Re: Select in subselect vs select = any array
From: Robert Haas <robertmhaas@gmail.com>
To: Adam Tistler <atistler@gmail.com>
Cc: Pavel Stehule <pavel.stehule@gmail.com>, pgsql-performance@postgresql.org
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

On Sun, Mar 20, 2011 at 11:20 PM, Adam Tistler <atistler@gmail.com> wrote:
> logicops2=3D# explain analyze select count(*) from nodes where node_id =
=3D any( =A0Array(select node_id from nodes limit 100000) );
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 QUERY PLAN
> -------------------------------------------------------------------------=
----------------------------------------------------------------
> =A0Aggregate =A0(cost=3D1718.59..1718.60 rows=3D1 width=3D0) (actual time=
=3D509.126..509.127 rows=3D1 loops=3D1)
> =A0 InitPlan 1 (returns $0)
> =A0 =A0 -> =A0Limit =A0(cost=3D0.00..1637.04 rows=3D100000 width=3D4) (ac=
tual time=3D0.010..76.604 rows=3D100000 loops=3D1)
> =A0 =A0 =A0 =A0 =A0 -> =A0Seq Scan on nodes =A0(cost=3D0.00..12355.41 row=
s=3D754741 width=3D4) (actual time=3D0.008..38.105 rows=3D100000 loops=3D1)
> =A0 -> =A0Bitmap Heap Scan on nodes =A0(cost=3D42.67..81.53 rows=3D10 wid=
th=3D0) (actual time=3D447.274..484.283 rows=3D100000 loops=3D1)
> =A0 =A0 =A0 =A0 Recheck Cond: (node_id =3D ANY ($0))
> =A0 =A0 =A0 =A0 -> =A0Bitmap Index Scan on n_node_id_index =A0(cost=3D0.0=
0..42.67 rows=3D10 width=3D0) (actual time=3D447.074..447.074 rows=3D100000=
 loops=3D1)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 Index Cond: (node_id =3D ANY ($0))
> =A0Total runtime: 509.209 ms
> (9 rows)
>
> Time: 510.009 ms
>
>
> logicops2=3D# explain analyze select count(*) from nodes where node_id in=
 (select node_id from nodes limit 100000);
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =
=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 QUERY PLAN
> -------------------------------------------------------------------------=
---------------------------------------------------------------
> =A0Aggregate =A0(cost=3D3017.17..3017.18 rows=3D1 width=3D0) (actual time=
=3D1052.866..1052.866 rows=3D1 loops=3D1)
> =A0 -> =A0Nested Loop =A0(cost=3D2887.04..3016.67 rows=3D200 width=3D0) (=
actual time=3D167.310..1021.540 rows=3D100000 loops=3D1)
> =A0 =A0 =A0 =A0 -> =A0HashAggregate =A0(cost=3D2887.04..2889.04 rows=3D20=
0 width=3D4) (actual time=3D167.198..251.205 rows=3D100000 loops=3D1)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 -> =A0Limit =A0(cost=3D0.00..1637.04 rows=3D1=
00000 width=3D4) (actual time=3D0.008..80.090 rows=3D100000 loops=3D1)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 -> =A0Seq Scan on nodes =A0(cost=
=3D0.00..12355.41 rows=3D754741 width=3D4) (actual time=3D0.007..41.566 row=
s=3D100000 loops=3D1)
> =A0 =A0 =A0 =A0 -> =A0Index Scan using n_node_id_index on nodes =A0(cost=
=3D0.00..0.63 rows=3D1 width=3D4) (actual time=3D0.006..0.007 rows=3D1 loop=
s=3D100000)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 Index Cond: (public.nodes.node_id =3D public.=
nodes.node_id)
> =A0Total runtime: 1053.523 ms
> (8 rows)
>
> Time: 1054.864 ms

This is a pretty interesting example.  I think this is just an
optimizer limitation.

When trying to build a join tree (in this case, between the copy of
nodes inside the subselect and the copy outside the subselect), the
planner considers three main join strategies: hash join, nested loop,
merge join.  A merge or hash join will have to read the
outside-the-subselect copy of nodes in its entirety (I think); the
only way to avoid that is to compute the subselect first and then use
the index probes to pull out just the matching rows.  That's what the
planner did in both cases, but in the second case it's not smart
enough to see that it can gather up all the values from the inner side
of the join and shove them into a bitmap index scan all at once, so it
just uses a regular index scan to pull 'em out one at a time.

I think this would be pretty tricky to support, since the join node
would need to understand all the parameter passing that needs to
happen between the inner and outer sides of the loop; it's almost like
a whole new join type.

You might also want to make the opposite transformation, turning the
first plan into the second one, if (for example) the subselect is
going to return a gigabyte of data.  But we're just not that smart.

--=20
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company