From: Robert Haas <robertmhaas@gmail.com>
To: Adam Tistler <atistler@gmail.com>
Cc: Pavel Stehule <pavel.stehule@gmail.com>
Cc: pgsql-performance@postgresql.org
Subject: Re: Select in subselect vs select = any array
Date: Mon, 18 Apr 2011 14:27:27 -0400
Message-ID: <BANLkTimX_2b1p80TA7bcyAsugiwUB6-Bfg@mail.gmail.com> (raw)
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>
On Sun, Mar 20, 2011 at 11:20 PM, Adam Tistler <atistler@gmail.com> wrote:
> logicops2=# explain analyze select count(*) from nodes where node_id = any( Array(select node_id from nodes limit 100000) );
> QUERY PLAN
> -----------------------------------------------------------------------------------------------------------------------------------------
> Aggregate (cost=1718.59..1718.60 rows=1 width=0) (actual time=509.126..509.127 rows=1 loops=1)
> InitPlan 1 (returns $0)
> -> Limit (cost=0.00..1637.04 rows=100000 width=4) (actual time=0.010..76.604 rows=100000 loops=1)
> -> Seq Scan on nodes (cost=0.00..12355.41 rows=754741 width=4) (actual time=0.008..38.105 rows=100000 loops=1)
> -> Bitmap Heap Scan on nodes (cost=42.67..81.53 rows=10 width=0) (actual time=447.274..484.283 rows=100000 loops=1)
> Recheck Cond: (node_id = ANY ($0))
> -> Bitmap Index Scan on n_node_id_index (cost=0.00..42.67 rows=10 width=0) (actual time=447.074..447.074 rows=100000 loops=1)
> Index Cond: (node_id = ANY ($0))
> Total runtime: 509.209 ms
> (9 rows)
>
> Time: 510.009 ms
>
>
> logicops2=# explain analyze select count(*) from nodes where node_id in (select node_id from nodes limit 100000);
> QUERY PLAN
> ----------------------------------------------------------------------------------------------------------------------------------------
> Aggregate (cost=3017.17..3017.18 rows=1 width=0) (actual time=1052.866..1052.866 rows=1 loops=1)
> -> Nested Loop (cost=2887.04..3016.67 rows=200 width=0) (actual time=167.310..1021.540 rows=100000 loops=1)
> -> HashAggregate (cost=2887.04..2889.04 rows=200 width=4) (actual time=167.198..251.205 rows=100000 loops=1)
> -> Limit (cost=0.00..1637.04 rows=100000 width=4) (actual time=0.008..80.090 rows=100000 loops=1)
> -> Seq Scan on nodes (cost=0.00..12355.41 rows=754741 width=4) (actual time=0.007..41.566 rows=100000 loops=1)
> -> Index Scan using n_node_id_index on nodes (cost=0.00..0.63 rows=1 width=4) (actual time=0.006..0.007 rows=1 loops=100000)
> Index Cond: (public.nodes.node_id = public.nodes.node_id)
> Total 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.
--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-performance@postgresql.org
Cc: robertmhaas@gmail.com, atistler@gmail.com, pavel.stehule@gmail.com
Subject: Re: Select in subselect vs select = any array
In-Reply-To: <BANLkTimX_2b1p80TA7bcyAsugiwUB6-Bfg@mail.gmail.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox