39

Why is the "IN" operator so slow when used with subquery?

select * 
from view1 
where id in (1,2,3,4,5,6,7,8,9,10) 
order by somedata;

executes in 9ms.

select * 
from view1 
where id in (select ext_id 
             from aggregate_table 
             order by somedata limit 10) 
order by somedata;

executes in 25000ms and seems to use sequential scan on the view (view1) instead of index scan on primary keys returned by subquery as in does in first query.

The subquery select ext_id from aggregate_table order by somedata limit 10 executes in 0.1ms

so the slowness of the second query is caused by sequential scan on view1 which is a view containing three UNIONS and about three JOINS in each UNION. The first UNION contains about a 1M rows, others much less. Joins with tables with some 100K rows. That's not so relevant, though, I just wanted to understand the IN operator behaviour.

What I'm trying to accomplish is to take the result of subquery (a set of primary keys) and select the data from a complex view (view1) using just them.

I also cannot use

select v1.* 
from view1 v1, 
     aggregate_table at 
where v1.id = at.ext_id 
order by at.somedata 
limit 10

because I do not want to sort the big join by somedata. I just want to select 10 results from the view by primary keys and then sort only these.

The question is why does IN operator perform fast when I explicitly list these keys and so slow when I use a fast subquery that returns the exact same set of keys?

EXPLAIN ANALYZE as requested

first query - select * from view1 where id in (1,2,3,4,5,6,7,8,9,10) order by somedata;

    Sort  (cost=348.480..348.550 rows=30 width=943) (actual time=14.385..14.399 rows=10 loops=1)
    Sort Key: "india".three
    Sort Method:  quicksort  Memory: 30kB
  ->  Append  (cost=47.650..347.440 rows=30 width=334) (actual time=11.528..14.275 rows=10 loops=1)
        ->  Subquery Scan "*SELECT* 1"  (cost=47.650..172.110 rows=10 width=496) (actual time=11.526..12.301 rows=10 loops=1)
              ->  Nested Loop  (cost=47.650..172.010 rows=10 width=496) (actual time=11.520..12.268 rows=10 loops=1)
                    ->  Hash Join  (cost=47.650..87.710 rows=10 width=371) (actual time=11.054..11.461 rows=10 loops=1)
                            Hash Cond: (hotel.alpha_five = juliet_xray.alpha_five)
                          ->  Bitmap Heap Scan on sierra hotel  (cost=42.890..82.800 rows=10 width=345) (actual time=10.835..11.203 rows=10 loops=1)
                                  Recheck Cond: (four = ANY ('quebec'::integer[]))
                                ->  Bitmap Index Scan on seven  (cost=0.000..42.890 rows=10 width=0) (actual time=0.194..0.194 rows=10 loops=1)
                                        Index Cond: (four = ANY ('quebec'::integer[]))
                          ->  Hash  (cost=4.340..4.340 rows=34 width=30) (actual time=0.184..0.184 rows=34 loops=1)
                                ->  Seq Scan on six juliet_xray  (cost=0.000..4.340 rows=34 width=30) (actual time=0.029..0.124 rows=34 loops=1)
                    ->  Index Scan using charlie on juliet_two zulu  (cost=0.000..8.390 rows=1 width=129) (actual time=0.065..0.067 rows=1 loops=10)
                            Index Cond: (zulu.four = hotel.victor_whiskey)
        ->  Subquery Scan "*SELECT* 2"  (cost=4.760..97.420 rows=10 width=366) (actual time=0.168..0.168 rows=0 loops=1)
              ->  Hash Join  (cost=4.760..97.320 rows=10 width=366) (actual time=0.165..0.165 rows=0 loops=1)
                      Hash Cond: (alpha_xray.alpha_five = juliet_xray2.alpha_five)
                    ->  Nested Loop  (cost=0.000..92.390 rows=10 width=340) (actual time=0.162..0.162 rows=0 loops=1)
                          ->  Seq Scan on lima_echo alpha_xray  (cost=0.000..8.340 rows=10 width=216) (actual time=0.159..0.159 rows=0 loops=1)
                                  Filter: (four = ANY ('quebec'::integer[]))
                          ->  Index Scan using charlie on juliet_two xray  (cost=0.000..8.390 rows=1 width=128) (never executed)
                                  Index Cond: (zulu2.four = alpha_xray.victor_whiskey)
                    ->  Hash  (cost=4.340..4.340 rows=34 width=30) (never executed)
                          ->  Seq Scan on six uniform  (cost=0.000..4.340 rows=34 width=30) (never executed)
        ->  Subquery Scan "*SELECT* 3"  (cost=43.350..77.910 rows=10 width=141) (actual time=1.775..1.775 rows=0 loops=1)
              ->  Hash Join  (cost=43.350..77.810 rows=10 width=141) (actual time=1.771..1.771 rows=0 loops=1)
                      Hash Cond: (golf.alpha_five = juliet_xray3.alpha_five)
                    ->  Bitmap Heap Scan on lima_golf golf  (cost=38.590..72.910 rows=10 width=115) (actual time=0.110..0.110 rows=0 loops=1)
                            Recheck Cond: (four = ANY ('quebec'::integer[]))
                          ->  Bitmap Index Scan on victor_hotel  (cost=0.000..38.590 rows=10 width=0) (actual time=0.105..0.105 rows=0 loops=1)
                                  Index Cond: (four = ANY ('quebec'::integer[]))
                    ->  Hash  (cost=4.340..4.340 rows=34 width=30) (actual time=0.118..0.118 rows=34 loops=1)
                          ->  Seq Scan on six victor_kilo  (cost=0.000..4.340 rows=34 width=30) (actual time=0.007..0.063 rows=34 loops=1)
 Total runtime: 14.728 ms

