Почему запрос с IN в СУБД PostgreSQL выполняется значительно медленнее аналогичного запроса с OR?

Question

[Leo_Eldorado]

Здравствуйте!
Имеется следующий запрос:

SELECT * from table 
WHERE column IN (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17) 
ORDER BY ID DESC LIMIT 500 OFFSET 0

Он выполняется на достаточно большой таблице размером в 25 млн. записей и время его выполнения составляет примерно 5-7 минут. Но стоит заменить IN на OR как время выполнения падает до 1 секунды. Вопрос состоит в следующем: почему так происходит и следует ли использовать данный метод для оптимизации запроса? В explain видно, что планы запросов разные и в одной статье видел совет наоборот переписывать OR на IN, поэтому и сомневаюсь, что OR будет лучшим выбором. Тем более, для ускорения этого запроса пробовал и другой подход, который заключается в создании отдельной, специализированной таблицы, к которой сначала выполняю подзапрос, после чего делаю объединение результатов этого запроса с основной таблицей с помощью INNER JOIN. Данный подход тоже дает хорошие результаты, ускоряя получение данных до 1 секунды.

Answer 1

[Melkij]

ORDER BY ID

хм.

Покажите explain (analyze,buffers) запросов. И покажите планы запросов с "ORDER BY ID + 0". И ещё

select * from pg_stats where tablename = 'table' and attname = 'column'

Я предположу что у вас вовсе не in медленный, а or ломает оценку планировщика, но в этом конкретном случае это оказывается неожиданным благом.

Comments

[Melkij]

Bavashi, нет, не странно. Нигде не сказано, что эквивалентные на вид запросы база и выполнять должна одинаково. Напротив, вполне логично допускать что планы могут быть выбраны разные.

Для определённых выводов не хватает данных.

[Leo_Eldorado]

EXPLAIN запроса с IN:

"Limit  (cost=1000.46..50764.77 rows=500 width=841) (actual time=219.720..459335.738 rows=500 loops=1)"
"  Buffers: shared hit=380808 read=2434396 dirtied=1"
"  ->  Gather Merge  (cost=1000.46..3481018.32 rows=34965 width=841) (actual time=219.716..459334.138 rows=500 loops=1)"
"        Workers Planned: 2"
"        Workers Launched: 2"
"        Buffers: shared hit=380808 read=2434396 dirtied=1"
"        ->  Parallel Index Scan Backward using entries_id on entries  (cost=0.44..3475982.46 rows=14569 width=841) (actual time=198.808..415458.848 rows=169 loops=3)"
"              Filter: (source = ANY ('{303,511,2004,2005,2006,2007,2008,2009,2010,2011,2012,2013,2016,3549,3550,3801,3802}'::bigint[]))"
"              Rows Removed by Filter: 6917953"
"              Buffers: shared hit=380808 read=2434396 dirtied=1"
"Planning Time: 2.265 ms"
"Execution Time: 459336.985 ms"

EXPLAIN запроса с OR:

