26.10.2015 08:57
Ivan22 8 12322 Источник
Хочу на простом примере рассказать о том, как иногда можно сильно оптимизировать вполне простые на первый взгляд запросы. Возьмем такой код, для примера на PostgreSQL 9.3, но принцип подходит ко всем субд, в которых присутствует hash join.

Задача простая — сджойнить две таблицы — одна весьма большая, другая маленькая — но джоин не простой, а золотой с OR. (Как реальный кейс — джоин таблицы проводок по счетам к самим счетам, учитывая, что в проводке два поля со счетом — для дебета и кредита.)

Готовим тестовые данные:

create table public.test1 
( id bigint,
  id2 bigint,
  value varchar(100)
);

create table public.test2
( id bigint,
  value varchar(100)
) ;

insert into public.test1 
select generate_series(1,2000000), 1, 'abcdef';

insert into public.test2 
select generate_series(1,100), 'abcdefssdf';

create index  ix_test2_id on public.test2 (id);
/* наличие индекса на маленькой таблице принципиально ничего не меняет, но он тут в реальности наверняка будет, так что пусть и в тесте пусть будет.  */

А вот и наш запрос в первоначальном виде, с условием по or.

select * 
from public.test1 t1
inner join public.test2 t2 on t1.id = t2.id or t1.id2 = t2.id;

Джоин с таким условием получит гарантированный nested loop. План таков:


"Nested Loop  (cost=0.00..3532741.25 rows=2000099 width=42) (actual time=0.043..61627.189 rows=2000099 loops=1)"
"  Join Filter: ((t1.id = t2.id) OR (t1.id2 = t2.id))"
"  Rows Removed by Join Filter: 197999901"
"  ->  Seq Scan on test1 t1  (cost=0.00..32739.00 rows=2000000 width=23) (actual time=0.010..385.658 rows=2000000 loops=1)"
"  ->  Materialize  (cost=0.00..2.50 rows=100 width=19) (actual time=0.000..0.007 rows=100 loops=2000000)"
"        ->  Seq Scan on test2 t2  (cost=0.00..2.00 rows=100 width=19) (actual time=0.005..0.018 rows=100 loops=1)"
"Total runtime: 61717.751 ms"

Обратите внимание на два миллиона циклов прохода по маленькой таблице. Это главный минус nested loop. Даже если бы тут было два миллиона поисков по индексу — все равно плохо.

Что же делать?

Нам бы помог hash join — хэш маленькой таблицы, влезающий в память + один проход по большой — идеально. Но с OR в условии его не получить. Выход есть!

Сделаем два джоина на разные поля и вынесем OR в фильтр:

select * 
from public.test1 t1
left join public.test2 t2 on t1.id = t2.id 
left join public.test2 t3 on t1.id2 = t3.id
where t2.id is not null or t3.id is not null;

План стал гораздо быстрее. 5кб хэш таблица — то, что надо: даже с учетом того, что джоинов два, выигрыш в десятки раз!

"Hash Left Join  (cost=6.50..67746.50 rows=2000000 width=61) (actual time=0.124..2230.636 rows=2000000 loops=1)"
"  Hash Cond: (t1.id2 = t3.id)"
"  Filter: ((t2.id IS NOT NULL) OR (t3.id IS NOT NULL))"
"  ->  Hash Left Join  (cost=3.25..40243.25 rows=2000000 width=42) (actual time=0.073..1065.822 rows=2000000 loops=1)"
"        Hash Cond: (t1.id = t2.id)"
"        ->  Seq Scan on test1 t1  (cost=0.00..32739.00 rows=2000000 width=23) (actual time=0.012..338.759 rows=2000000 loops=1)"
"        ->  Hash  (cost=2.00..2.00 rows=100 width=19) (actual time=0.041..0.041 rows=100 loops=1)"
"              Buckets: 1024  Batches: 1  Memory Usage: 5kB"
"              ->  Seq Scan on test2 t2  (cost=0.00..2.00 rows=100 width=19) (actual time=0.004..0.015 rows=100 loops=1)"
"  ->  Hash  (cost=2.00..2.00 rows=100 width=19) (actual time=0.039..0.039 rows=100 loops=1)"
"        Buckets: 1024  Batches: 1  Memory Usage: 5kB"
"        ->  Seq Scan on test2 t3  (cost=0.00..2.00 rows=100 width=19) (actual time=0.004..0.016 rows=100 loops=1)"
"Total runtime: 2318.009 ms"

