Индексы в PostgreSQL

Thank you for reading this post, don't forget to subscribe!

Предназначение индексов

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

Если про­ве­сти ана­ло­гию меж­ду базой дан­ных и кни­гой, индек­са­ми мож­но счи­тать оглав­ле­ние кни­ги и пред­мет­ный ука­за­тель. Дей­стви­тель­но, если бы у нас не было таких «индек­сов», для поис­ка кон­крет­ной гла­вы или для поис­ка опре­де­ле­ния како­го-то поня­тия при­шлось бы листать и читать всю кни­гу цели­ком, пока не най­дем то, что нуж­но. Имея оглав­ле­ние и пред­мет­ный ука­за­тель, нам нуж­но про­смот­реть суще­ствен­но мень­ший объ­ем дан­ных, после чего мы точ­но узна­ем номер стра­ни­цы кни­ги, на кото­рой нахо­дит­ся то, что мы ищем. Индек­сы в базах дан­ных по сути устро­е­ны так же, как оглав­ле­ние или как пред­мет­ный ука­за­тель книги.

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

В каче­стве при­ме­ра рас­смот­рим зада­чу поис­ка в спис­ке чисел. Исполь­зуя пере­бор эле­мен­тов спис­ка, в худ­шем слу­чае, нам при­дет­ся про­смот­реть спи­сок цели­ком. Алго­рит­ми­че­ская слож­ность тако­го мето­да — O(n). Но если мы будем хра­нить наши чис­ла осо­бым обра­зом — отсор­ти­ро­ван­ны­ми по воз­рас­та­нию или по убы­ва­нию — смо­жем исполь­зо­вать алго­ритм бинар­но­го поиска.

2 4 5 10 23 34 38 58 112 114 115 110 123 134 138 158 180

Допу­стим, необ­хо­ди­мо опре­де­лить, содер­жит ли этот отсор­ти­ро­ван­ный спи­сок чис­ло 158. Для этого:

  • Смот­рим на чис­ло в сере­дине спис­ка — 114. Наш спи­сок отсор­ти­ро­ван по воз­рас­та­нию, и мы ищем чис­ло 158 > 114. Зна­чит, левую поло­ви­ну спис­ка до чис­ла 114 мы можем отбро­сить: в ней гаран­ти­ро­ван­но не может быть иско­мо­го элемента. 
    • 2 4 5 10 23 34 38 58 112 114 115 110 123 134 138 158 180
  • Теперь дела­ем то же самое для пра­вой поло­ви­ны спис­ка. В сере­дине у нее чис­ло 134, зна­чит, мы сно­ва можем отбро­сить эле­мен­ты левее. 
    • 2 4 5 10 23 34 38 58 112 114 115 110 123 134 138 158 180
  • Дела­ем то же самое для эле­мен­тов пра­вее 134. В сере­дине у них чис­ло 158 — иско­мый эле­мент. Поиск закончен.

В ито­ге метод бинар­но­го поис­ка дал нам резуль­тат все­го за три шага. При пол­ном пере­бо­ре с нача­ла спис­ка нам потре­бо­ва­лось бы 16 шагов. Бинар­ный поиск име­ет алго­рит­ми­че­скую слож­ность O(log(n)). Исполь­зуя фор­му­лы алго­рит­ми­че­ской слож­но­сти O(n) и O(log(n)), мы можем оце­нить, как будет менять­ся при­бли­зи­тель­ное коли­че­ство опе­ра­ций при поис­ке раз­ны­ми спо­со­ба­ми с ростом объ­е­ма данных:

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

Исполь­зо­ва­ние индек­сов в базе дан­ных дает ана­ло­гич­ный резуль­тат. Прин­цип рабо­ты одно­го из важ­ней­ших индек­сов в базе дан­ных (индекс на осно­ве B-дере­ва) осно­ван имен­но на рас­смот­рен­ном нами выше прин­ци­пе — воз­мож­но­сти хра­нить дан­ные в отсор­ти­ро­ван­ном виде.

Индексы в PostgreSQL

В базах дан­ных, таких как PostgreSQL, индекс фор­ми­ру­ет­ся из зна­че­ний одно­го или несколь­ких столб­цов таб­ли­цы и ука­за­те­лей на стро­ки этой таблицы.

Рас­смот­рим запрос:

