DOC.PROTOTYPES.RU

Главная > Базы данных > PostgreSQL > Индексы >

Композитные (составные) индексы

В качестве затравки

Каждый из нас, наверняка, сталкивался с ситуацией, когда имея два поля в условии запроса и два индекса по этим полям выборка производится довольно медленно:

SQL код (1)
devel=> EXPLAIN ANALYSE
    SELECT * FROM my_table WHERE field1 = 1 AND field2 = 2 ORDER BY id LIMIT 100;
                QUERY PLAN                                                                     
------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..159.96 rows=100 width=1341) (actual time=0.568..25.499 rows=100 loops=1)
   ->  Index Scan using my_table_pkey on my_table (cost=0.00..44554.02 rows=27853 width=1341) (actual time=0.565..25.250 rows=100 loops=1)
         Filter: ((field1 = 1) AND (field2 = 2))
 Total runtime: 25.672 ms
(4 rows)

что несколько странно, так как индексы на field1 и field2 у нас в наличии, а id так вообще первичный ключ, но даже если без сортировки, что все равно не все проходит по индексу:

SQL код (2)
devel=> EXPLAIN ANALYSE
    SELECT * FROM my_table WHERE field1 = 1 AND field2 = 2 LIMIT 100;
                QUERY PLAN                                                                
------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..57.16 rows=100 width=1341) (actual time=0.492..1.342 rows=100 loops=1)
   ->  Index Scan using field1_idx on my_table (cost=0.00..15922.04 rows=27853 width=1341) (actual time=0.488..1.082 rows=100 loops=1)
         Index Cond: (field1 = 1)
         Filter: (field2 = 2)
 Total runtime: 1.514 ms
(5 rows)

легче, но не намного, так как фильтр по field2 в данном примере накладывается всего на 28 тысяч записей, да сортировка таки нужна :-(

Для этого существуют композитные индексы, которые, собственно, позволяют использовать их для множественных условий:

SQL код (3)
devel=> CREATE INDEX ci_f1_f2 ON my_table USING btree("field1", "field2");
CREATE INDEX

devel=> EXPLAIN ANALYSE
    SELECT * FROM my_table WHERE field1 = 1 AND field2 = 2 LIMIT 100;
                                                             QUERY PLAN                                                              
-------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..52.79 rows=100 width=1341) (actual time=0.101..0.620 rows=100 loops=1)
   ->  Index Scan using ci_f1_f2 on my_table (cost=0.00..14703.13 rows=27853 width=1341) (actual time=0.098..0.379 rows=100 loops=1)
         Index Cond: ((field1 = 1) AND (field2 = 2))
 Total runtime: 0.775 ms
(4 rows)

Увеличение производительности видно даже на таком небольшом количестве записей, но при добавлении сортировки в запрос, легче совсем не становится:

SQL код (4)
devel=> EXPLAIN ANALYSE
    SELECT * FROM my_table WHERE field1 = 1 AND field2 = 2 ORDER BY id LIMIT 100;
                QUERY PLAN                                                                     
------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..159.96 rows=100 width=1341) (actual time=0.568..25.499 rows=100 loops=1)
   ->  Index Scan using my_table_pkey on my_table (cost=0.00..44554.02 rows=27853 width=1341) (actual time=0.565..25.250 rows=100 loops=1)
         Filter: ((field1 = 1) AND (field2 = 2))
 Total runtime: 25.672 ms
(4 rows)

все потому, что сортировка так же является одним из условий запроса, соответственно поле сортировки так же нужно добавлять в композитный индекс:

SQL код (5)
vision=> CREATE INDEX comp_index ON my_table USING btree("field1", "field2", "id");
CREATE INDEX

vision=> EXPLAIN ANALYSE
    SELECT * FROM my_table WHERE field1 = 1 AND field2 = 2 ORDER BY id LIMIT 100;
                                                             QUERY PLAN                                                              
-------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..52.82 rows=100 width=1341) (actual time=0.244..0.809 rows=100 loops=1)
   ->  Index Scan using comp_index on my_table (cost=0.00..14711.15 rows=27854 width=1341) (actual time=0.240..0.568 rows=100 loops=1)
         Index Cond: ((field1 = 1) AND (field2 = 2))
 Total runtime: 0.968 ms
(4 rows)

вуаля!

Что интересно, при этом анализатор не говорит, что сортировка производится тоже по индексу, но при этом сортирует именно по нему.

Теперь можно поговорить уже и про теорию, что же это за композитные индексы такие...

Как это работает