"Limit  (cost=52997.07..53055.40 rows=500 width=841) (actual time=238.713..244.806 rows=500 loops=1)"
"  Buffers: shared hit=134 read=1016"
"  ->  Gather Merge  (cost=52997.07..56394.64 rows=29120 width=841) (actual time=238.711..244.776 rows=500 loops=1)"
"        Workers Planned: 2"
"        Workers Launched: 2"
"        Buffers: shared hit=134 read=1016"
"        ->  Sort  (cost=51997.04..52033.44 rows=14560 width=841) (actual time=200.064..200.072 rows=206 loops=3)"
"              Sort Key: id DESC"
"              Sort Method: quicksort  Memory: 764kB"
"              Worker 0:  Sort Method: quicksort  Memory: 607kB"
"              Worker 1:  Sort Method: quicksort  Memory: 560kB"
"              Buffers: shared hit=134 read=1016"
"              ->  Parallel Bitmap Heap Scan on entries  (cost=571.21..51560.24 rows=14560 width=841) (actual time=2.892..198.640 rows=519 loops=3)"
"                    Recheck Cond: ((source = 303) OR (source = 511) OR (source = 2004) OR (source = 2005) OR (source = 2006) OR (source = 2007) OR (source = 2008) OR (source = 2009) OR (source = 2010) OR (source = 2011) OR (source = 2012) OR (source = 2013 (...)"
"                    Heap Blocks: exact=438"
"                    Buffers: shared hit=120 read=1016"
"                    ->  BitmapOr  (cost=571.21..571.21 rows=34965 width=0) (actual time=7.460..7.460 rows=0 loops=1)"
"                          Buffers: shared hit=45 read=14"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=3.460..3.460 rows=0 loops=1)"
"                                Index Cond: (source = 303)"
"                                Buffers: shared hit=3 read=3"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.798..0.799 rows=0 loops=1)"
"                                Index Cond: (source = 511)"
"                                Buffers: shared hit=1 read=2"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.826..0.826 rows=0 loops=1)"
"                                Index Cond: (source = 2004)"
"                                Buffers: shared hit=1 read=2"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.005..0.005 rows=0 loops=1)"
"                                Index Cond: (source = 2005)"
"                                Buffers: shared hit=3"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.002..0.002 rows=0 loops=1)"
"                                Index Cond: (source = 2006)"
"                                Buffers: shared hit=3"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.523..0.523 rows=141 loops=1)"
"                                Index Cond: (source = 2007)"
"                                Buffers: shared hit=3 read=1"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.585..0.586 rows=614 loops=1)"
"                                Index Cond: (source = 2008)"
"                                Buffers: shared hit=3 read=2"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.268..0.268 rows=405 loops=1)"
"                                Index Cond: (source = 2009)"
"                                Buffers: shared hit=3 read=1"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.517..0.518 rows=224 loops=1)"
"                                Index Cond: (source = 2010)"
"                                Buffers: shared hit=3 read=1"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.014..0.014 rows=172 loops=1)"
"                                Index Cond: (source = 2011)"
"                                Buffers: shared hit=3"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.002..0.002 rows=0 loops=1)"
"                                Index Cond: (source = 2012)"
"                                Buffers: shared hit=3"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.002..0.002 rows=0 loops=1)"
"                                Index Cond: (source = 2013)"
"                                Buffers: shared hit=3"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.001..0.002 rows=0 loops=1)"
"                                Index Cond: (source = 2016)"
"                                Buffers: shared hit=3"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.437..0.437 rows=0 loops=1)"
"                                Index Cond: (source = 3549)"
"                                Buffers: shared hit=1 read=2"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.003..0.003 rows=0 loops=1)"
"                                Index Cond: (source = 3550)"
"                                Buffers: shared hit=3"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.002..0.002 rows=0 loops=1)"
"                                Index Cond: (source = 3801)"
"                                Buffers: shared hit=3"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.002..0.002 rows=0 loops=1)"
"                                Index Cond: (source = 3802)"
"                                Buffers: shared hit=3"
"Planning Time: 12.784 ms"
"Execution Time: 245.548 ms"

[Leo_Eldorado]

IN с ORDER BY ID + 0:

spoiler

"Limit  (cost=52884.63..52885.88 rows=500 width=849) (actual time=4.238..4.282 rows=500 loops=1)"
"  Buffers: shared hit=1133"
"  ->  Sort  (cost=52884.63..52972.05 rows=34965 width=849) (actual time=4.237..4.254 rows=500 loops=1)"
"        Sort Key: ((id + 0))"
"        Sort Method: top-N heapsort  Memory: 775kB"
"        Buffers: shared hit=1133"
"        ->  Bitmap Heap Scan on entries  (cost=431.45..51835.68 rows=34965 width=849) (actual time=0.415..2.476 rows=1556 loops=1)"
"              Recheck Cond: (source = ANY ('{303,511,2004,2005,2006,2007,2008,2009,2010,2011,2012,2013,2016,3549,3550,3801,3802}'::bigint[]))"
"              Heap Blocks: exact=1077"
"              Buffers: shared hit=1133"
"              ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..422.70 rows=34965 width=0) (actual time=0.307..0.307 rows=1556 loops=1)"
"                    Index Cond: (source = ANY ('{303,511,2004,2005,2006,2007,2008,2009,2010,2011,2012,2013,2016,3549,3550,3801,3802}'::bigint[]))"
"                    Buffers: shared hit=56"
"Planning Time: 0.285 ms"
"Execution Time: 5.113 ms"

OR с ORDER BY ID + 0:

spoiler

