Убрзавање претраге по текстуалном шаблону у PostgreSQL

2021-07-16

Садржај:

Увод

Претпоставимо да имамо табелу са уписима коју желимо да претражујемо по неком текстуалном атрибуту, као што је име или наслов. Такође желимо да сортирамо те уписе на начин који није нужно повезан ни са именом ни називом - на примјер, желимо да прво прикажемо најновије уписе, или оне најпопуларније. Након неког времена, број уписа у табели се повећао, претрага постаје све спорија, и морамо некако да је убрзамо. Какве су нам опције на располагању?

У наредним редовима видјећемо неке од техника оптимизације SQL перформанси, са акцентом на избјегавању операције сортирања као потенцијално скупе операције.

За примјер ћемо користити табелу која садржи податке о различитим музичким извођачима:

create table music_artist (
    id integer,
    name character varying(255),
    cover_photo character varying(255),
    short_bio text,
    active boolean,
    rating bigint
);

Иако се неки од концепата могу искористити у различитим системима база података, овај чланак се примарно бави са PostgreSQL и његовим могућностима.

Префиксна/постфиксна претрага

Иако претрага за текст који почиње (или завршава) на одређени начин није тако честа, технику вриједи описати из разлога што се оптимизација може постићи стандардним b-tree индексом.

Префикс и постфикс претрага користе LIKE оператор, са знаком % на крају (префикс), или на почетку (постфикс) текста за који претражујемо уписе. Како претрага не би била осјетљива на мала и велика слова, можемо да користимо ILIKE оператор, или да се и улазни и уписани текст конвертују у сва мала или сва велика слова.

Префиксна претрага

Упит за префиксну претрагу написан као припремљени исказ може да изгледа овако:

prepare mas(text) as 
  select * from music_artist 
  where name ilike $1 || '%' and active = true 
  order by rating desc 
  limit 5;

Извршавањем наредбе explain на овај упит показује да је потребно секвенцијално очитати цијелу табелу, све резултате сортирати у радној меморији, а затим одабрати првих 5 резултата:

=> explain execute mas('the');
                                           QUERY PLAN
------------------------------------------------------------------------------------------------
 Limit  (cost=29890.60..29891.17 rows=5 width=50)
   ->  Gather Merge  (cost=29890.60..34297.28 rows=38319 width=50)
         Workers Planned: 1
         ->  Sort  (cost=28890.59..28986.39 rows=38319 width=50)
               Sort Key: rating DESC
               ->  Parallel Seq Scan on music_artist  (cost=0.00..28254.12 rows=38319 width=50)
                     Filter: (active AND ((name)::text ~~* 'the%'::text))

Како b-tree индекс подржава префиксну претрагу текста (осјетљиво на мала/велика слова), можемо креирати индекс који ће садржати колоне name и rating, са текстом из колоне name конвертованим у сва мала слова:

create index pref_search_idx on music_artist (rating desc, lower(name)) 
  where active = true;

Овај индекс је парцијални, заснован на функцијама трансформације, који чува трансформисане податке за све уписе који имају колону active постављену на true. Како нас занимају само најбоље оцјењени резултати, искористићемо модификатор за опадајући редослијед desc на колони rating, и такође ћемо је поставити на прво мјесто приликом дефиниције индекса, јер редослијед мора да се поклапа са редослиједом у ORDER BY клаузули.

Како би се ажурирала статистика у систему након креирања индекса, искористићемо командуanalyze music_artist;.

Сада упит може да се препише да користи нови индекс тако што ћемо да искористимо LIKE оператор, а колону и улазни текст трансформишемо у сва мала слова:

prepare mas2(text) as 
  select * from music_artist 
  where lower(name) like lower($1) || '%' and active = true 
  order by rating desc 
  limit 5;

План извршавања новог упита сада садржи само скенирање индекса (index scan) који се зауставља чим се пронађе првих 5 резултата:

=> explain execute mas2('the');
                                            QUERY PLAN
--------------------------------------------------------------------------------------------------
 Limit  (cost=0.43..36.77 rows=5 width=50)
   ->  Index Scan using pref_search_idx on music_artist  (cost=0.43..58586.92 rows=8061 width=50)
         Filter: (lower((name)::text) ~~ 'the%'::text)

Вријеме одзива је сада побољшано са више стотина милисекунди на свега неколико милисекунди (у тестном окружењу са око 1.6 милиона уписа у табели)!

Као што видимо, у плану извршавања нема Sort операције, што значи да су резултати већ сортирани, и није потребно додатно сортирање.

Недостаци

Док ће извлачење првих неколико резултата бити изузетно брзо, пад перформанси ће се примјетити када претрага буде морала да зађе дубље како би нашла лошије оцијењене уписе. Уколико у том случају перформансе буду изузетно лоше, могуће их је додатно побољшати помоћу покривајућег индекса (умјесто претходног), односно индекса који садржи све колоне из упита:

-- covering index
create index pref_search_idx on music_artist (rating desc, lower(name)) 
  include (id, name, cover_photo, short_bio) 
  where active = true;

-- new query
prepare mas4(text) as 
  select id, name, cover_photo, short_bio, rating from music_artist 
  where lower(name) like lower($1) || '%' and active = true 
  order by rating desc 
  limit 5;

Креирање покривајућег индекса у суштини значи дуплирање података из много колона (или чак цијеле табеле), и потенцијално је скупо рјешење у смислу потребног капацитета дискова. Али предност покривајућег индекса је што све укључене податке држи физички близу у предефинисаном редослиједу, тако да претрага дубље у податке постаје значајно бржа, јер нема потребе за насумичним приступањем подацима из табеле на диску.

Постфиксна претрага