Композитный индекс можно представить в виде такой схемы:

Схема композитного индекса

Как видно из схемы, что для каждого из элементов на следующем уровне формируется частичный индекс в его (элемента) пределах. Отсюда становится понятным, что порядок полей в композитном индексе имеет очень большое значение.

Так, в предыдущем примере (SQL код (5)) мы указали последовательность полей как (field1, field2, id), можно сравнить, что будет происходить, если мы поменяем порядок полей как (id, field1, field2):

SQL код (6)
devel=> CREATE INDEX comp_index ON my_table USING btree("id", "field1", "field2");
CREATE INDEX
devel=> EXPLAIN ANALYSE SELECT * FROM my_table WHERE field1 = 1 AND field2 = 2 ORDER BY id LIMIT 100;
                                                             QUERY PLAN                                                              
-------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..62.09 rows=100 width=1341) (actual time=0.180..2.819 rows=100 loops=1)
   ->  Index Scan using comp_index on my_table (cost=0.00..17295.78 rows=27854 width=1341) (actual time=0.178..2.571 rows=100 loops=1)
         Index Cond: ((field1 = 1) AND (field2 = 2))
 Total runtime: 2.986 ms
(4 rows)

Как видно, скорость упала в разы. Рассмотрим как производится выборка по индексу в обоих случаях:

(field1, field2, id)

Схема правильной работы композитного индекса
(id, field1, field2)

Схема неправильной работы композитного индекса

Теперь понятно откуда такие задержки. По сути получается все равно фильтрация, но по индексу, так как данные для этого присутствуют. Так же видно, что уникальное поле в композитном индексе имеет смысл ставить только в конце, так как на следующих уровнях индекса буджет находится всего по одному элементу.

Немного усложним задачу и уберем LIMIT:

SQL код (7)
devel=> CREATE INDEX comp_index ON my_table USING btree("field1", "field2", "id");
CREATE INDEX
devel=> EXPLAIN ANALYSE SELECT * FROM my_table WHERE field1 = 1 AND field2 = 2 ORDER BY id;
                                                            QUERY PLAN                                                            
----------------------------------------------------------------------------------------------------------------------------------
 Index Scan using comp_index on my_table (cost=0.00..14690.15 rows=27693 width=1342) (actual time=0.160..64.130 rows=25882 loops=1)
   Index Cond: ((field1 = 1) AND (field2 = 2))
 Total runtime: 95.499 ms
(3 rows)
SQL код (8)
devel=> CREATE INDEX comp_index ON my_table USING btree("id", "field1", "field2");
CREATE INDEX
devel=> EXPLAIN ANALYSE SELECT * FROM my_table WHERE field1 = 1 AND field2 = 2 ORDER BY id;
                                                            QUERY PLAN                                                            
----------------------------------------------------------------------------------------------------------------------------------
 Index Scan using comp_index on my_table (cost=0.00..17211.42 rows=27693 width=1342) (actual time=0.130..81.112 rows=25882 loops=1)
   Index Cond: ((field1 = 1) AND (field2 = 2))
 Total runtime: 112.915 ms
(3 rows)

Как видно, при больших объемах, разница незначительная, так как все начинает упираться в чтение строк с диска.

Как это использовать

Итак, как работают композитные индексы, понятно. Остается вопрос, как правильно их использовать.

Первое на что хотел бы обратить внимание, опять же порядок. Понятно, что в первую очередь в композитном индексе нужно указывать поля из условия WHERE, а во второй - из сортировки ORDER BY. Причем, если порядок полей из сортировки понятен - ровно такой, какой указываем в сортировке, то порядок полей из условия WHERE не совсем однозначен.

По сути, для получения данных порядок полей в композитном индексе не имеет значения, но для планировщика запросов очень даже имеет, так например:

SQL код (9)
devel=> CREATE INDEX field1_idx ON my_table USING btree("field1");
CREATE INDEX
devel=> CREATE INDEX comp_index ON my_table USING btree("field2", "field1", "id");
CREATE INDEX
devel=> EXPLAIN ANALYSE SELECT * FROM my_table WHERE field1 = 1 AND field2 = 2 ORDER BY id;
                                                                 QUERY PLAN                                                                  
---------------------------------------------------------------------------------------------------------------------------------------------
 Sort  (cost=17661.40..17730.64 rows=27695 width=1342) (actual time=156.753..193.793 rows=25882 loops=1)
   Sort Key: id
   Sort Method:  quicksort  Memory: 36949kB
   ->  Index Scan using field1_idx on my_table (cost=0.00..15617.88 rows=27695 width=1342) (actual time=0.105..70.054 rows=25882 loops=1)
         Index Cond: (field1 = 1)
         Filter: (field2 = 2)
 Total runtime: 228.808 ms