"Limit  (cost=53033.47..53091.80 rows=500 width=849) (actual time=21.660..25.380 rows=500 loops=1)"
"  Buffers: shared hit=1147"
"  ->  Gather Merge  (cost=53033.47..56431.04 rows=29120 width=849) (actual time=21.658..25.343 rows=500 loops=1)"
"        Workers Planned: 2"
"        Workers Launched: 2"
"        Buffers: shared hit=1147"
"        ->  Sort  (cost=52033.44..52069.84 rows=14560 width=849) (actual time=1.955..1.970 rows=167 loops=3)"
"              Sort Key: ((id + 0))"
"              Sort Method: top-N heapsort  Memory: 775kB"
"              Worker 0:  Sort Method: quicksort  Memory: 25kB"
"              Worker 1:  Sort Method: quicksort  Memory: 25kB"
"              Buffers: shared hit=1147"
"              ->  Parallel Bitmap Heap Scan on entries  (cost=571.21..51596.64 rows=14560 width=849) (actual time=0.195..1.147 rows=519 loops=3)"
"                    Recheck Cond: ((source = 303) OR (source = 511) OR (source = 2004) OR (source = 2005) OR (source = 2006) OR (source = 2007) OR (source = 2008) OR (source = 2009) OR (source = 2010) OR (source = 2011) OR (source = 2012) OR (source = 2013 (...)"
"                    Heap Blocks: exact=1077"
"                    Buffers: shared hit=1133"
"                    ->  BitmapOr  (cost=571.21..571.21 rows=34965 width=0) (actual time=0.397..0.397 rows=0 loops=1)"
"                          Buffers: shared hit=56"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.015..0.015 rows=0 loops=1)"
"                                Index Cond: (source = 303)"
"                                Buffers: shared hit=3"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.005..0.005 rows=0 loops=1)"
"                                Index Cond: (source = 511)"
"                                Buffers: shared hit=3"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.016..0.016 rows=0 loops=1)"
"                                Index Cond: (source = 2004)"
"                                Buffers: shared hit=3"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.002..0.002 rows=0 loops=1)"
"                                Index Cond: (source = 2005)"
"                                Buffers: shared hit=3"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.001..0.001 rows=0 loops=1)"
"                                Index Cond: (source = 2006)"
"                                Buffers: shared hit=3"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.095..0.095 rows=141 loops=1)"
"                                Index Cond: (source = 2007)"
"                                Buffers: shared hit=4"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.094..0.094 rows=614 loops=1)"
"                                Index Cond: (source = 2008)"
"                                Buffers: shared hit=5"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.028..0.029 rows=405 loops=1)"
"                                Index Cond: (source = 2009)"
"                                Buffers: shared hit=4"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.097..0.097 rows=224 loops=1)"
"                                Index Cond: (source = 2010)"
"                                Buffers: shared hit=4"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.023..0.023 rows=172 loops=1)"
"                                Index Cond: (source = 2011)"
"                                Buffers: shared hit=3"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.002..0.002 rows=0 loops=1)"
"                                Index Cond: (source = 2012)"
"                                Buffers: shared hit=3"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.002..0.002 rows=0 loops=1)"
"                                Index Cond: (source = 2013)"
"                                Buffers: shared hit=3"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.002..0.002 rows=0 loops=1)"
"                                Index Cond: (source = 2016)"
"                                Buffers: shared hit=3"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.004..0.004 rows=0 loops=1)"
"                                Index Cond: (source = 3549)"
"                                Buffers: shared hit=3"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.002..0.002 rows=0 loops=1)"
"                                Index Cond: (source = 3550)"
"                                Buffers: shared hit=3"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.002..0.002 rows=0 loops=1)"
"                                Index Cond: (source = 3801)"
"                                Buffers: shared hit=3"
"                          ->  Bitmap Index Scan on entries_source_desc  (cost=0.00..24.87 rows=2057 width=0) (actual time=0.001..0.001 rows=0 loops=1)"
"                                Index Cond: (source = 3802)"
"                                Buffers: shared hit=3"
"Planning Time: 0.527 ms"
"Execution Time: 25.876 ms"

[Melkij]

Всё как я и подумал. Хоть данные статистики и не показали.

Планировщик основываясь на MCV списке статистики решил, что требуемых source в таблице достаточно много. Потому решил исключить сортировку данных и идти по индексу по полю id, выбрасывая по пути в рантайме неподходящее. Реальное распределение данных оказалось однако не таким. И пока набрали limit записей - прошло уже много времени и random io.

