Ие­рар­хи­че­ские би­то­вые ин­дек­сы

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

Otkrytye sistemy. SUBD. - - СУБД - Илья Труб

Клю­че­вые сло­ва: СУБД, оп­ти­ми­за­ция Sql-за­про­сов Keyworsds: DBMS, query optimization

По­ня­тие би­то­вых ин­дек­сов (bitmap index) хо­ро­шо зна­ко­мо каждому про­ек­ти­ров­щи­ку баз дан­ных. Впер­вые вве­ден­ные в 1987 го­ду, они ста­ли стан­дарт­ным спо­со­бом оп­ти­ми­за­ции за­про­сов в про­мыш­лен­ных СУБД: Oracle, Cache и др. Од­на­ко эф­фек­тив­ность их ис­поль­зо­ва­ния силь­но за­ви­сит как от за­про­сов, так и от осо­бен­но­стей ба­зы дан­ных. В [1] рас­кры­ва­ют­ся не­ко­то­рые сек­ре­ты и раз­вен­чи­ва­ют­ся устой­чи­вые за­блуж­де­ния по по­во­ду би­то­вых ин­дек­сов, но в це­лом ли­те­ра­ту­ры на рус­ском язы­ке крайне ма­ло, а меж­ду тем в за­ви­си­мо­сти от за­да­чи мож­но ис­поль­зо­вать не би­то­вые ин­дек­сы в ви­де, предо­став­ля­е­мом СУБД, а их мо­ди­фи­ка­цию, что су­ще­ствен­но по­вы­ша­ет эф­фек­тив­ность по­ис­ка, при­чем за­тра­ты на та­кую мо­ди­фи­ка­цию с лих­вой оку­па­ют­ся по­вы­ше­ни­ем про­из­во­ди­тель­но­сти обработки за­про­сов.

Вы­бор стра­те­гии ис­поль­зо­ва­ния би­то­вых ин­дек­сов определяется ря­дом фак­то­ров, сре­ди них:

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

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

Ко­ли­че­ство под­хо­дов, учи­ты­ва­ю­щих эти и дру­гие фак­то­ры, се­год­ня очень ве­ли­ко. Изу­че­ние и раз­ви­тие тео­рии и прак­ти­ки би­то­вых ин­дек­сов идет по трем ос­нов­ным на­прав­ле­ни­ям: сжа­тие (compression), ко­ди­ро­ва­ние (encoding) и груп­пи­ро­ва­ние (binning). Оста­но­вим­ся по­дроб­нее на третьем, наи­бо­лее важ­ном для по­ни­ма­ния кон­цеп­ции иерар­хи­че­ских ин­дек­сов. Же­ла­ю­щим же озна­ко­мить­ся с ос­нов­ны­ми тео­ре­ти­че­ски­ми до­сти­же­ни­я­ми по би­то­вым ин­дек­сам в их ис­то­ри­че­ском раз­ви­тии мож­но по­ре­ко­мен­до­вать об­зор [5].

Идея груп­пи­ро­ва­ния до­ста­точ­но про­ста — вме­сто то­го, что­бы со­зда­вать би­то­вую стро­ку для каж­до­го от­дель­но­го зна­че­ния свойства, весь диа­па­зон зна­че­ний де­лит­ся на ин­тер­ва­лы (bins), а би­то­вая стро­ка со­зда­ет­ся для каж­до­го ин­тер­ва­ла. На­при­мер, би­то­вые ин­дек­сы для групп вы­гля­дят сле­ду­ю­щим об­ра­зом: груп­па 0–11010010; груп­па 1–00000101; груп­па 2–00101000 (табл. 1). По­ми­мо оче­вид­но­го вы­иг­ры­ша по об­ще­му объ­е­му ин­дек­сов, вы­иг­рыш в про­из­во­ди­тель­но­сти до­сти­га­ет­ся в том слу­чае, ес­ли диа­па­зон

за­про­са по ат­ри­бу­ту пол­но­стью на­кры­ва­ет од­ну или несколь­ко групп, — ко­ли­че­ство дизъ­юнк­ций би­то­вых строк то­гда со­кра­ща­ет­ся до од­но­го. Од­на­ко, по­ми­мо оп­ти­маль­но­го раз­би­е­ния на груп­пы, здесь возникает про­бле­ма, ко­гда за­прос лишь ча­стич­но на­кры­ва­ет од­ну из групп и тре­бу­ет­ся до­пол­ни­тель­ная про­вер­ка для каж­до­го зна­че­ния из та­кой груп­пы: удо­вле­тво­ря­ет оно за­про­су или нет. Эта про­бле­ма по­лу­чи­ла на­зва­ние candidate checking, и для ее ре­ше­ния та­к­же пред­ло­же­но мно­же­ство под­хо­дов. Но в це­лом, осо­бен­но с по­яв­ле­ни­ем хра­ни­лищ и озер дан­ных, про­сто груп­пи­ро­ва­ния, да­же с все­воз­мож­ны­ми мо­ди­фи­ка­ци­я­ми, ока­за­лось недо­ста­точ­но для достижения при­ем­ле­мой про­из­во­ди­тель­но­сти обработки за­про­сов на боль­ших ба­зах дан­ных. Про­дол­же­ни­ем кон­цеп­ции binning ста­ли ие­рар­хи­че­ские би­то­вые ин­дек­сы (Hierarchical Bitmap

Indexes, HBI) — ак­тив­но раз­ви­ва­ю­ще­е­ся се­год­ня на­прав­ле­ние оп­ти­ми­за­ции ра­бо­ты с ба­за­ми дан­ных.