Спасибо за внимание.

Комментарии (8)


  1. zuborg
    26.10.2015 15:16
    #8627275

    А если можно обойтись без джойна, тогда ещё проще:
    select * from public.test1
    where id in (select id from public.test2) or id2 in (select id from public.test2);

    Seq Scan on test1 t1 (cost=4.50..42743.50 rows=1500000 width=23) (actual time=0.086..589.390 rows=2000000 loops=1)
    Filter: ((hashed SubPlan 1) OR (hashed SubPlan 2))
    SubPlan 1
    -> Seq Scan on test2 (cost=0.00..2.00 rows=100 width=8) (actual time=0.006..0.023 rows=100 loops=1)
    SubPlan 2
    -> Seq Scan on test2 test2_1 (cost=0.00..2.00 rows=100 width=8) (actual time=0.004..0.024 rows=100 loops=1)
    Planning time: 0.120 ms
    Execution time: 673.445 ms


    А вообще данные для примера не самые удачные — результат содержит все 2м строк, т.к. всегда верно t1.id2=t2.id


    1. zuborg
      26.10.2015 15:39
      #8627301
      +2

      Для разреженных данных из

      => insert into public.test1
      select generate_series(1,2000000), (random()*1000000)::bigint, 'abcdef';

      и при наличии индексов на id и id2 в test1 исходный запрос существенно быстрее «оптимизированного»:

      => explain analyze select * from public.test1 t1 inner join public.test2 t2 on t1.id = t2.id or t1.id2 = t2.id;
      QUERY PLAN
      — Nested Loop (cost=8.89..2485.66 rows=408 width=42) (actual time=0.031..0.902 rows=306 loops=1)
      -> Seq Scan on test2 t2 (cost=0.00..2.00 rows=100 width=19) (actual time=0.008..0.021 rows=100 loops=1)
      -> Bitmap Heap Scan on test1 t1 (cost=8.89..24.80 rows=4 width=23) (actual time=0.005..0.007 rows=3 loops=100)
      Recheck Cond: ((id = t2.id) OR (id2 = t2.id))
      Heap Blocks: exact=306
      -> BitmapOr (cost=8.89..8.89 rows=4 width=0) (actual time=0.004..0.004 rows=0 loops=100)
      -> Bitmap Index Scan on ix_test_id (cost=0.00..4.44 rows=1 width=0) (actual time=0.002..0.002 rows=1 loops=100)
      Index Cond: (id = t2.id)
      -> Bitmap Index Scan on ix_test_id2 (cost=0.00..4.45 rows=3 width=0) (actual time=0.002..0.002 rows=2 loops=100)
      Index Cond: (id2 = t2.id)
      Planning time: 0.108 ms
      Execution time: 0.943 ms

      => explain analyze select * from public.test1 t1 left join public.test2 t2 on t1.id = t2.id
      left join public.test2 t3 on t1.id2 = t3.id
      where t2.id is not null or t3.id is not null;
      QUERY PLAN
      — Hash Left Join (cost=6.50..60487.58 rows=2000000 width=61) (actual time=46.352..756.604 rows=306 loops=1)
      Hash Cond: (t1.id2 = t3.id)
      Filter: ((t2.id IS NOT NULL) OR (t3.id IS NOT NULL))
      Rows Removed by Filter: 1999694
      -> Hash Left Join (cost=3.25..52981.25 rows=2000000 width=42) (actual time=46.316..551.457 rows=2000000 loops=1)
      Hash Cond: (t1.id = t2.id)
      -> Seq Scan on test1 t1 (cost=0.00..45477.00 rows=2000000 width=23) (actual time=46.262..218.580 rows=2000000 loops=1)
      -> Hash (cost=2.00..2.00 rows=100 width=19) (actual time=0.036..0.036 rows=100 loops=1)
      Buckets: 1024 Batches: 1 Memory Usage: 5kB
      -> Seq Scan on test2 t2 (cost=0.00..2.00 rows=100 width=19) (actual time=0.004..0.013 rows=100 loops=1)
      -> Hash (cost=2.00..2.00 rows=100 width=19) (actual time=0.032..0.032 rows=100 loops=1)
      Buckets: 1024 Batches: 1 Memory Usage: 5kB
      -> Seq Scan on test2 t3 (cost=0.00..2.00 rows=100 width=19) (actual time=0.003..0.011 rows=100 loops=1)
      Planning time: 0.323 ms
      Execution time: 756.671 ms


  1. itcoder
    26.10.2015 15:59
    #8627353
    +5

    Ждал развязки, но статья как то кончилась неожиданно.


    1. Stepanow
      26.10.2015 16:14
      #8627391

      Мне наоборот показалось что кончилась ожидаемо


  1. Ivan22
    27.10.2015 10:29
    #8628631

    Да. Тестовые данные надо подправить. Возьмем так, чтобы id был адекватным: 

    insert into public.test1 