Постфиксна претрага се састоји од тога тако што се једноставно обрну улазни текст и текст из колоне, и креира индекс са истим функцијама трансформације:

-- index
create index pref_search_rev_idx on music_artist (rating desc, reverse(lower(name))) 
  where active = true;

-- query
prepare mas3(text) as 
  select * from music_artist 
  where reverse(lower(name)) like reverse(lower($1)) || '%' and active = true 
  order by rating desc 
  limit 5;

План извршавања, као и недостаци, су исти као и за префиксну претрагу.

Инфиксна претрага

Ово је знатно чешћи начин претраге, када улазни текст може да буде било гдје у уписаном тексту, односно инфиксна претрага. Ова претрага се врши тако што се улазни текс окружи са % знаковима, нпр. ILIKE %input text%. Како убрзати такву претрагу?

Најчешћи начин за PostgreSQL је кориштење екстензије pg_trgm која подржава операторе шаблонске претраге (LIKE, ILIKE, ~*), а онда се креира GIN (или GiST) индекс над текстуалном колоном:

-- add extension
create extension pg_trgm;

-- create GIN index
create index ma_name_gin_idx on music_artist using gin(name gin_trgm_ops) 
  where active = true;

-- query
prepare mas5(text) as 
  select * from music_artist 
  where name ilike '%' || $1 || '%' and active = true 
  order by rating desc 
  limit 5;

Перформансе су значајно повећане на овај начин. Са разумном количином података, ова техника је довољна да се вријеме одзива држи довољно ниским. Али шта ако није довољно ниско? Шта још може да се уради?

Ако погледамо план извршавања од упита изнад, видимо да укључује неколико корака, укључујући сортирање:

=> explain (costs off) execute mas5('the');
                                QUERY PLAN
---------------------------------------------------------------------------
 Limit
   ->  Sort
         Sort Key: rating DESC
         ->  Bitmap Heap Scan on music_artist
               Recheck Cond: (((name)::text ~~* '%the%'::text) AND active)
               ->  Bitmap Index Scan on ma_name_gin_idx
                     Index Cond: ((name)::text ~~* '%the%'::text)

Рјешавање овог проблема захтјева нешто више креативности.

GiST индекс

Екстензија pg_trgm такође може да користи и GiST индекс за шаблонску претрагу текста, иако се GIN индекс генерално препоручује као бржи у оваквим случајевима. GiST такође интерно може да има ”лажно позитивне” резултате, што утиче на перформансе.

Шта је посебно у вези GiST индекса? Овај индекс може да користи тзв. алгоритам k-најближих сусједа како би сортирао резултате помоћу оператора удаљености (<->), док GIN индекс не подржава сортирање уопште.

Како GiST индекс не подржава скаларне вриједности сам по себи, а rating колона је скаларна вриједност (број типа bigint), прво нам је потребна екстензија која омогућава такву употребу:

create extension btree_gist;

Сада креирајмо GiST индекс над табелом (напомена: претходно креирани индекси треба да се уклоне). Редослијед колона није важан:

create index ma_name_gist_idx on music_artist using gist(name gist_trgm_ops, rating) 
  where active = true;

Упит који ће да искористи нови индекс може да се напише овако:

prepare mas6(text) as 
  select * from music_artist 
  where name ilike '%' || $1 || '%' and active = true 
  order by rating <-> 50000 
  limit 5;

Сада план извршавања изгледа много једноставније:

=> explain (costs off) execute mas6('the');
                               QUERY PLAN
-------------------------------------------------------------------------
 Limit
   ->  Index Scan using ma_name_gist_idx on music_artist
         Index Cond: ((name)::text ~~* (('%'::text || $1) || '%'::text))
         Order By: (rating <-> '50000'::bigint)

Вриједност 50000 овде је вриједност већа или једнака максималној вриједности из rating колоне, како би резултати били добијени у опадајућем редослиједу. Оно што је важно напоменути овде је да за оператор дистанце потребна константа. Ако покушамо да вриједност 50000 добијемо преко угњежденог упита, сортирање помоћу индекса неће бити активирано, и операција Sort ће да се појави у плану извршавања! То значи да ова вриједност мора да буде претходно прикупљена, у случају да се претрага обавља на овај начин.

Напомена: опрезно са кориштењем колона типа bigint са овим приступом, јер чини се да постоји грешка приликом кориштења високих вриједности за константу, која може да поремети редослијед резултата. Чак сам поставио питање на Stack Overflow на ову тему, али чини се да нема одговора.

Недостаци

Овај начин индексирања пати од истих проблема као и префиксна/постиксна претрага. Што је мања оцјена, дуже је вријеме претраге. Нажалост, не може даље да се побољша кориштењем покривајућег индекса. GiST индекс подржава покривајуће индексирање, али скенирање самог индекса неће бити активирано за све класе оператора, што се чини да је овде случај.

Закључак

Да ли ћете користити стандардни индекс, GIN или GiST како би убрзали претрагу, зависи од тога шта је циљ, као и од количине прикупљених података. Надам се да сам дао увид у предности и мане за сваки од њих када је у питању претрага текста по шаблону. Међутим, ако релациона база података није довољно добра за претрагу веће количине текста, можда би било боље искористити специјализовани алат за претрагу текста, као нпр. Elastic Search.

Додатна литература

Топло препоручујем веб сајт Use The Index, Luke! који води Маркус Винанд, гдје може много да се научи о индексирању података и SQL-у, пријеко потребном знању за сваког чији опис посла укључује рад са базама података
Ако неког интересује више примјера из области оптимизације перформанси, направио сам GitHub репозиторијум гдје сам се бавио техникама оптимизације сличним онима описаним у овом чланку, као и неким стратегијама денормализације података

#PostgreSQL #Перформансе