SELECT * FROM table_name WHERE P(column_name) = 1

Здесь выра­же­ние P(column_name) = 1 озна­ча­ет, что зна­че­ние в колон­ке column_name удо­вле­тво­ря­ет неко­то­ро­му усло­вию (пре­ди­ка­ту) P.

В отсут­ствии индек­са для колон­ки column_name, PostgreSQL для выпол­не­ния это­го запро­са был бы вынуж­ден про­смот­реть таб­ли­цу table_name цели­ком, вычис­ляя для каж­дой стро­ки зна­че­ние пре­ди­ка­та P и, если зна­че­ние истин­но, добав­лял бы стро­ку к резуль­та­там запроса.

Имея индекс для колон­ки column_name, PostgreSQL может быст­ро, не про­смат­ри­вая таб­ли­цу цели­ком, полу­чить из индек­са ука­за­те­ли на стро­ки таб­ли­цы, кото­рые удо­вле­тво­ря­ют усло­вию P, и затем уже по этим ука­за­те­лям про­чи­тать дан­ные из таб­ли­цы и сфор­ми­ро­вать резуль­тат. Это ана­ло­гич­но тому, как мы, вме­сто того что­бы про­смат­ри­вать всю кни­гу цели­ком, смот­рим толь­ко ее оглав­ле­ние, чита­ем номе­ра стра­ниц, соот­вет­ству­ю­щие инте­ре­су­ю­щим нам гла­вам, а затем пере­хо­дим на эти страницы.

Пре­ди­кат P может вычис­лять­ся от зна­че­ния несколь­ких коло­нок. В этом слу­чае для уско­ре­ния запро­са исполь­зу­ет­ся индекс, постро­ен­ный не для одной колон­ки, а для несколь­ких. Такие индек­сы назы­ва­ют состав­ны­ми.

Если мы хотим уско­рить выпол­не­ние запро­са, усло­вие кото­ро­го вычис­ля­ет­ся по одной или несколь­ким колон­кам, в PostgreSQL нам необ­хо­ди­мо создать для этих коло­нок индекс с помо­щью коман­ды CREATE INDEX:

Эта коман­да име­ет боль­шой пере­чень допол­ни­тель­ных пара­мет­ров, с пол­ным спис­ком кото­рых мож­но озна­ко­мить­ся в доку­мен­та­ции.

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

Или мы можем создать индекс не по полю таб­ли­цы, а по функ­ции или ска­ляр­но­му выра­же­нию с одной или несколь­ки­ми колон­ка­ми таб­ли­цы (такие индек­сы назы­ва­ют функ­ци­о­наль­ны­ми или индек­са­ми по выра­же­нию). Это поз­во­ля­ет быст­ро нахо­дить дан­ные в таб­ли­це по резуль­та­там вычис­ле­ний. Напри­мер, мы хотим уско­рит запрос реги­стро­не­за­ви­си­мо­го поис­ка по тек­сто­во­му полю:

Если мы созда­дим обыч­ный индекс по полю text_field, он нам никак не помо­жет, т. к. PostgreSQL про­ин­дек­си­ру­ет те зна­че­ния, кото­рые хра­нят­ся в этом поле в исход­ном виде (необя­за­тель­но в ниж­нем реги­стре), а мы хотим искать по зна­че­ни­ям это­го поля, при­ве­ден­ные к ниж­не­му реги­стру вызо­вом функ­ции lower. Одна­ко мы можем создать индекс по резуль­та­там вычис­ле­ния выра­же­ния lower(text_fields):

CREATE INDEX index_name ON table_name(lower(text_field))

И такой индекс уже может успеш­но при­ме­нять­ся для уско­ре­ния наше­го запроса.

В зави­си­мо­сти от типа индек­си­ру­е­мых дан­ных, для индек­си­ро­ва­ния при­ме­ня­ют­ся раз­ные под­хо­ды. По умол­ча­нию при созда­нии индек­са исполь­зу­ет­ся индекс на осно­ве B-дере­ва. Но PostgreSQL под­дер­жи­ва­ет раз­ные типы индек­сов для очень широ­ко­го кру­га задач, и при необ­хо­ди­мо­сти мы можем ука­зать дру­гой тип индек­са, отлич­ный от B-tree. Для это­го перед спис­ком индек­си­ру­е­мых полей необ­хо­ди­мо ука­зать дирек­ти­ву USING <тип_индекса>. Напри­мер, для исполь­зо­ва­ния индек­са типа GiST:

