Базы данных/Лабораторная работа 3/Индексы
Содержание
Как хранятся индексы
Понятно, что проще всего найти какой-то элемент в списке, если список отсортирован. В отсортированном списке хранятся кортежи в базе данных. Но, если добавлять новые кортежи, то для хранения отсортированного списка нужно дерево. СУБД хранит данные в дереве, сортируя по первичному ключу (если он есть). Поэтому любые операции связанные с первичным ключом выполняются за столько, сколько нужно, чтобы найти его в дереве O(log n) то есть.
Больше одного такого индекса построить нельзя, потому что на листьях этого хранятся непосредственно данные, перестраивать эту структуру нельзя. Но можно построить индекс, на листьях которого будут ссылки на нужные кортежи. То есть значения поля, для которого будет строиться индекс, сортируются в выстраивается дерево. Если есть много объектов, для которых значение поля одинаковое - они просто в одном листе. Этот это дерево со ссылками будет храниться в месте отдельно от данных, но СУБД будет обращаться к нему, если можно будет узнать, где нужные данные. С хэш-индексами то же самое: строится хэш-таблица с корзинами ссылок на нужные кортежи.
Как выполняется запрос
В плане запроса написано, какие операции будут выполнны СУБД. Чем ниже в дереве операция, тем она раньше выполнится. Стоимость операций в одной ветке складываются, и самая первая строка плана - это итоговая стоимость запроса.
В процессе выполнения запроса СУБД строит временные индексы (каждый раз заново) по крайне мере hash, чтобы выполнять join, bitmap - обычно чтобы сортировать, aggregation hash - чтобы считать агрегации - эти все нельзя добавить вручную, чтобы не считалось каждый раз.
СУБД старается прежде всего выбрать из тех таблиц, где меньше данных, чтобы побольше отфильтровать сразу. Когда выбираешь из cast_info, присоединяя title, то внизу дерева будут title, затем будет присоединяться cast_info, поэтому нужно смотреть дерево снизу и искать там Sec Scan On (полный просмотр таблицы) с большими значениями cost.
Для join СУБД выстраивает хэш-индекс для внешних ключей (для обоих полей: слева и справа), в этой операции построение хэша для cast_info.movie_id - долгая операция, поэтому можно построить хэш-таблицу один раз заранее индексом using hash. Еще, так как идентификаторы - это числа, можно сделать и обычный индекс. По дереву будет искать быстро для большого количества данных, а для хэша медленее, так как надо еще дополнительно искать элемент в корзине.
Индексы не работают, когда нужно выбрать все данные. Если просто присоединить title и cast_info, то построится хэш, но для обеих таблиц сначала логично выполнится Seq Scan On, поэтому для каких-либо подзапросов, которые не связаны с основным, лучше указывать условия ограничения.
Советы по текстовым индексам
Для таблиц *_info нет большого смысла делать индекс целиком на поля info, так как это скопирует таблицу целиком (в ней практически ничего нет кроме внешнего ключа и самого info) и займет кучу места. Здесь обязательно нужно указать условия для индекса именно таким, какое будет в условии запроса.
Если нужно добавить индекс на условие типа like '%something', то хэш здесь очевидно не подойдет, так как строка до конца не определена. А для построения b-tree нужно, чтобы слова были в алфабитном порядке. Если было бы известно начало
Как еще ускорить выборку
Результаты агрегаций и сортировок можно вынести в отдельную таблицу:
create table as select ...
Это изменит план запроса, но позволит быстрее проверить другие части выборки на корректность в общем запросе.
Примеры
explain
select ts.id, ts.title, count(1) from title ts
join title te on te.episode_of_id=ts.id
where ts.id in (2300061, 1173955)
group by ts.id, ts.title;
/*
"HashAggregate (cost=103545.97..103545.98 rows=1 width=21)"
" -> Hash Join (cost=12.93..103545.96 rows=1 width=21)"
" Hash Cond: (te.episode_of_id = ts.id)"
" -> Seq Scan on title te (cost=0.00..89677.38 rows=3694838 width=4)"
" -> Hash (cost=12.90..12.90 rows=2 width=21)"
" -> Index Scan using title_pkey on title ts (cost=0.43..12.90 rows=2 width=21)"
" Index Cond: (id = ANY ('{2300061,1173955}'::integer[]))"
*/
Здесь целиком сканируется title, сами сериалы взяты по первичному ключу - это почти нисколько не стоит. Но чтобы соединить их episode_of_id нужно построить временный хэш для всех значений этого поля, а значит нужно пройтись по всем.
CREATE INDEX title_episode_of_id ON title USING HASH(episode_of_id);
/*
"HashAggregate (cost=1287.95..1287.96 rows=1 width=21)"
" -> Nested Loop (cost=5.70..1287.95 rows=1 width=21)"
" -> Index Scan using title_pkey on title ts (cost=0.43..12.90 rows=2 width=21)"
" Index Cond: (id = ANY ('{2300061,1173955}'::integer[]))"
" -> Bitmap Heap Scan on title te (cost=5.27..635.88 rows=164 width=4)"
" Recheck Cond: (episode_of_id = ts.id)"
" -> Bitmap Index Scan on title_episode_of_id (cost=0.00..5.23 rows=164 width=0)"
" Index Cond: (episode_of_id = ts.id)"
*/
Здесь уже не нужно считать хэш, а по итоговой стоимости можно предположить, сколько коллизий произошло.
Попробуем другой тип индекса:
drop index title_episode_of_id;
CREATE INDEX title_episode_of_id ON title(episode_of_id);
/*
"HashAggregate (cost=60.69..60.70 rows=1 width=21)"
" -> Nested Loop (cost=0.86..60.68 rows=1 width=21)"
" -> Index Scan using title_pkey on title ts (cost=0.43..12.90 rows=2 width=21)"
" Index Cond: (id = ANY ('{2300061,1173955}'::integer[]))"
" -> Index Only Scan using title_episode_of_id on title te (cost=0.43..22.25 rows=164 width=4)"
" Index Cond: (episode_of_id = ts.id)"
*/
Здесь СУБД уже знает, какие именно значения бывают в episode_of_id и решает, что проще в цикле состоящем из двух элементов (ид сериалов) пройтись по дереву и найти листья с соответствующими записями. Их уже не придется как-то просматривать, поэтому здесь меньше операций.
Пример оптимизации с запроса с cast_info:
explain
select ts.id, ts.title, te.title, count(1) from title ts
join title te on te.episode_of_id=ts.id
join cast_info ci on ci.movie_id=te.id
where ts.id in (2300061, 1173955)
group by ts.id, ts.title, te.title;
/*
"HashAggregate (cost=1059496.59..1059496.73 rows=14 width=38)"
" -> Hash Join (cost=60.69..1059496.45 rows=14 width=38)"
" Hash Cond: (ci.movie_id = te.id)"
" -> Seq Scan on cast_info ci (cost=0.00..868122.72 rows=51016772 width=4)"
" -> Hash (cost=60.68..60.68 rows=1 width=42)"
" -> Nested Loop (cost=0.86..60.68 rows=1 width=42)"
" -> Index Scan using title_pkey on title ts (cost=0.43..12.90 rows=2 width=21)"
" Index Cond: (id = ANY ('{2300061,1173955}'::integer[]))"
" -> Index Scan using title_episode_of_id on title te (cost=0.43..22.25 rows=164 width=25)"
" Index Cond: (episode_of_id = ts.id)"
*/
CREATE INDEX cast_info_movie_index ON cast_info USING HASH(movie_id);
/*
"HashAggregate (cost=214.46..214.60 rows=14 width=38)"
" -> Nested Loop (cost=0.86..214.32 rows=14 width=38)"
" -> Nested Loop (cost=0.86..60.68 rows=1 width=42)"
" -> Index Scan using title_pkey on title ts (cost=0.43..12.90 rows=2 width=21)"
" Index Cond: (id = ANY ('{2300061,1173955}'::integer[]))"
" -> Index Scan using title_episode_of_id on title te (cost=0.43..22.25 rows=164 width=25)"
" Index Cond: (episode_of_id = ts.id)"
" -> Index Scan using cast_info_movie_index on cast_info ci (cost=0.00..153.26 rows=38 width=4)"
" Index Cond: (movie_id = te.id)"
*/
CREATE INDEX cast_info_movie_index ON cast_info(movie_id);
/*
"HashAggregate (cost=213.30..213.44 rows=14 width=38)"
" -> Nested Loop (cost=5.61..213.16 rows=14 width=38)"
" -> Nested Loop (cost=0.86..60.68 rows=1 width=42)"
" -> Index Scan using title_pkey on title ts (cost=0.43..12.90 rows=2 width=21)"
" Index Cond: (id = ANY ('{2300061,1173955}'::integer[]))"
" -> Index Scan using title_episode_of_id on title te (cost=0.43..22.25 rows=164 width=25)"
" Index Cond: (episode_of_id = ts.id)"
" -> Bitmap Heap Scan on cast_info ci (cost=4.75..152.10 rows=38 width=4)"
" Recheck Cond: (movie_id = te.id)"
" -> Bitmap Index Scan on cast_info_movie_index (cost=0.00..4.74 rows=38 width=0)"
" Index Cond: (movie_id = te.id)"
*/