second query - select * from view1 where id in (select ext_id from aggregate_table order by somedata limit 10) order by somedata;

Sort  (cost=254515.780..254654.090 rows=55325 width=943) (actual time=24687.475..24687.488 rows=10 loops=1)
    Sort Key: "five".xray_alpha
    Sort Method:  quicksort  Memory: 30kB
  ->  Hash Semi Join  (cost=54300.820..250157.370 rows=55325 width=943) (actual time=11921.783..24687.308 rows=10 loops=1)
          Hash Cond: ("five".lima = "delta_echo".lima)
        ->  Append  (cost=54298.270..235569.720 rows=1106504 width=494) (actual time=3412.453..23091.938 rows=1106503 loops=1)
              ->  Subquery Scan "*SELECT* 1"  (cost=54298.270..234227.250 rows=1100622 width=496) (actual time=3412.450..20234.122 rows=1100622 loops=1)
                    ->  Hash Join  (cost=54298.270..223221.030 rows=1100622 width=496) (actual time=3412.445..17078.021 rows=1100622 loops=1)
                            Hash Cond: (three_victor.xray_hotel = delta_yankee.xray_hotel)
                          ->  Hash Join  (cost=54293.500..180567.160 rows=1100622 width=470) (actual time=3412.251..12108.676 rows=1100622 loops=1)
                                  Hash Cond: (three_victor.tango_three = quebec_seven.lima)
                                ->  Seq Scan on india three_victor  (cost=0.000..104261.220 rows=1100622 width=345) (actual time=0.015..3437.722 rows=1100622 loops=1)
                                ->  Hash  (cost=44613.780..44613.780 rows=774378 width=129) (actual time=3412.031..3412.031 rows=774603 loops=1)
                                      ->  Seq Scan on oscar quebec_seven  (cost=0.000..44613.780 rows=774378 width=129) (actual time=4.142..1964.036 rows=774603 loops=1)
                          ->  Hash  (cost=4.340..4.340 rows=34 width=30) (actual time=0.149..0.149 rows=34 loops=1)
                                ->  Seq Scan on alpha_kilo delta_yankee  (cost=0.000..4.340 rows=34 width=30) (actual time=0.017..0.095 rows=34 loops=1)
              ->  Subquery Scan "*SELECT* 2"  (cost=4.760..884.690 rows=104 width=366) (actual time=7.846..10.161 rows=104 loops=1)
                    ->  Hash Join  (cost=4.760..883.650 rows=104 width=366) (actual time=7.837..9.804 rows=104 loops=1)
                            Hash Cond: (foxtrot.xray_hotel = delta_yankee2.xray_hotel)
                          ->  Nested Loop  (cost=0.000..877.200 rows=104 width=340) (actual time=7.573..9.156 rows=104 loops=1)
                                ->  Seq Scan on four_india foxtrot  (cost=0.000..7.040 rows=104 width=216) (actual time=0.081..0.311 rows=104 loops=1)
                                ->  Index Scan using three_delta on oscar alpha_victor  (cost=0.000..8.350 rows=1 width=128) (actual time=0.077..0.078 rows=1 loops=104)
                                        Index Cond: (quebec_seven2.lima = foxtrot.tango_three)
                          ->  Hash  (cost=4.340..4.340 rows=34 width=30) (actual time=0.216..0.216 rows=34 loops=1)
                                ->  Seq Scan on alpha_kilo quebec_foxtrot  (cost=0.000..4.340 rows=34 width=30) (actual time=0.035..0.153 rows=34 loops=1)
              ->  Subquery Scan "*SELECT* 3"  (cost=4.760..457.770 rows=5778 width=141) (actual time=0.264..58.353 rows=5777 loops=1)
                    ->  Hash Join  (cost=4.760..399.990 rows=5778 width=141) (actual time=0.253..39.062 rows=5777 loops=1)
                            Hash Cond: (four_uniform.xray_hotel = delta_yankee3.xray_hotel)
                          ->  Seq Scan on whiskey four_uniform  (cost=0.000..315.780 rows=5778 width=115) (actual time=0.112..15.759 rows=5778 loops=1)
                          ->  Hash  (cost=4.340..4.340 rows=34 width=30) (actual time=0.117..0.117 rows=34 loops=1)
                                ->  Seq Scan on alpha_kilo golf  (cost=0.000..4.340 rows=34 width=30) (actual time=0.005..0.059 rows=34 loops=1)
        ->  Hash  (cost=2.430..2.430 rows=10 width=4) (actual time=0.303..0.303 rows=10 loops=1)
              ->  Subquery Scan "ANY_subquery"  (cost=0.000..2.430 rows=10 width=4) (actual time=0.092..0.284 rows=10 loops=1)
                    ->  Limit  (cost=0.000..2.330 rows=10 width=68) (actual time=0.089..0.252 rows=10 loops=1)
                          ->  Index Scan using tango_seven on zulu romeo  (cost=0.000..257535.070 rows=1106504 width=68) (actual time=0.087..0.227 rows=10 loops=1)
 Total runtime: 24687.975 ms
