pg.ddx.io pgsql-sql@postgresql.org mailing list archive
help / color / mirror / Atom feedalternate idioms for large "IN (...)" lists
4+ messages / 3 participants
[nested] [flat]
* alternate idioms for large "IN (...)" lists
@ 2002-06-02 06:10 russm <russm@icorp.com.au>
2002-06-02 18:01 ` Re: alternate idioms for large "IN (...)" lists Christopher Kings-Lynne <chriskl@familyhealth.com.au>
0 siblings, 1 reply; 4+ messages in thread
From: russm @ 2002-06-02 06:10 UTC (permalink / raw)
To: pgsql-sql
I'm working on an application (originally written for Oracle) that is being
brought to it's knees by one commonly-executed query - finding the most
common attributes for a given list of assets...
SELECT attribute_id, COUNT(asset_id)
FROM attribute_map
WHERE asset_id IN ( <potentially several thousand asset_id values> )
GROUP BY attribute_id
HAVING COUNT(asset_id) < <cutoff value>
ORDER BY count DESC
LIMIT <limit>
where attribute_map is a many-to-many map of asset_id to attribute_id -
demo=# \d attribute_map
Table "attribute_map"
Column | Type | Modifiers
--------------+---------+-----------
asset_id | integer |
attribute_id | integer |
Indexes: am_asset_id_idx,
am_attribute_id_idx
Unique keys: am_asset_id_attribute_id_un
Triggers: RI_ConstraintTrigger_26912,
RI_ConstraintTrigger_26906
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: alternate idioms for large "IN (...)" lists
2002-06-02 06:10 alternate idioms for large "IN (...)" lists russm <russm@icorp.com.au>
@ 2002-06-02 18:01 ` Christopher Kings-Lynne <chriskl@familyhealth.com.au>
2002-06-03 06:45 ` Re: alternate idioms for large "IN (...)" lists russm <russm@icorp.com.au>
0 siblings, 1 reply; 4+ messages in thread
From: Christopher Kings-Lynne @ 2002-06-02 18:01 UTC (permalink / raw)
To: russm <russm@icorp.com.au>; pgsql-sql
Yep, Postgresql's IN implementation is very slow. You are far better off
rewriting your query to use EXISTS or an OUTER JOIN.
See:
http://www3.us.postgresql.org/users-lounge/docs/7.2/postgres/functions-subqu
ery.html
eg.
SELECT attribute_id, COUNT(asset_id)
FROM attribute_map
WHERE EXISTS (SELECT asset_id FROM <potentially several thousand asset_id
values> WHERE asset_id=...)
GROUP BY attribute_id
HAVING COUNT(asset_id) < <cutoff value>
ORDER BY count DESC
LIMIT <limit>
or something like:
SELECT attribute_id, COUNT(asset_id)
FROM attribute_map atm RIGHT JOIN assets_map aam
ON atm.asset_id=asm.asset_id
GROUP BY....blah blah blah...
Play around with these alternative syntaxes and stay away from putting
thousands of rows in IN() and you will be able to make your query run orders
of magnitude faster.
Chris
----- Original Message -----
From: "russm" <russm@icorp.com.au>
To: <pgsql-sql@postgresql.org>
Sent: Saturday, June 01, 2002 11:10 PM
Subject: [SQL] alternate idioms for large "IN (...)" lists
> I'm working on an application (originally written for Oracle) that is
being
> brought to it's knees by one commonly-executed query - finding the most
> common attributes for a given list of assets...
>
>
> SELECT attribute_id, COUNT(asset_id)
> FROM attribute_map
> WHERE asset_id IN ( <potentially several thousand asset_id values> )
> GROUP BY attribute_id
> HAVING COUNT(asset_id) < <cutoff value>
> ORDER BY count DESC
> LIMIT <limit>
>
>
> where attribute_map is a many-to-many map of asset_id to attribute_id -
>
> demo=# \d attribute_map
> Table "attribute_map"
> Column | Type | Modifiers
> --------------+---------+-----------
> asset_id | integer |
> attribute_id | integer |
> Indexes: am_asset_id_idx,
> am_attribute_id_idx
> Unique keys: am_asset_id_attribute_id_un
> Triggers: RI_ConstraintTrigger_26912,
> RI_ConstraintTrigger_26906
>
>
> >From what i've read here, postgresql doesn't handle IN (...) queries
> especially efficiently, and it looks to me like I'm being bitten by that.
An
> EXPLAIN ANALYZE on that query with just under 40k rows in attribute_map
and
> 667 asset_id values in the IN (...) list returns
>
> NOTICE: QUERY PLAN:
>
> Limit (cost=64361.51..64361.51 rows=200 width=8) (actual
> time=24431.51..24431.80 rows=200 loops=1)
> -> Sort (cost=64361.51..64361.51 rows=1647 width=8) (actual
> time=24431.50..24431.61 rows=201 loops=1)
> -> Aggregate (cost=0.00..64273.49 rows=1647 width=8) (actual
> time=55.29..24324.75 rows=1747 loops=1)
> -> Group (cost=0.00..64191.13 rows=16473 width=8) (actual
> time=2.38..24198.18 rows=21308 loops=1)
> -> Index Scan using am_attribute_id_idx on
> attribute_map (cost=0.00..64149.94 rows=16473 width=8) (actual
> time=2.37..24034.97 rows=21308 loops=1)
> Total runtime: 24433.20 msec
>
>
> which I'm assuming means that the backend is doing a seperate index lookup
> for each of the 667 asset_id values in the list.
>
> Are there any standard idioms in postgres for getting around the poor
> handling of IN (...) lists? Placing the list of asset_id values in a table
> and then joining against that runs in about 1/15 the time (postgres makes
a
> hash of the asset_id values and then hash joins against the attribute_map)
> but since my asset_id values come from outside the database that approach
> would require creating and managing a whole lot of temporary tables, which
> i'd rather avoid.
>
> Much obliged for any suggestions
>
> Russell
>
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 3: if posting/reading through Usenet, please send an appropriate
> subscribe-nomail command to majordomo@postgresql.org so that your
> message can get through to the mailing list cleanly
>
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: alternate idioms for large "IN (...)" lists
2002-06-02 06:10 alternate idioms for large "IN (...)" lists russm <russm@icorp.com.au>
2002-06-02 18:01 ` Re: alternate idioms for large "IN (...)" lists Christopher Kings-Lynne <chriskl@familyhealth.com.au>
@ 2002-06-03 06:45 ` russm <russm@icorp.com.au>
2002-06-03 23:38 ` Re: alternate idioms for large "IN (...)" lists Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 4+ messages in thread
From: russm @ 2002-06-03 06:45 UTC (permalink / raw)
To: pgsql-sql
I've been playing with other ways of structuring the query to try and make
the planner use a hash join, and am currently looking at replacing
SELECT attribute_id, COUNT(asset_id)
FROM attribute_map
WHERE asset_id IN ( 564,3789, ... ,5240)
with
SELECT attribute_id, COUNT(asset_id)
FROM attribute_map m, (
SELECT 564 AS a UNION
SELECT 3789 AS a UNION
...
SELECT 5240 AS a
) a
WHERE m.asset_id = a.a
which produces a hash join between attribute_map and the list of asset_id
values, and runs in ~7% the time of the "IN (...)" version of the query.
I'll need to see how it scales to our full dataset, but this may be enough
of an improvement to get us by. The downside is that the queries I'm passing
to the DB are bloated by a factor of 5 - I suspect I can live with this.
Christopher suggested I rewrite the query in terms of EXISTS, but can't
figure out how to do that in a way that improves the performance of this
query - am I missing something here?
Just out of curiosity, why does postgresql's IN perform so poorly? Is it
because IN is implemented in terms of ANY? I would expect that the best
approach for an IN expression is a hash join, but that only works for = and
!=, and not any of the other operators that ANY supports.
cheers
Russell
On 3/6/02 4:01 AM, "Christopher Kings-Lynne" <chriskl@familyhealth.com.au>
wrote:
> Yep, Postgresql's IN implementation is very slow. You are far better off
> rewriting your query to use EXISTS or an OUTER JOIN.
>
> See:
> http://www3.us.postgresql.org/users-lounge/docs/7.2/postgres/functions-subqu
> ery.html
>
> eg.
>
> SELECT attribute_id, COUNT(asset_id)
> FROM attribute_map
> WHERE EXISTS (SELECT asset_id FROM <potentially several thousand asset_id
> values> WHERE asset_id=...)
> GROUP BY attribute_id
> HAVING COUNT(asset_id) < <cutoff value>
> ORDER BY count DESC
> LIMIT <limit>
>
> or something like:
>
> SELECT attribute_id, COUNT(asset_id)
> FROM attribute_map atm RIGHT JOIN assets_map aam
> ON atm.asset_id=asm.asset_id
> GROUP BY....blah blah blah...
>
> Play around with these alternative syntaxes and stay away from putting
> thousands of rows in IN() and you will be able to make your query run orders
> of magnitude faster.
>
> Chris
>
> ----- Original Message -----
> From: "russm" <russm@icorp.com.au>
> To: <pgsql-sql@postgresql.org>
> Sent: Saturday, June 01, 2002 11:10 PM
> Subject: [SQL] alternate idioms for large "IN (...)" lists
>
>
>> I'm working on an application (originally written for Oracle) that is
> being
>> brought to it's knees by one commonly-executed query - finding the most
>> common attributes for a given list of assets...
>>
>>
>> SELECT attribute_id, COUNT(asset_id)
>> FROM attribute_map
>> WHERE asset_id IN ( <potentially several thousand asset_id values> )
>> GROUP BY attribute_id
>> HAVING COUNT(asset_id) < <cutoff value>
>> ORDER BY count DESC
>> LIMIT <limit>
>>
>>
>> where attribute_map is a many-to-many map of asset_id to attribute_id -
>>
>> demo=# \d attribute_map
>> Table "attribute_map"
>> Column | Type | Modifiers
>> --------------+---------+-----------
>> asset_id | integer |
>> attribute_id | integer |
>> Indexes: am_asset_id_idx,
>> am_attribute_id_idx
>> Unique keys: am_asset_id_attribute_id_un
>> Triggers: RI_ConstraintTrigger_26912,
>> RI_ConstraintTrigger_26906
>>
>>
>>> From what i've read here, postgresql doesn't handle IN (...) queries
>> especially efficiently, and it looks to me like I'm being bitten by that.
> An
>> EXPLAIN ANALYZE on that query with just under 40k rows in attribute_map
> and
>> 667 asset_id values in the IN (...) list returns
>>
>> NOTICE: QUERY PLAN:
>>
>> Limit (cost=64361.51..64361.51 rows=200 width=8) (actual
>> time=24431.51..24431.80 rows=200 loops=1)
>> -> Sort (cost=64361.51..64361.51 rows=1647 width=8) (actual
>> time=24431.50..24431.61 rows=201 loops=1)
>> -> Aggregate (cost=0.00..64273.49 rows=1647 width=8) (actual
>> time=55.29..24324.75 rows=1747 loops=1)
>> -> Group (cost=0.00..64191.13 rows=16473 width=8) (actual
>> time=2.38..24198.18 rows=21308 loops=1)
>> -> Index Scan using am_attribute_id_idx on
>> attribute_map (cost=0.00..64149.94 rows=16473 width=8) (actual
>> time=2.37..24034.97 rows=21308 loops=1)
>> Total runtime: 24433.20 msec
>>
>>
>> which I'm assuming means that the backend is doing a seperate index lookup
>> for each of the 667 asset_id values in the list.
>>
>> Are there any standard idioms in postgres for getting around the poor
>> handling of IN (...) lists? Placing the list of asset_id values in a table
>> and then joining against that runs in about 1/15 the time (postgres makes
> a
>> hash of the asset_id values and then hash joins against the attribute_map)
>> but since my asset_id values come from outside the database that approach
>> would require creating and managing a whole lot of temporary tables, which
>> i'd rather avoid.
>>
>> Much obliged for any suggestions
>>
>> Russell
>>
>>
>>
>> ---------------------------(end of broadcast)---------------------------
>> TIP 3: if posting/reading through Usenet, please send an appropriate
>> subscribe-nomail command to majordomo@postgresql.org so that your
>> message can get through to the mailing list cleanly
>>
>
>
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: alternate idioms for large "IN (...)" lists
2002-06-02 06:10 alternate idioms for large "IN (...)" lists russm <russm@icorp.com.au>
2002-06-02 18:01 ` Re: alternate idioms for large "IN (...)" lists Christopher Kings-Lynne <chriskl@familyhealth.com.au>
2002-06-03 06:45 ` Re: alternate idioms for large "IN (...)" lists russm <russm@icorp.com.au>
@ 2002-06-03 23:38 ` Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 0 replies; 4+ messages in thread
From: Tom Lane @ 2002-06-03 23:38 UTC (permalink / raw)
To: russm <russm@icorp.com.au>; +Cc: pgsql-sql
russm <russm@icorp.com.au> writes:
> Just out of curiosity, why does postgresql's IN perform so poorly?
Because no one's gotten around to improving it.
The current implementation is actually just fine for small numbers of
values in the IN-list. Making it work nicely for large numbers of
values without pessimizing the small-list case would involve supporting
(at least) two implementations and teaching the planner how to choose
one. This definitely should be done, but has not gotten to the top of
anyone's to-do queue.
Most of the complaints we've seen about IN performance have to do with
the IN-subselect case, which is yet a different animal. It's likely
that that will get fixed before anyone worries about the large-number-
of-scalar-values case...
regards, tom lane
^ permalink raw reply [nested|flat] 4+ messages in thread
end of thread, other threads:[~2002-06-03 23:38 UTC | newest]
Thread overview: 4+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2002-06-02 06:10 alternate idioms for large "IN (...)" lists russm <russm@icorp.com.au>
2002-06-02 18:01 ` Christopher Kings-Lynne <chriskl@familyhealth.com.au>
2002-06-03 06:45 ` russm <russm@icorp.com.au>
2002-06-03 23:38 ` Tom Lane <tgl@sss.pgh.pa.us>
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