Indeksi (InterBase i Firebird)
Alexey Kovyazin, последње ажурирање 07-Сеп-2005
Концепт који је узет као основа индекса је једноставан и визуелан и представља једну од најважнијих основа дизајна база података. На основу индекса засновани су многи основни објекти база података, а штавише, правилна употреба индекса је кључна за побољшање продуктивности апликација база података. Међутим, шта је индекс? Индекс је уређени показивач записа у табели. Показивач значи да индекс садржи вредности једног или више поља у табели и адресе страница података где се те вредности налазе (за детаље о страницама података, погледајте поглавље “Структура InterBase базе података”) (део 4). Другим речима, индекс се састоји од парова вредности “вредност поља” - “физичка локација овог поља”.
Дакле, по вредности поља (или поља), укљученог у индекс, користећи индекс можемо брзо пронаћи место у табели где је запис који садржи ову вредност смештен. Уређено значи да су вредности поља ускладиштене у индексу уређене. Врло често се индекс пореди са библиотечким каталогом, у коме су све књиге записане на картице и уређене на неки начин: по абецеди или темама, и у свакој картици садржи информацију о томе где је тачно дата књига смештена у складишту.
Зашто су нам потребни индекси?
Једина ствар коју индекси промовишу је убрзавање проналажења записа по његовом индексираном пољу (индексирано - значи укључено у индекс). Главна функција индекса је да обезбеди брзо проналажење записа у табели. Свака употреба индекса своди се на ово.
Како се ова функција проналажења реализује? На улазу ове функције имамо вредност индексираног поља (или више поља). Као резултат проналажења требало би да добијемо цео запис, у коме индексирано поље има унапред задату вредност. Прво се у индексу (тачније, у уређеном низу вредности индексираног поља) тражи потребна вредност, затим се узима адреса странице података где се потребни запис налази, сервер одлази на ту страницу и чита пронађени запис. Изгледа прилично незгодно, међутим, претрага користећи индекс је много пута бржа од секвенцијалног набрајања свих вредности из табеле.
Ако наставимо аналогију између индекса и библиотечког каталога, видећемо да је проналажење записа користећи индекс врло слично претрази књиге помоћу картице. Када пронађемо књигу у прилично малом каталогу (у поређењу са целим библиотечким складиштем), одмах добијамо информацију о томе где је тачно књига ускладиштена и можемо отићи право тамо. Претрага без коришћења индекса може се упоредити са секвенцијалним набрајањем свих књига у библиотеци!
Набрајање свих записа у табели назива се директно или природно. Треба рећи да упркос снази савремених рачунара природно набрајање може бити веома дуго ако табела садржи велики број записа.
Како су организовани?
Индекс није део табеле, он је засебан објекат повезан са табелом и другим објектима базе података. Ово је веома важна тачка имплементације система за управљање базама података која омогућава раздвајање складиштења информација од њихове презентације.
InterBase као и свака друга релациона база података чува записе у табелама на неуређен начин, тј. уопште не води рачуна о томе како су записи физички распоређени у табели. Неуређено складиштење значи да два записа додата у табелу један за другим можда неће бити један поред другог. Штавише, подаци извучени из табеле такође немају редослед осим оног који би корисник требало експлицитно да наведе при прављењу упита за проналажење.
Међутим, не можемо без уређивања ускладиштених података: крајњи корисници апликација желе да виде податке у одређеном редоследу - на пример, презимена људи по абецеди. Индекси решавају проблем презентације података на уређен начин. Вредности поља укључене у индекс су уређене и представљене у посебном приказу, оптимизованом за проналажење потребних вредности (наиме, ово је од суштинског значаја за креирање уређених секвенци).
Раздвајање складиштења података од њихове презентације даје додатне предности у поређењу са директним сортирањем - можда ћете морати да сортирате почетну табелу на различите начине. Тада ће вам индекси помоћи - може постојати до 64 индекса за сваку табелу!
Ако говоримо о имплементацији индекса на физичком нивоу, они представљају бинарно стабло чији чворови представљају парове “вредност поља у индексу” - “алокација података у табели”. Проналажење потребног записа у индексу врши се помоћу механизма хеш-претраге - једног од најбржих алгоритама за претрагу.
Примена индекса
Сада, када је јасно шта можемо захтевати од индекса, време је да сазнамо о њиховој функцији у бази података. Индекси се користе у три главна случаја:
-
Убрзавање извршења упита. Индекси се креирају за поља која се користе под условима претраге SQL-упита.
-
Подршка јединствености вредности у пољима; примарни кључ (о коме је било речи у поглављу “Табеле. Примарни кључеви”) захтева да у табели неће постојати две идентичне вредности поља укључених у примарни кључ. Да би се испунио овај услов, при уметању новог записа треба претражити исту вредност која ће бити уметнута. За проналажење записа користи се посебна врста индекса - јединствени индекс (погледајте испод).
-
Подршка референцијалног интегритета. Ограничења страних кључева (која се разматрају у поглављу “Ограничења базе података”) користе се за проверу да вредности уметнуте у табелу нужно постоје у другој табели. При креирању страног кључа аутоматски се креира индекс. Овај индекс се примењује за убрзавање упита који користе спајање табела, као и за проверу услова страног кључа. Укратко смо покрили све могуће примене индекса. Сада ћемо детаљније размотрити посебности сваког случаја и одговорићемо на најчешће постављана питања у вези са применом индекса.
Убрзавање извршења упита користећи индексе
Горе је описано да примена индекса може у великој мери убрзати извршење упита. Заиста је тако у већини случајева, али постоје одређене напомене. Прво ћемо одговорити на питање које се често јавља код оних који су се упознали са индексима. Ако индекси убрзавају проналажење из базе података, зашто не бисмо индексирали сва поља у табели? Постоје два момента која блокирају опште индексирање - простор на диску и трошкови при модификацији података у табели. Сваки креирани индекс има величину једнаку величини података у индексираном пољу, плус величина података алокације записа. Ако креирамо индексе за свако поље у табели, њихова укупна величина биће већа од величине података у табели! Стога, креирање великог броја индекса доводи до огромне потрошње простора на диску.
Други момент је важнији. То су издаци при модификацији података у табели. У релационом систему за управљање базама података, као што знате, записи у табелама су неуређени и стога додавање/брисање записа иде без значајних издатака ресурса сервера. Чак и ако се запис избрише из средине базе података, нема померања величина података да би се попунила та празнина - то није потребно: сервер ће једноставно означити празно место и уписати нешто тамо када буде потребно. Што се тиче додавања, у већини случајева оно се извршава на крају табеле. Међутим, иако сервер не помера главне податке у табели при модификацији, подаци ускладиштени у индексима се преуређују сваки пут при додавању/брисању записа! Другим речима, сервер мора поново изградити индекс при додавању записа у средину табеле. Свакако, имплементација индекса је на неки начин намењена за честе реорганизације, али ове операције ипак одузимају време и ресурсе процесора и када постоји велики број индекса у табели, модификација података у њој може бити много спорија него у истој табели без индекса!
Ово су два главна разлога која ометају опште индексирање. Поред њих, постоје још неке напомене које ограничавају примену индекса. Прва је правило од 20 %. Оно каже да ако упит за проналажење враћа више од 20 % записа из табеле, коришћење индекса може успорити проналажење података! Свакако, ситуација зависи од конкретног упита и услова постављених за проналажење, али треба запамтити да је 20 % записа праг када ефикасност коришћења индекса постаје сумњива. Друга напомена није формулисана тако јасно. Она је повезана са радом InterBase оптимизатора.
Оптимизатор је скуп механизама који развија план извршења упита. Када корисник да било који SQL упит InterBase-у, он одређује шта сервер треба да врати након извршења упита, али не дефинише КАКО сервер треба да испуни упит. Оптимизатор на основу датог упита креира план његовог извршења, тј. одакле и којим редом ће се подаци за извршење упита узимати, који индекси ће се при томе користити. Када сервер анализира услове претраживања (то су углавном делови израза WHERE, ORDER BY, итд.) за свако поље укључено у услов, сервер покушава да користи индекс. Нажалост, алгоритам креирања плана је непотпун и оптимизатор често користи индексе који нису превише ефикасни за конкретан упит, због чега време извршења може бити значајно успорено. Стога, креирање непотребних индекса може довести до креирања неоптималних планова.
Треба напоменути да је у Yaffil клону овај проблем решен коришћењем савремених алгоритама за креирање планова. Трећи случај када индекс није потребан су поља са ограниченим скупом вредности - на пример, поље које чува информације о полу особе и садржи само две могуће вредности - “F” и “M”; нема смисла индексирати ово поље. Дакле, размотрили смо главна ограничења при креирању индекса. Сада треба да покријемо проблем када је неопходно користити индексе да би се постигло побољшање продуктивности. Постоје 3 главна случаја када поље мора бити индексирано:
- Када се ово поље користи под условима претраживања у упитима
- Када се ово поље користи при спајању табела
- Када се ово поље користи у изјави сортирања ORDER BY Ако се поље примењује на горе поменути начин, креирање индекса за њега може довести до побољшања продуктивности упита.
Размотримо синтаксу креирања индекса. Ево комплетног формата DDL команде која омогућава креирање индекса:
CREATE [UNIQUE] [ASC[ENDING] | DESC[ENDING]] INDEX index ON table (col [, col …]);
Минимални израз који креира индекс је следећи:
CREATE INDEX my_index ON Table_example(ID)
У овом примеру, индекс са именом my_index је креиран за табелу Table_example, а ID поље је индексирано поље. Индекс је растући, тј. вредности у њему су поређане по растућем редоследу, као и неуникатан, што значи да ID поље може имати неколико идентичних вредности. Ово је свакако најједноставнији пример индекса - најчешћи. Као што можемо видети из описа синтаксе, индекс може садржати не једно, већ неколико поља. Такав индекс се користи када се упити често извршавају и садрже комбинацију индексираних поља под условима претраживања или сортирања. На пример, ако имамо табелу која садржи поља Презиме, Име, Очинство, такав индекс ће се применити при креирању упита који користи сортирање по Презимену, Имену и Очинству. Уопштено, није неопходно навести услове за сва 3 поља примењена у индексу да би се искористиле његове предности. Ако желимо да сортирамо резултат упита, индекс ће се користити у случају да се прво поље у услову сортирања поклапа са првим пољем у индексу. На пример, наш индекс ће се применити у случају сортирања по Презимену и Имену.
Према документацији за оптимизацију извршења упита који садржи у изјави WHERE спајање поља са OR условом, треба користити не збирни индекс, већ неколико појединачних за сва поља укључена у OR услов.
Што се тиче питања реда сортирања индекса, он може бити или растући или опадајући. Зашто су нам потребни различити редови сортирања? Очигледно, за различита сортирања! Ако желимо да сортирамо људе по презимену у растућем редоследу, креирамо растући индекс (ASC), а ако у опадајућем (од Z до A) - онда опадајући! Ако желимо обоје, морамо креирати оба индекса.
Подршка референцијалног интегритета помоћу индекса
Постоји још једна опција у дефиницији индекса - UNIQUE. Ако је наведемо, индекс ће омогућити уметање само јединствених вредности у табелу. Заправо, то је основа за имплементацију јединствених кључева. Јединствени кључеви се широко користе у базама података. То јест, РК је јединствени кључ-индекс, али није сваки УК РК. Горе смо говорили само о РК. Примарни кључ је најчешће коришћени тип јединственог кључа. При креирању примарног кључа за табелу аутоматски се креира јединствени индекс. Добија име састављено од RDB$PRIMARYNNN, где је NNN секвенцијални јединствени број у оквиру базе података. Дакле, два главна ограничења референцијалног интегритета - јединствени кључ и примарни кључ се реализују коришћењем јединственог индекса. Очигледно је да је појам јединствености неспојив са појмом недефинисане вредности. Другим речима, не би требало да буде вредности NULL типа у пољима садржаним у јединственим индексима. Пре креирања јединственог индекса за поље, неопходно је поставити NOT NULL ограничење. Ако се индекс креира за податке који већ постоје, онда ће при креирању индексирано поље бити проверено да ли садржи понављајуће вредности. Ако садржи, биће вам забрањено да креирате индекс.
Поред јединствених и примарних кључних ограничења, механизам индекса је основа имплементације још једног ограничења референцијалног интегритета - страног кључа. Ограничење страног кључа се поставља за једно или неколико поља било које табеле и спречава уметање вредности у та поља које нису укључене у примарни кључ друге, родитељске табеле. За имплементацију страног кључа, тј. за вршење провере да ли постоји вредност у родитељској табели, аутоматски се креира посебан индекс. Његово име је RDB$FOREIGNNN, где је NNN секвенцијални јединствени број у оквиру базе података.
Зашто се механизам индекса користи за имплементацију ограничења референцијалног интегритета? Ствар је у томе што су индекси у InterBase-у у посебном, повлашћеном положају - каже се да се извршавају ван контекста трансакција. Ово је веома важно својство. Говорићемо о трансакцијама касније, у поглављу посвећеном њима. Сада ћемо само поменути да када су индекси ван трансакција, то значи да сви корисници који истовремено раде са подацима у истој табели морају да поштују ограничења референцијалног интегритета.
Оптимизација продуктивности индекса
У наслову овог дела можемо пронаћи известан парадокс - индекси, као што је горе речено, треба да убрзају извршење упита, а испоставља се да и њих треба оптимизовати! Али шта да се ради (такав је живот) - неко мора да води бригу о индексима. Шта се дешава са индексима? Зашто “губе форму”? Мораћемо још једном да кажемо да су индекси реализовани као бинарно стабло. И када се нови запис додаје (ажурира, брише - како желите) у табелу, нова грана се додаје у стабло. Ове гране се не додају у средину стабла, већ на врхове других грана. Постепено стабло постаје све разгранатије (или неуравнотеженије), а претраживање - мање ефикасно. Поновна изградња стабла или (у неким случајевима) поновно израчунавање статистике може побољшати ситуацију.
Периодично је потребно поново креирати индекс да би се обновила његова продуктивност. Поновно креирање индекса се дешава у следећим случајевима:
- При поновној изградњи индекса коришћењем ALTER INDEX команде.
- При брисању и поновном креирању индекса коришћењем DROP INDEX и CREATE INDEX команди.
- При прављењу резервне копије и враћању из резервне копије коришћењем gbak алата.
Такође можете користити поновно израчунавање статистике. Али морате разумети да ова операција не мења стање индекса, она само информише оптимизатор о прецизним информацијама о његовом стању омогућавајући правилно коришћење овог индекса. Другим речима, поновно израчунавање статистике није “лек” за индекс, већ само прецизна дијагностика његовог стања. Размотримо све ове начине оптимизације индекса детаљније. Употреба ALTER INDEX команде има следећи формат:
ALTER INDEX name {ACTIVE | INACTIVE};
Овде је name име индекса, а ACTIVE и INACTIVE - два стања индекса у која се може превести коришћењем ALTER INDEX команде. Параметар ACTIVE значи да је индекс активан и може се применити у свим упитима и процедурама. Ако поставите индекс на INACTIVE, то ће резултирати искључивањем његове употребе. За преуређивање стабла треба секвенцијално извршити две команде:
ALTER INDEX name INACTIVE; ALTER INDEX name ACTIVE;
На тај начин, индекс ће бити поново изграђен. Коришћење ALTER INDEX-а има одређена ограничења: не можете поново изградити индексе који се користе у примарним, јединственим и страним кључевима; не можете поново изградити индекс ако га тренутно користи било који упит; такође, за измену индекса потребно је имати администраторска права (SYSDBA) или бити креатор датог индекса.
Поновно креирање индекса помоћу DROP INDEX и CREATE INDEX команди доводи до потпуног брисања индекса из базе података, а затим до његовог креирања из основног облика. Синтакса DROP INDEX команде је очигледна:
DROP INDEX име_индекса;
Након брисања, потребно је креирати индекс са истим именом и параметрима користећи CREATE INDEX команду чију смо синтаксу већ размотрили. Начин поновне изградње индекса његовим потпуним поновним креирањем има слична ограничења као и коришћење ALTER INDEX-а.
Трећи начин поновне изградње индекса заснива се на својству резервних копија InterBase база података креираних помоћу gbak алата. Ствар је у томе да се при прављењу резервне копије подаци укључени у индекс не чувају у резервној копији, већ се чува само дефиниција индекса. Приликом враћања из резервне копије, индекс се поново креира. Ако желите да сазнате више о резервним копијама, погледајте поглавље „Прављење резервне копије и враћање из резервне копије" (део 4).
Четврти начин за побољшање продуктивности индекса је прикупљање статистике о индексима помоћу SET STATISTICS команде. Статистика табеле је вредност у опсегу од 0 до 1, чија вредност зависи од броја различитих записа у табели. InterBase оптимизатор користи статистику за одређивање ефикасности примене одређеног индекса у упиту. Када се број записа у табели може значајно променити (на пример, због великог броја уметања или брисања), поновно израчунавање статистике може значајно побољшати продуктивност. Команда за поновно израчунавање статистике је следећа:
SET STATISTICS INDEX name;
Овде је name име индекса за који се статистика поново израчунава. Поновно израчунавање статистике не поново гради индекс, и зато је ослобођено већине ограничења постављених за горе описане начине побољшања продуктивности, осим што само креатор индекса или системски администратор (корисник са именом SYSDBA) може поново израчунати статистику. Тачна статистика омогућава оптимизатору да донесе исправну одлуку о томе да ли ће користити одређени индекс или не.
Размотрили смо неколико начина за побољшање продуктивности индекса. Користећи ALTER INDEX и DROP/CREATE INDEX команде, можемо поново изградити било које индексе осим системских индекса креираних аутоматски, намењених за обезбеђивање референцијалног интегритета. Ако желите да поново изградите ове индексе, требало би да користите команде за измену и креирање табела - ALTER TABLE и CREATE TABLE, јер су ови индекси саставни део табеларних кључева.