select generate_series(1,1000000), 1000000-generate_series(1,1000000), 'abcdef';

/*Плюс пару индексов:*/
create index  ix_test1_id2 on public.test1 (id2);
create index  ix_test1_id on public.test1 (id);


    — 1. Запрос из первого коментария у меня работал быстро, но ровно до момента когда я не вставил в public.test2
    40 тысяч записей. Он вообще перестал выполнятся!!! На 30к за полсекунды, а на 40к — стоп. Ни разу не отработал даже за 10 минут, сколько ни запускал.
    Его план ни о чем мне не говорит, что такое Filter: ((hashed SubPlan 1) OR (hashed SubPlan 2)) ???
    Это видимо тоже какие-то хэш таблцицы в памяти, но явно есть отличие от хэш джоина, возможно нет spill на диск?? Кто просветит механику?
    — 2. Запрос из второго коментария конечно интереснее.
    Он действительно может быть быстрее, за счет лукапа по индексам в большую таблицу, но
    1.) Нужны 2 больших индекса, хотя они скорее всего там и так возможно будут, но если их нет — вариантов нет.
    2.) Все таки начиная с какого-то объема таблицы 2 — у меня уже с 200к, запрос с хэш джоином обгоняет его.
    Всеже рандомные чтения в разы медленнее секвенс скана. Ну а если вообще планируется выбрать всю большую таблицу — без вариантов лукапить её по одной строке — плохо.
    3.) В этом запросе inner join — он позволяет при Nested Loop менять входные таблицы. Если заменить джоин на LEFT OUTER JOIN —
    nested loop не сможет поменять входные таблицы местами — и план будет такой как в моем пример — медленный. Тут тоже только 2 hash join-а помогут, в этом случае left работает так же как и иннер.

    А так естественно нужно просто знать все варианты и использовать по месту нужный!!!


  1. xtender
    27.10.2015 14:24
    #8629359

    В oracle еще срабатывает такой подход:

    select/*+ leading(test2 test1) use_hash(test1) */ *
from test1 t1,test2 t2
where t1.id*0 = t2.id*0 -- форсируем hash join "все-ко-всему"
and (t1.id = t2.id or t1.id2 = t2.id) -- остальные условия оставляем в фильтре

    ps. только для not null полей


    1. AHDPEu
      28.10.2015 19:04
      #8631839

      И без хинтов hash join будет
      В вашем примере вернёт только те строки, id которых есть в test2
      Я полагаю, что нужно вернуть все строки test1


      1. AHDPEu
        28.10.2015 19:13
        #8631863

        Проглядел inner join у автора. Две нижние строчки моего комментария вычёркиваем