Как нетрудно заметить - все три других плана запросов сортируют результат в рантайме и используют другой индекс.

Можно попробовать поднять statistic target для поля и пересобрать статистику. Вероятно вправит оценку планировщика. Или оставить order by id + 0. Это известный костыль для этой вполне известной грабли.

[Leo_Eldorado]

order by id + 0 я использовать не могу, потому что это сортировка (как я понял) не в том порядке, который мне нужен. А мне нужен именно порядок сортировки от большего к меньшему, т.е. DESC. В целом, можно ли использовать OR на "боевом" сервере или лучше воспользоваться решением с доп. таблицей, которое тоже дает хорошие результаты по времени выполнения запроса?

[Leo_Eldorado]

Статистика вот. Только я не знаю, к сожалению, как предоставить её в более удобном виде.

schemaname,tablename,attname,inherited,null_frac,avg_width,n_distinct,most_common_vals,most_common_freqs,histogram_bounds,correlation,most_common_elems,most_common_elem_freqs,elem_count_histogram
public,entries,source,f,0,8,55,"{107,102,3201,114,115,129,510,1001,509,1002,505,508,513,515,3301,2003,3302,901,902,110,305,111,301,2302,2901,109,2301,103,309,1203,2902,514,506,512,308,1202,2903,104,1204}","{0.286533,0.210833,0.1589,0.0813,0.0635333,0.0347333,0.0293667,0.0163667,0.0161667,0.0161,0.0148667,0.0109,0.00713333,0.00703333,0.00673333,0.00666667,0.0062,0.0041,0.00403333,0.0016,0.0016,0.00153333,0.0015,0.00143333,0.00106667,0.000833333,0.000833333,0.000766667,0.0007,0.0007,0.0007,0.000633333,0.000566667,0.000533333,0.0005,0.0005,0.0005,0.000366667,0.000366667}","{106,131,307,307,311,311,316,319,517,1201,1201,1201,1405,1406,1408,2904}",-0.107206,,,

[Melkij]

order by id + 0 я использовать не могу

Какой это у вас тип данных, что для него определён оператор сложения с числом, но при этом при сложении с константой нарушается сортировка?
asc/desc неважно.

А начните, как я уже сказал, с поднятия statistic target.

Переключение форматирования в psql - команда \x

[Leo_Eldorado]

Я выполняю запросы с ORDER BY ID DESC и ORDER BY ID +0 и получаю разные результаты, причем во втором случае неправильные, не такие как мне нужны. Сортировка от большего к меньшему, т.е. DESC, важна это требование ТЗ. Тип данных обычный bigint у ключа.

[Melkij]

ну так и где вы потеряли этот desc? Добавьте раз нужен.
Сортировка по bigint не изменяется относительно сортировки по bigint+0 потому что сортируются всё равно по результирующему bigint.

[Leo_Eldorado]

Поднятие statistic target должно дать ускорение варианта запроса с использованием IN? Но если вариант с OR уже работает быстро, то можно ли использовать его?

[Leo_Eldorado]

Извините, думал, что +0 это замена DESC... Я просто не знаю, что это такое, не понял Вас поэтому сразу. Действительно, добавление DESC делает результаты такими, как нужно, при этом сохраняя скорость. Т.о. первоначальный запрос IN начинает выполняться также быстро как и вариант с OR.

[Leo_Eldorado]

В чем смысл +0? Почему его добавление позволяет так сильно ускорить выполнение запроса?

[Melkij]

В чем смысл +0?

Это полностью лишённое смысла действие.
Зато об этом не знает планировщик. Как следствие не рассматривает использование индекса по этому полю как возможный план выполнения запроса.
Можно считать магией DBA. Применять как универсальное средство нельзя, только под конкретные симптомы.

что это такое

Простое сложение двух чисел.

первоначальный запрос IN начинает выполняться также быстро как и вариант с OR.

Быстрее. При том существенно, быстрее в 50 раз.

Поднятие statistic target должно дать ускорение варианта запроса с использованием IN?

Должно выправить статистику. С увеличение объёма статистики все запросы задевающее это поле будут планироваться медленнее, но давать более аккуратную оценку числа строк. Чем точнее оценка - тем точнее косты и более оптимальный план выполнения.