Ие­рар­хи­че­ские ин­дек­сы бе­рут свое на­ча­ло с ра­бо­ты [4] и бы­ли вве­де­ны для вы­пол­не­ния за­про­сов по ат­ри­бу­там-мно­же­ствам (Set-valued Attributes), до­пу­сти­мых стан­дар­том SQL3.

Рас­смот­рим таб­ли­цу Purchases (trans id, cust id, products), хра­ня­щую за­пи­си о по­куп­ках кли­ен­та. В таб­ли­це три по­ля: ID транзакции (покупки), ID кли­ен­та, куп­лен­ные им про­дук­ты. Ти­по­вые за­про­сы мож­но раз­де­лить на за­прос под­мно­же­ства (subset query), ко­гда ищут­ся покупки, в со­став ко­то­рых вхо­дит за­дан­ный на­бор про­дук­тов; за­прос по­кры­ва­ю­ще­го мно­же­ства (superset query), ко­гда ищут­ся покупки, в со­став ко­то­рых вхо­дят покупки толь­ко из за­дан­но­го мно­же­ства; за­прос по­до­бия (similarity query), ко­гда ищут­ся покупки, сов­па­да­ю­щие с дан­ным мно­жест-

вом с точ­но­стью до уста­нов­лен­но­го по­ро­га по­до­бия. Вот как мог бы вы­гля­деть subset query на SQL для ко­ли­че­ства по­ку­пок с мо­ло­ком и мас­лом:

SELECT COUNT (DISTINCT A.cust id) FROM Purchases A, Purchases B

WHERE A.trans id = B.trans id

AND A.item = ‘milk’ AND B.item = ‘butter’;

Та­кой за­прос нель­зя на­звать эф­фек­тив­ным: во-пер­вых, из-за «тя­же­лой» опе­ра­ции self-join для таб­ли­цы по­ку­пок; во-вто­рых, до­бав­ле­ние еще од­но­го про­дук­та в за­прос при­во­дит к из­ме­не­нию пред­ло­же­ния FROM; и, на­ко­нец, за­прос в це­лом те­ря­ет есте­ствен­ность и труд­но чи­та­ет­ся.

Идея HBI со­сто­ит в том, что­бы про­ну­ме­ро­вать все зна­че­ния, ко­то­рые мо­гут быть эле­мен­та­ми set-ат­ри­бу­та, и па­ра­мет­ри­зо­вать его дву­мя чис­ла­ми: l — дли­на ин­декс­но­го уз­ла, d — ко­ли­че­ство уров­ней иерар­хии. То­гда лю­бое зна­че­ние set-ат­ри­бу­та (неко­то­рое мно­же­ство) мо­жет быть пред­став­ле­но де­ре­вом би­то­вых ин­дек­сов. Та­кое пред­став­ле­ние поз­во­ля­ет све­сти выполнение за­про­са с усло­ви­ем по set-ат­ри­бу­ту к неболь­шо­му ко­ли­че­ству эф­фек­тив­ных ло­ги­че­ских опе­ра­ций над би­то­вы­ми стро­ка­ми, рав­но­му d. По­яс­ним это на при­ме­ре subset-за­про­са. Пусть зна­че­ние set-ат­ри­бу­та S= {2, 3, 9, 12, 13, 14, 38, 40}, l=4, d=3. То­гда

это зна­че­ние мож­но пред­ста­вить в ви­де дерева би­то­вых ин­дек­сов (табл. 2). На пер­вом уровне на­хо­дит­ся един­ствен­ный узел — ко­рень (root node), на по­след­нем — уз­лы-ли­стья (leaf nodes), на осталь­ных — внутренние уз­лы (inner nodes).

Но­ме­ра по­зи­ций еди­ниц в ли­стьях со­от­вет­ству­ют зна­че­ни­ям элементов S (ну­ме­ра­ция от еди­ни­цы). Пу­стые уз­лы (empty nodes), со­сто­я­щие толь­ко из ну­лей, — эти уз­лы не хра­нят­ся в ви­де ин­дек­са на дис­ке. Пусть име­ет­ся за­прос q= {9, 13, 40}. Ис­поль­зуя ин­декс­ное де­ре­во для S, нуж­но опре­де­лить, удо­вле­тво­ря­ет мно­же­ство это­му за­про­су или нет.

Та­б­ли­ца 1. Груп­пи­ро­ва­ние

Newspapers in Russian

Newspapers from Russia

© PressReader. All rights reserved.