12
  • 1
    Could you show us the EXPLAIN ANALYZE SELECT ...? Perhaps using depesz
    – MatheusOl
    Feb 20, 2013 at 18:32
  • I would try putting subquery results in temp table, and do IN (select id from temptable). The difference is 'limit' clause which might cause optimizer to execute subselect for every single row in table1. PS this seems effectively the same as @Clodoaldo is suggesting
    – rootkit
    Feb 20, 2013 at 18:41
  • tried create temporary table aggregate_table_tmp as select ext_id from aggregate_table order by somedata limit 10 and then using it in subquery select * from table1 where id in (select ext_id from aggregate_table_tmp) order by somedata - no luck. Same 25000ms.
    – Snifff
    Feb 20, 2013 at 18:55
  • 1
    "table1 ... is a view containing three joins" - About views and joins - I noticed (on SQL server though) that changing JOIN to LEFT JOIN or removing ORDER BY can make a huge difference in performance (specifically on the view, not necessarily queries relating to it), worth playing around with it. Wouldn't "view1" be a less misleading name? Feb 20, 2013 at 19:10
  • I would like to see the definition of the view. Does it contain UNION's ? Feb 20, 2013 at 19:21

3 Answers 3

54

Seems that I have finally found a solution:

select * 
  from view1 
  where view1.id = ANY(
                       (select array(select ext_id 
                                     from aggregate_table 
                                     order by somedata limit 10)
                       )::integer[]
                      ) 
  order by view1.somedata;

After elaborating @Dukeling's idea:

I suspect where id in (1,2,3,4,5,6,7,8,9,10) can be optimised and where id in (select ...) can't, the reason being that (1,2,3,4,5,6,7,8,9,10) is a constant expression, while the select is not.

and locating these in faster query plan

Recheck Cond: (id = ANY ('{1,2,3,4,5,6,7,8,9,10}'::integer[]))
Index Cond: (id = ANY ('{1,2,3,4,5,6,7,8,9,10}'::integer[]))

this works even faster than the first query in the question, about 1.2ms, and now it uses

Recheck Cond: (id = ANY ($1))
Index Cond: (id = ANY ($1))

and bitmap scans in the plan.

4
  • 19
    Using ARRAY is a nice trick to instruct PG to use index in subquery. BTW, the above ANY clause can be simplified to this ANY(array(<your select query>))
    – Blue Smith
    Dec 6, 2015 at 19:02
  • I don't have a big data (yet) to experiment with but why select array(select ...) instead of the suggested by @BlueSmith array(select ...)? Also does ::integer[] make any difference? For example, if I have string values, do I need to cast any type for faster performance? Jun 30, 2016 at 13:45
  • So what kind of time scale delta is there with this solution? Aug 1, 2018 at 22:14
  • 24687.975 ms vs 1.2 ms. Assuming there is an index to use etc. But I believe this has been fixed in more recent PG versions and no longer an issue, query planner takes care.
    – Snifff
    Aug 5, 2018 at 14:58
3

I suspect where id in (1,2,3,4,5,6,7,8,9,10) can be optimised and where id in (select ...) can't, the reason being that (1,2,3,4,5,6,7,8,9,10) is a constant expression, while the select is not.

How about:

WITH myCTE AS
(
  SELECT ext_id
  FROM aggregate_table
  ORDER BY somedata
  LIMIT 10
)
SELECT *
FROM myCTE
LEFT JOIN table1
  ON myCTE.ext_id = table1.id
ORDER BY somedata
4
  • same as @Clodoaldo's variant, 24000 ms
    – Snifff
    Feb 20, 2013 at 18:50
  • @Snifff Changed to LEFT JOIN, may make a difference. Bottom line seems to be that PostgreSQL is doing a terrible job at optimising, I'd like to see MySQL or SQL Server's performance on the same data. Feb 20, 2013 at 18:53
  • 4
    LEFT JOIN does make a difference - time up to 65000ms :(
    – Snifff
    Feb 20, 2013 at 18:56
  • still does a sequential scan what a pity :(
    – PirateApp
    Dec 7, 2019 at 11:22
0

this is similar to the solution in LINQ:

the execution plan for concatenated queries can be complex, so

c= a.Select(...).Select( ...)

replace with

b= a.Select( ...).ToArray(); c=b.Select(...)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.