(7 rows)

Казалось бы, совершенно неожиданное поведение, у нас же есть специально заточненный индекс для этого запроса, а он, почему-то использует другой индекс, причем, если мы не создадим индекс field1_idx, то все становится в норму:

SQL код (10)
devel=> CREATE INDEX comp_index ON my_table USING btree("field2", "field1", "id");
CREATE INDEX
devel=> EXPLAIN ANALYSE SELECT * FROM my_table WHERE field1 = 1 AND field2 = 2 ORDER BY id;
                                                            QUERY PLAN                                                            
----------------------------------------------------------------------------------------------------------------------------------
 Index Scan using comp_index on my_table (cost=0.00..18985.98 rows=27695 width=1342) (actual time=0.070..64.735 rows=25882 loops=1)
   Index Cond: ((field1 = 1) AND (field2 = 2))
 Total runtime: 97.229 ms
(3 rows)

Все очень просто. Вариантов значений field1 - 1269, а field2 всего 23:

SQL код (11)
devel=> EXPLAIN ANALYSE SELECT field2 FROM my_table GROUP BY field2;
                                                         QUERY PLAN                                                         
----------------------------------------------------------------------------------------------------------------------------
 HashAggregate  (cost=42596.67..42596.91 rows=24 width=2) (actual time=656.608..656.640 rows=23 loops=1)
   ->  Seq Scan on my_table (cost=0.00..42070.74 rows=210374 width=2) (actual time=0.005..314.775 rows=210375 loops=1)
 Total runtime: 656.753 ms
(3 rows)

devel=> EXPLAIN ANALYSE SELECT field1 FROM my_table GROUP BY field1;
                                                         QUERY PLAN                                                         
----------------------------------------------------------------------------------------------------------------------------
 HashAggregate  (cost=42596.67..42609.35 rows=1268 width=4) (actual time=695.617..697.530 rows=1269 loops=1)
   ->  Seq Scan on my_table (cost=0.00..42070.74 rows=210374 width=4) (actual time=0.004..313.789 rows=210375 loops=1)
 Total runtime: 699.078 ms
(3 rows)

В итоге планировщик принимает относительно правильное решение, отфильтровывать сначала 1/1269 часть данных, чем 1/23.

Отсюда правило: порядок полей из условия WHERE зависит от того, сколько вариантов значений может принимать поле, чем больше - тем первее.

Как это можно оптимизировать

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

Что бы уменьшить объем можно сделать разделенный композитный индекс. Так например:

Есть каталог новостей, новость привязана к рубрике, у новости есть статус (черновик, показывать в рубрике, архивная новость):

SQL код (12)
devel=> SELECT * FROM news WHERE rubric_id = [id рубрики] AND status = [статус новости] ORDER BY ndate DESC LIMIT 20;

Соответственно можно создать композитный индекс:

SQL код (13)
devel=> CREATE INDEX comp_index ON news USUNG btree("rubric_id", "status", "ndate");

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

SQL код (14)
devel=> CREATE INDEX comp_index ON news USUNG btree("rubric_id", "ndate") WHERE status = 1;

Что значительно облегчит индекс. Причем поле status вообще убирается из индекса, так как фильтрация по этому полю будет производится на уровне разделителя индекса, правда, если нам понадобится несколько статусов, то это поле все же придется добавить в индекс.

Итоги

В итоге получились следующие заключения для композитный индексов:

P.S.

Кстати композитные бывают не только индексы и сортировки, а еще и условия. Так например запрос:

SQL код (15)
SELECT i.*
    FROM items AS i
        WHERE
            i.rubric_id = 1 AND
            ( i.rating, i.date ) < ( SELECT n.rating, n.date FROM items AS n WHERE id = 1234 )
        ORDER BY i.rating DESC, i.date DESC
        LIMIT 10;

Выберет следующие 10 записей после записи с id = 1234 в соответсвии с композитным порядком сортировки. Причем даже если у последующих записей поле rating такое же, но дата меньше, они будут все равно выбраны, так как у нас условие ( i.rating, i.date ) < ... композитное. Правда, при разнонаправленной сортировке такой фокус не пройдет.

Сергей Томулевич aka Phoinix (02.03.2011 г.)
Valid HTML 4.01 Transitional
Copyright © 2011 Сергей Томулевич