CREATE INDEX index_name ON table_name USING GIST (column_name)

B-tree

Этот тип индек­са исполь­зу­ет­ся по умол­ча­нию и покры­ва­ет очень широ­кий круг задач (базы дан­ных боль­шин­ства при­ло­же­ний успеш­но могут обхо­дить­ся толь­ко индек­са­ми на осно­ве B-деревьев).

С помо­щью B-дере­ва мож­но про­ин­дек­си­ро­вать любые дан­ные, кото­рые могут быть отсор­ти­ро­ва­ны, т. е. для кото­рых при­ме­ни­мы опе­ра­ции срав­не­ния больше/меньше/равно. Сюда мож­но отне­сти чис­ла, стро­ки, даты и вре­мя, логи­че­ский тип и любые дан­ные, кото­рые мож­но ими закодировать.

Какой тип запро­сов может быть уско­рен с помо­щью B-дере­ва? На самом деле, прак­ти­че­ски любой запрос, усло­вие кото­ро­го явля­ет­ся выра­же­ни­ем, состо­я­щим из полей вхо­дя­щих в индекс, логи­че­ских опе­ра­то­ров и опе­ра­ций равенства/сравнения. Например:

  • Най­ти поль­зо­ва­те­ля по его email: 
  • Най­ти това­ры одной из двух категорий: 
    • SELECT * FROM goods WHERE category_id = 10 OR category_id = 20
  • Най­ти коли­че­ство поль­зо­ва­те­лей, заре­ги­стри­ро­вав­ших­ся в кон­крет­ный месяц: 
    • SELECT COUNT(id) FROM users WHERE reg_date >= 01.01.2021 AND reg_date <= 31.01.2021

Выпол­не­ние этих и мно­гих дру­гих запро­сов может быть уско­ре­но с помо­щью B-дере­ва. Кро­ме того, индекс на осно­ве B-дере­ва уско­ря­ет сор­ти­ров­ку резуль­та­тов, если в ORDER BY ука­за­но про­ин­дек­си­ро­ван­ное поле.

Прин­цип рабо­ты индек­са на осно­ве B-дере­ва осно­ван на рас­смот­рен­ном нами ранее алго­рит­ме бинар­но­го поис­ка: т. к. все зна­че­ния упо­ря­до­че­ны, мы можем быст­ро опре­де­лять обла­сти, в кото­рых гаран­ти­ро­ван­но не может быть дан­ных, удо­вле­тво­ря­ю­щих запрос, суще­ствен­но сни­жая таким обра­зом коли­че­ство пере­би­ра­е­мых записей.

Одна­ко хра­нить индекс  про­сто  в виде отсор­ти­ро­ван­но­го мас­си­ва мы не можем, т. к. дан­ные могут моди­фи­ци­ро­вать­ся: зна­че­ния могут менять­ся, запи­си — уда­лять­ся или добав­лять­ся. Что­бы эффек­тив­но под­дер­жи­вать хра­не­ние индек­си­ру­е­мых дан­ных в отсор­ти­ро­ван­ном виде, индекс хра­нят в виде сба­лан­си­ро­ван­но­го силь­но вет­вя­ще­го­ся дере­ва, назы­ва­е­мо­го B-дере­вом (B-tree).

Кор­не­вой узел B-дере­ва содер­жит в упо­ря­до­чен­ном виде несколь­ко зна­че­ний из обще­го набо­ра, допу­стим, эле­мен­тов. Тогда все осталь­ные эле­мен­ты мож­но рас­пре­де­лить по t+1 дочер­ним под­де­ре­вьям по сле­ду­ю­ще­му правилу:

  • Пер­вое под­де­ре­во будет содер­жать эле­мен­ты, кото­рые мень­ше, чем 1-й эле­мент кор­не­во­го узла (на рисун­ке выше пер­вое под­де­ре­во содер­жит чис­ла, мень­шие 30).
  • Вто­рое под­де­ре­во будет содер­жать эле­мен­ты, кото­рые нахо­дят­ся меж­ду 1-м и 2-м эле­мен­та­ми кор­не­во­го узла (на рисун­ке выше вто­рое под­де­ре­во содер­жит чис­ла меж­ду 30 и 70).
  • И т. д. — послед­нее под­де­ре­во будет содер­жать эле­мен­ты, боль­шие эле­мен­та кор­не­во­го узла с номе­ром t (на рисун­ке выше тре­тье под­де­ре­во содер­жит эле­мен­ты, боль­шие 70).

