Производительность оператора IN в PostgreSQL (и вообще)

Question

Я знаю, что, возможно, об этом уже спрашивали, но я не могу найти его с помощью поиска SO.

Допустим, у меня есть TABLE1 и TABLE2, как мне ожидать выполнения запроса, такого как этот:

SELECT * FROM TABLE1 WHERE id IN SUBQUERY_ON_TABLE2;

уменьшаться по мере роста числа строк в TABLE1 и TABLE2, а id является первичным ключом в TABLE1.

Да, я знаю, что использование IN - такая ошибка n00b, но TABLE2 имеет общее отношение (общее отношение django) ко многим другим таблицам, поэтому я не могу придумать другой способ фильтрации данных. При каком (приблизительном) количестве строк в таблицах TABLE1 и TABLE2 следует ожидать проблем с производительностью из-за этого? Будет ли производительность снижаться линейно, экспоненциально и т. Д. В зависимости от количества строк?

Answer 1

Когда количество записей, возвращаемых подзапросом, мало, а итоговое количество строк, возвращаемых основным запросом, также мало, вы просто получите быстрый поиск индекса по каждой. По мере того, как процент возвращаемых данных увеличивается, в конечном итоге каждый из двух переключится на использование последовательного сканирования вместо индексированного, чтобы захватить всю таблицу одним глотком, а не объединить ее. Это не просто падение производительности, которое является либо линейным, либо экспоненциальным; Существуют значительные разрывы по мере изменения типа плана. И количество строк, в которых это происходит, зависит от размера таблиц, поэтому никаких полезных правил для вас там тоже нет. Вы должны построить симуляцию, как я делаю ниже, и посмотреть, что происходит с вашим собственным набором данных, чтобы понять, как выглядит кривая.

Вот пример того, как это работает, используя базу данных PostgreSQL 9.0, загруженную с базой данных Dell Store 2 . Когда подзапрос возвращает 1000 строк, он выполняет полное сканирование основной таблицы. И как только подзапрос рассматривает 10 000 записей, это также превращается в полное сканирование таблицы. Каждый из них запускался дважды, поэтому вы видите производительность в кэше. Как изменения производительности в зависимости от состояния в кэше и в кэше - это отдельная тема:

dellstore2=# EXPLAIN ANALYZE SELECT * FROM customers WHERE customerid IN 
  (SELECT customerid FROM orders WHERE orderid<2);
Nested Loop  (cost=8.27..16.56 rows=1 width=268) (actual time=0.051..0.060 rows=1 loops=1)
  ->  HashAggregate  (cost=8.27..8.28 rows=1 width=4) (actual time=0.028..0.030 rows=1 loops=1)
        ->  Index Scan using orders_pkey on orders  (cost=0.00..8.27 rows=1 width=4) (actual time=0.011..0.015 rows=1 loops=1)
              Index Cond: (orderid < 2)
  ->  Index Scan using customers_pkey on customers  (cost=0.00..8.27 rows=1 width=268) (actual time=0.013..0.016 rows=1 loops=1)
        Index Cond: (customers.customerid = orders.customerid)
Total runtime: 0.191 ms

dellstore2=# EXPLAIN ANALYZE SELECT * FROM customers WHERE customerid IN 
  (SELECT customerid FROM orders WHERE orderid<100);
Nested Loop  (cost=10.25..443.14 rows=100 width=268) (actual time=0.488..2.591 rows=98 loops=1)
  ->  HashAggregate  (cost=10.25..11.00 rows=75 width=4) (actual time=0.464..0.661 rows=98 loops=1)
        ->  Index Scan using orders_pkey on orders  (cost=0.00..10.00 rows=100 width=4) (actual time=0.019..0.218 rows=99 loops=1)
              Index Cond: (orderid < 100)
  ->  Index Scan using customers_pkey on customers  (cost=0.00..5.75 rows=1 width=268) (actual time=0.009..0.011 rows=1 loops=98)
        Index Cond: (customers.customerid = orders.customerid)
Total runtime: 2.868 ms

dellstore2=# EXPLAIN ANALYZE SELECT * FROM customers WHERE customerid IN 
  (SELECT customerid FROM orders WHERE orderid<1000);
Hash Semi Join  (cost=54.25..800.13 rows=1000 width=268) (actual time=4.574..80.319 rows=978 loops=1)
  Hash Cond: (customers.customerid = orders.customerid)
  ->  Seq Scan on customers  (cost=0.00..676.00 rows=20000 width=268) (actual time=0.007..33.665 rows=20000 loops=1)
  ->  Hash  (cost=41.75..41.75 rows=1000 width=4) (actual time=4.502..4.502 rows=999 loops=1)
        Buckets: 1024  Batches: 1  Memory Usage: 24kB
        ->  Index Scan using orders_pkey on orders  (cost=0.00..41.75 rows=1000 width=4) (actual time=0.056..2.487 rows=999 loops=1)
              Index Cond: (orderid < 1000)
Total runtime: 82.024 ms

dellstore2=# EXPLAIN ANALYZE SELECT * FROM customers WHERE customerid IN 
  (SELECT customerid FROM orders WHERE orderid<10000);
Hash Join  (cost=443.68..1444.68 rows=8996 width=268) (actual time=79.576..157.159 rows=7895 loops=1)
  Hash Cond: (customers.customerid = orders.customerid)
  ->  Seq Scan on customers  (cost=0.00..676.00 rows=20000 width=268) (actual time=0.007..27.085 rows=20000 loops=1)
  ->  Hash  (cost=349.97..349.97 rows=7497 width=4) (actual time=79.532..79.532 rows=7895 loops=1)
        Buckets: 1024  Batches: 1  Memory Usage: 186kB
        ->  HashAggregate  (cost=275.00..349.97 rows=7497 width=4) (actual time=45.130..62.227 rows=7895 loops=1)
              ->  Seq Scan on orders  (cost=0.00..250.00 rows=10000 width=4) (actual time=0.008..20.979 rows=9999 loops=1)
                    Filter: (orderid < 10000)
Total runtime: 167.882 ms