Каж­дое под­де­ре­во, в свою оче­редь, тоже явля­ет­ся B-дере­вом, име­ет кор­не­вой эле­мент и стро­ит­ся далее рекур­сив­но по тако­му же принципу.

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

  • Кор­не­вой узел содер­жит чис­ла 30 и 70, зна­чит, иско­мый эле­мент сле­ду­ет искать во вто­ром под­де­ре­ве, т.к. 67 > 30 и 67 < 70.
  • Кор­не­вой узел вто­ро­го под­де­ре­ва содер­жит эле­мен­ты 40 и 50. Т. к. 67 > 50, иско­мый эле­мент сле­ду­ет искать в тре­тьем потом­ке это­го узла.
  • На тре­тьем шаге мы полу­чи­ли узел, не име­ю­щий потом­ков, сре­ди эле­мен­тов кото­ро­го нахо­дим иско­мое чис­ло 67.

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

Кро­ме того, важ­ное и полез­ное свой­ство B-дере­ва при его исполь­зо­ва­нии в СУБД — воз­мож­ность эффек­тив­но хра­нить его во внеш­ней памя­ти. Каж­дый узел B-дере­ва обыч­но хра­нит такой объ­ем дан­ных, кото­рый может быть эффек­тив­но запи­сан на диск или про­чи­тан за одну опе­ра­цию вво­да-выво­да. B-дере­во даже может не поме­щать­ся цели­ком в опе­ра­тив­ной памя­ти. В этом слу­чае СУБД может дер­жать в памя­ти толь­ко узлы верх­не­го уров­ня (кото­рые веро­ят­но будут часто исполь­зо­вать­ся при поис­ке), читая узлы ниж­них уров­ней толь­ко при необходимости.

Индекс на осно­ве B-дере­ва может уско­рять запро­сы, кото­рые исполь­зу­ют не цели­ком вхо­дя­щие в индекс поля, а любую часть, начи­ная с нача­ла. Напри­мер, индекс может уско­рить запрос LIKE для поис­ка строк, кото­рые начи­на­ют­ся с задан­ной подстроки:

SELECT * FROM table_name WHERE text_field LIKE 'start_substring%'

Если индекс постро­ен по несколь­ким колон­кам, он может уско­рять запро­сы, в кото­рых фигу­ри­ру­ют одна или несколь­ко пер­вых коло­нок. Поэто­му важен поря­док, в кото­ром мы ука­зы­ва­ем колон­ки при созда­нии индек­са. Допу­стим, у нас есть индекс по колон­кам col_1 и col_2. Тогда он может исполь­зо­вать­ся в том чис­ле для уско­ре­ния запро­са вида:

SELECT * FROM table_name WHERE col_1 = 123

И нам не нуж­но созда­вать отдель­ный индекс для колон­ки col_1. Будет исполь­зо­вать­ся состав­ной индекс (col_1, col_2).

Одна­ко для запро­са толь­ко по колон­ке col_2 такой состав­ной индекс уже исполь­зо­вать не получится.

Подроб­нее, как индекс на осно­ве B-дере­ва реа­ли­зо­ван в PostgreSQL, см. ста­тью.

GiST и SP-GiST

GiST — сокра­ще­ние от «generalized search tree». Это сба­лан­си­ро­ван­ное дере­во поис­ка, точ­но так же, как и рас­смот­рен­ный ранее b-tree. Но b-tree при­ме­ни­мо толь­ко к тем типам дан­ных, для кото­рых име­ет смысл опе­ра­ция срав­не­ния и есть воз­мож­ность упо­ря­до­чи­ва­ния. Но PostgreSQL поз­во­ля­ет хра­нить и такие дан­ные, для кото­рых опе­ра­ция упо­ря­до­чи­ва­ния не име­ет смыс­ла, напри­мер, гео­дан­ные и гео­мет­ри­че­ские объекты.

Тут на помощь при­хо­дит индекс­ный метод GiST. Он поз­во­ля­ет рас­пре­де­лить дан­ные любо­го типа по сба­лан­си­ро­ван­но­му дере­ву и исполь­зо­вать это дере­во для поис­ка по самым раз­ным усло­ви­ям. Если при постро­е­нии B-дере­ва мы сор­ти­ру­ем все мно­же­ство объ­ек­тов и делим его на части по прин­ци­пу боль­ше-мень­ше, при постро­е­нии GiST индек­сов мож­но реа­ли­зо­вать любой прин­цип раз­би­е­ния любо­го мно­же­ства объектов.

Напри­мер, в GiST-индекс мож­но уло­жить R-дере­во для про­стран­ствен­ных дан­ных с под­держ­кой опе­ра­то­ров вза­им­но­го рас­по­ло­же­ния (нахо­дит­ся сле­ва, спра­ва; содер­жит и т. д.). Такой индекс досту­пен в PostgreSQL и может быть поле­зен при раз­ра­бот­ке гео­ин­фор­ма­ци­он­ных систем, в кото­рых воз­ни­ка­ют запро­сы вида «полу­чить мно­же­ство объ­ек­тов на кар­те, нахо­дя­щих­ся от задан­ной точ­ки на рас­сто­я­нии не более 1 км».

SP-GiST похож GiST, но он поз­во­ля­ет созда­вать несба­лан­си­ро­ван­ные дере­вья. Такие дере­вья могут быть полез­ны при раз­би­е­нии мно­же­ства на непе­ре­се­ка­ю­щи­е­ся объ­ек­ты. Бук­вы SP озна­ча­ют space partitioning. К тако­му типу индек­сов мож­но отне­сти kd-дере­вья, реа­ли­за­ция кото­рых при­сут­ству­ет в PostgreSQL. Его, как и R-дере­во, мож­но исполь­зо­вать для уско­ре­ния запро­сов гео­мет­ри­че­ско­го поис­ка. Свой­ство непе­ре­се­че­ния упро­ща­ет при­ня­тие реше­ний при встав­ке и поис­ке. С дру­гой сто­ро­ны, полу­ча­ю­щи­е­ся дере­вья, как пра­ви­ло, сла­бо вет­ви­сты, что услож­ня­ет их эффек­тив­ное хра­не­ние во внеш­ней памяти.

Кро­ме того, GiST и SP-GiST могут слу­жить свое­об­раз­ным фрейм­вор­ком, облег­ча­ю­щим рас­ши­ре­ние PostgreSQL и добав­ле­ние в него совер­шен­но новых видов дере­вьев для индек­са­ции новых типов данных.

Подроб­нее об алго­рит­мах, лежа­щих в осно­ве R- и kd-дере­вьев см. раз и два, а об их реа­ли­за­ции и исполь­зо­ва­нии в PostgreSQL см. в этой и этой ста­тье.

Заключение

Индек­сы — важ­ней­ший инстру­мент баз дан­ных, уско­ря­ю­щий поиск. Он не бес­пла­тен, созда­вать мно­го индек­сов без лиш­ней необ­хо­ди­мо­сти не сто­ит — индек­сы зани­ма­ют допол­ни­тель­ную память, и при любом обнов­ле­нии про­ин­дек­си­ро­ван­ных дан­ных СУБД долж­на выпол­нять допол­ни­тель­ную рабо­ту по под­дер­жа­нию индек­са в акту­аль­ном состоянии.

PostgreSQL под­дер­жи­ва­ет раз­ные типы индек­сов для раз­ных задач:

  • B-дере­во покры­ва­ет широ­чай­ший класс задач, т. к. при­ме­ни­мо к любым дан­ным, кото­рые мож­но отсортировать.
  • GiST и SP-GiST могут быть полез­ны при рабо­те с гео­мет­ри­че­ски­ми объ­ек­та­ми и для созда­ния совер­шен­но новых типов индек­сов для новых типов данных.
  • За рам­ка­ми этой ста­тьи ока­зал­ся ещё один важ­ный тип индек­сов — GIN. GIN индек­сы полез­ны для орга­ни­за­ции пол­но­тек­сто­во­го поис­ка и для индек­са­ции таких типов дан­ных, как мас­си­вы или jsonb. Подроб­нее см. в ста­тье. Совре­мен­ные вер­сии PostgreSQL име­ют вари­а­цию тако­го индек­са под назва­ни­ем RUM (см. ста­тью).