Индекс — як бор ва барои ҳамеша

Таърифи индекс

Индекс сохторест дар диск, ки ба ҷадвал ё намоиш (view) вобаста буда, ёфтани сатрҳоро аз он тез мекунад.

Индекс як сохтори ёрирасони додаҳо — data structure — барои баланд бардоштани суръати ҷустуҷӯ дар пойгоҳи додаҳо мебошад.

Бе индекс маҷбур мешавем тамоми ҷадвалро аз назар гузаронем — Full Table Scan. Барои ҷадвалҳои калон, масалан дорои чанд миллион сатр, ин кор хеле суст иҷро мешавад.

Индекс ба феҳристи китоб монанд аст: аз рӯйи он мефаҳмед, ки мавзуи муайян дар кадом саҳифаҳо ҷойгир аст.

Индекс суръати хонданро зиёд мекунад, аммо хароҷоти иловагӣ дорад: амалиёти INSERT / UPDATE / DELETE сусттар мешаванд, зеро индекс низ бояд нав карда шавад.

Агар индексро дуруст истифода барем, амалиёти зерин тезтар мешаванд:

• WHERE
• JOIN
• ORDER BY
• GROUP BY

Стратегияи индекс барои зиёд кардани суръат як чиз аст: хурд кардани фазои ҷустуҷӯ — search space.

Роҳи тезтарини ҷустуҷӯ дар байни чанд миллион сатр ин аст, ки ҳамаи он сатрҳоро насанҷем ва фазои ҷустуҷӯро то ҳадди имкон кам кунем.

Мафҳуми Heap ва тарзи нигоҳдории ҷадвалу индекс дар диск

Heap шакли нигоҳдории додаҳост, ки дар он пойгоҳи додаҳо сатрҳоро бе тартиби муайян ба диск менависад.

Дар матни аслӣ он ба мафҳуми heap ва stack дар хотираи барномаҳо, махсусан C/C++, монанд карда шудааст, бо ин фарқ ки дар ин ҷо сухан аз нигоҳдорӣ дар диск меравад. Он ба сохтори додаҳои heap, ки дар алгоритмҳо истифода мешавад, дахл надорад.

Дар матни пешниҳодшуда худи тасвирҳо мавҷуд нестанд; танҳо шарҳу унвонҳои онҳо омадаанд.

Шарҳи тасвири нигоҳдории ҷадвалҳо ва индексҳо дар диск:

Фарз мекунем ҳазор сатр дорем ва дар ҳар page — саҳифа се сатр ҷой мегирад. Додаҳо, албатта, дар шакли бинарӣ навишта мешаванд. Дар мисол андозаи саҳифаи PostgreSQL 8 KB гирифта шудааст.

Пойгоҳи додаҳо барои ҳар сатр шиносаи дохилӣ, бо номи row_id ё tuple_id, таъин мекунад.

Дар қисми индекс қимати сутунро ҳамроҳ бо row_id ва page_number нигоҳ медорем. Худи индекс низ ба шакли саҳифаҳо нигоҳ дошта мешавад.

Дар тасвир индекс хаттӣ нишон дода шудааст, аммо вобаста ба навъаш метавонад дарахт ё сохтори дигар бошад.

10 (1, 0)  

Яъне қимати 10 дар сатри row_id = 1, дар саҳифаи 0 ҷойгир аст.

40 (4, 1)  

Яъне қимати 40 дар сатри row_id = 4, дар саҳифаи 1 ҷойгир аст.

Минбаъд навъҳои индексро аз рӯйи чанд гурӯҳбандӣ баррасӣ мекунем.

1. Навъҳои индекс аз рӯйи нигоҳдории физикӣ

Додаҳои ҷадвал ба таври пешфарз дар Heap, дар диск, бе тартиби муайян нигоҳ дошта мешаванд.

1.1. Индекси кластерӣ — Clustered Index

Бо истифода аз индекси кластерӣ метавонем пойгоҳи додаҳоро водор кунем, ки додаҳоро аз рӯйи сутуни муайян, одатан primary key, ба тартиб нигоҳ дорад. Гӯё худи ҷадвал як навъ индекс бошад.

Ин навъи индекс дар SQL Server ва MySQL бо муҳаррики InnoDB вуҷуд дорад. Дар тавсифи матни аслӣ primary key ҳамчун clustered index истифода шуда, ҷадвал ба тартиб нигоҳ дошта мешавад.

PostgreSQL чунин навъи индекс надорад: ҳамаи индексҳояш secondary — дуюмдараҷа мебошанд. Яъне додаҳои ҷадвал дар Heap бе тартиби муайян навишта мешаванд ва сохтори алоҳидаи берун аз ҷадвал ба ҷустуҷӯ кумак мекунад.

Албатта, PostgreSQL фармони CLUSTER дорад, ки ҷадвалро аз рӯйи индекс ба тартиб медарорад. Аммо ин тартиб доимӣ нигоҳ дошта намешавад ва бо тағйир ёфтани сатрҳо метавонад вайрон шавад.

1.2. Индекси ғайрикластерӣ — Non-Clustered Index

Индекси ғайрикластерӣ сохтори додаҳоест, ки аз ҷадвал ҷудо сохта мешавад ва ба тартиби нигоҳдории додаҳо дар дохили ҷадвал дахолат намекунад.

Масалан:

• B-tree
• GIN
• ва дигарҳо.

2. Навъҳои индекс аз рӯйи сохтори додаҳо

Дар PostgreSQL чанд навъи индекс вуҷуд дорад.

2.1. B+Tree

Ин навъи индекс барои чунин вазифаҳо хеле хуб кор мекунад:

• амалгарҳои муқоиса: ``, =, =;
• дархостҳои фосилавӣ — range query;
• нигоҳдории қиматҳои ягона — unique;
• ORDER BY.

Сабабаш ин аст, ки қиматҳоро ба тартиб нигоҳ медорад.

Вақте ба PostgreSQL мегӯед индекс созад, ба таври пешфарз ҳамин навъро месозад. Худи PostgreSQL онро B-tree меномад, аммо мувофиқи матни аслӣ дар татбиқаш аз B+Tree истифода мешавад.

Дар матн гуфта мешавад, ки ин навъи индекс барои сутунҳои дорои кардиналияти паст, яъне шумораи ками қиматҳои фарқкунанда, монанди enum ё true/false, мувофиқ нест.

2.2. GIN

Ихтисораи Generalized Inverted Index, яъне «индекси чаппаи умумӣ» мебошад.

Барои инҳо мувофиқ аст:

• ҷустуҷӯи пурраматнӣ — Full-Text Search;
• массивҳо — Array;
• додаҳои JSONB.

Чаро онро «чаппа» меноманд?

Он ҳам қиматҳоро ба сатрҳои мувофиқ пайваст мекунад:

a → [row1, row2, ...]  
b → [row4, row6, ...]  

Фарқаш дар он аст, ки қимати сутунро ба қисмҳо — токенҳо — ҷудо мекунад.

Масалан, барои ҷустуҷӯи пурраматнӣ ҷумла ба калимаҳо ҷудо шуда, ҳар калима ба сатрҳои дорои он пайваст мешавад.

Индекси маъмулӣ:

"how are you?" → [row1, row2, ...]  

Индекси чаппа:

"how" → [row1, row10]  
"are" → [row2, row20]  
"you" → [row3, row4, row12]  

«Умумӣ — Generalized» чӣ маъно дорад?

Яъне индекс танҳо барои ҷустуҷӯи пурраматнӣ нест. Он барои JSON, массив ва навъҳои дигари додаҳо низ кор карда метавонад. Танҳо бояд operator class — opclass-и мувофиқро муайян кунем, то индекс тавонад аз қиматҳои сутун ҷузъҳои лозимаро ҷудо кунад.

Ин навъи индекс барои маҷмуаҳои хеле хурди додаҳо ва ҷадвалҳое, ки бисёр нав мешаванд, мувофиқ нест.

2.3. Hash

Ин як hash map аст: қиматҳо ба функсияи ҳеш дода мешаванд ва натиҷаи ҳеш ба сатри мувофиқ пайваст мегардад.

Барои муқоисаи баробарӣ — equality — истифода мешавад.

Аммо индекси пешфарзи B-tree низ ин вазифаро иҷро мекунад ва илова бар он қиматҳоро ба тартиб нигоҳ медорад. Аз ҳамин сабаб Hash камтар истифода мешавад.

Дар бисёр ҳолатҳо B-tree ҳатто беҳтар кор мекунад. Мувофиқи матни аслӣ, Hash дар баъзе ҳолатҳо, вақте қиматҳои сутун якнавохт паҳн шудаанд, масалан UUID, метавонад беҳтар бошад.

2.4. GiST

Ихтисораи Generalized Search Tree мебошад.

Барои додаҳое мувофиқ аст, ки сохтори хаттӣ надоранд, масалан додаҳои ҷуғрофӣ.

Масалан, мехоҳем объектҳоро дар доираи як километр аз нуқтаи ҷуғрофии муайян пайдо кунем. Дар чунин ҳолат GiST аз B-tree мувофиқтар ва самараноктар аст.

Дар матн гуфта мешавад, ки барои муқоисаи баробарӣ ба андозаи B-tree хуб нест, аммо барои ҷустуҷӯ дар ҳудудҳо хеле мувофиқ аст.

2.5. SP-GiST

Ихтисораи Space-Partitioned GiST мебошад.

Дар матни аслӣ он ҳамчун варианти беҳинашудаи навъи қаблӣ барои додаҳои камзич, пароканда ё ғайриякнавохт тавсиф шудааст.

2.6. BRIN — Block Range Index

Барои ҷадвалҳои хеле калон мувофиқ аст, ки додаҳояшон табиатан ба тартиб ворид мешаванд ва байни қиматҳои додаҳо ва ҷойгиршавии физикии онҳо ҳамбастагӣ — correlation вуҷуд дорад.

Масалан, ҷадвали логҳои рӯйдодҳо.

Ин индекс ҳаҷми хеле кам дорад ва ҳатто дарахт нест. Он танҳо фосилаҳои блокҳоро ба фосилаҳои муайяни қиматҳо, масалан фосилаҳои вақт, пайваст мекунад.

Дар матни аслӣ гуфта мешавад, ки он барои муқоисаи фосилаҳо мувофиқ буда, барои баробарӣ фоида надорад.

Ҳамчунин, муаллиф мегӯяд, ки баъди ҳазфи додаҳо ва иҷрои VACUUM ҳамбастагии табиии додаҳо бо ҷойгиршавии физикиашон метавонад вайрон шавад. Дар натиҷа индекс камсамартар мешавад, зеро пойгоҳи додаҳо маҷбур мешавад ҷойҳои бештарро ҷустуҷӯ кунад.

3. Навъҳои индекс аз рӯйи хусусиятҳои амалӣ

3.1. Индекси яксутуна — Single-Column Index

Танҳо дар як сутун сохта мешавад:

CREATE INDEX idx_name ON grades(name);  

3.2. Индекси бисёрсутуна ё таркибӣ — Multi-Column / Composite Index

Омезиши чанд сутунро индекс мекунем:

CREATE INDEX idx_orders_customer_date  
ON orders(customer_id, order_date);  

Қоидаи пешванди чап — Leftmost Prefix Rule

Тартиби муайян кардани сутунҳо муҳим аст!

Дар ин ҷо сухан аз B-tree меравад. Индекс:

1. Аввал аз рӯйи калиди якум ба тартиб медарорад.
2. Қиматҳои дорои калиди якуми якхеларо аз рӯйи калиди дуюм ба тартиб медарорад.
3. Қиматҳои дорои калидҳои якуму дуюми якхеларо аз рӯйи калиди сеюм ба тартиб медарорад.

Яъне, мувофиқи шарҳи матни аслӣ, индекси таркибӣ мустақиман ба чунин дархостҳо кумак мекунад:

• танҳо сутуни якум;
• сутуни якум ҳамроҳ бо сутунҳои баъдӣ, бо ҳамон тартиб.

Барои ҳолатҳои дигар чунин кафолат дода намешавад.

Муаллиф бар ин асос тавсия медиҳад, ки сутунҳои дорои кардиналияти баландтарро аввал ва сутунҳои дорои кардиналияти пасттарро баъд ҷой диҳем.

3.3. Индекси қисмӣ — Partial Index

Бо гузоштани шарт доираи индексро маҳдуд мекунем. Ба ҷойи тамоми ҷадвал танҳо қисми муайяни он индекс мешавад.

Масалан:

CREATE INDEX idx_users_active_email  
ON users(email)  
WHERE is_active = true;  

Дархост:

SELECT *  
FROM users  
WHERE is_active = true  
AND email = 'test@example.com';  

Дар ин мисол мо ҳамеша корбарони фаъолро ҷустуҷӯ мекунем. Пас беҳтар аст индексро танҳо барои сатрҳое созем, ки шартро қонеъ мекунанд.

Бо ин роҳ фазои ҷустуҷӯ боз ҳам хурдтар ва индекс самараноктар мешавад.

3.4. Индекси пӯшонанда — Covering Index / Include Index

Баъзе сутунҳоеро, ки қисми калиди индекс нестанд, низ дар индекс нигоҳ медорем. Ҳадаф ин аст, ки пойгоҳи додаҳо онҳоро бевосита аз индекс гирад ва барои ёфтанашон ба Heap наравад.

Масалан:

SELECT age, email  
FROM users  
WHERE name = 'Ali';  

Индекс:

CREATE INDEX idx_user_name  
ON users(name)  
INCLUDE (age, email);  

Дар ин мисол мо аз рӯйи ном ҷустуҷӯ мекунем, аммо ҳамеша синну сол ва почтаи электрониро низ мехоҳем.

Ба ҷойи он ки аввал бо Index Scan ё Bitmap Index Scan сатрҳои мувофиқро пайдо карда, баъд барои гирифтани майдонҳои дигар ба Heap равем, метавонем аз Index Only Scan истифода барем ва додаҳоро аз худи индекс гирем.

Сутунҳо ду гурӯҳ мешаванд:

• Key column: сутуне, ки қисми калиди индекс аст.
• Non-key column: сутуне, ки қисми калиди индекс нест, аммо қиматаш дар индекс нигоҳ дошта мешавад.

3.5. Индекси ягонагӣ — Unique Index

Кафолат медиҳад, ки қиматҳои такрорӣ вуҷуд надошта бошанд:

CREATE UNIQUE INDEX idx_email  
ON users(email);  

3.6. Индекс аз рӯйи функсия ё ифода — Function / Expression Index

Индекс дар натиҷаи як ифода сохта мешавад.

Масалан, агар аксари ҷустуҷӯҳо бо номи ба ҳарфҳои хурд табдилёфта анҷом шаванд:

CREATE INDEX idx_lower_name  
ON customers(LOWER(first_name));  

Филтри Блум — Bloom Filter

Филтри Блум сохтори додаҳоест, ки ба чунин савол ҷавоб медиҳад:

«Оё ин қимат узви ин маҷмуа ҳаст?»

Он метавонад ду навъи ҷавоб диҳад:

• «Не» — бо итминон.
• «Бале» — эҳтимолан.

Агар «не» гӯяд, он қимат воқеан дар маҷмуа вуҷуд надорад. Агар «бале» гӯяд, мумкин аст вуҷуд дошта бошад, аммо мумкин аст вуҷуд надошта бошад.

Яъне:

• False positive дорад: метавонад қимати мавҷуднабударо эҳтимолан мавҷуд нишон диҳад.
• False negative надорад: қимати мавҷударо ғоиб нишон намедиҳад.

Мубодила чунин аст: хотираи камтар сарф мекунем, аммо дақиқии камтар мегирем.

Ин барои чӣ лозим аст?

Филтри Блум метавонад дархостҳоро беҳина карда, шумораи муроҷиатҳоро ба пойгоҳи додаҳо, диск ё манбаи асосӣ кам кунад. Худи он хотираи хеле кам мегирад.

Дар шабакаҳо, Cassandra барои кам кардани I/O, Redis ва бисёр ҷойҳои дигар истифода мешавад ва аз ҷустуҷӯҳои нолозим пешгирӣ мекунад.

PostgreSQL низ як навъи иловагии индекс бо номи Bloom дорад. Дар матн он барои ҷадвалҳои калон ва филтркунии чанд майдон бо AND муфид дониста шудааст.

CREATE EXTENSION IF NOT EXISTS bloom;

CREATE INDEX idx_users_bloom  
ON users USING bloom (gender, status, age);  

Чӣ гуна кор мекунад?

Массиви битӣ месозем ва ҳамаи битҳоро дар оғоз 0 мегузорем.

Баъд функсияи ҳеш муайян мекунем. Ҳар қимате, ки ба маҷмуа илова мешавад, аз ин функсия мегузарад.

Функсияи ҳеш рақамеро дар ҳудуди индексҳои массив медиҳад. Бити ҳамон мавқеъро 1 мекунем.

Ҳангоми санҷиши мавҷудияти қимат:

1. Қиматро аз функсияи ҳеш мегузаронем.
2. Бити мувофиқро месанҷем.
3. Агар бит 0 бошад, қимат ҳатман вуҷуд надорад.
4. Агар бит 1 бошад, қимат эҳтимолан вуҷуд дорад ва бояд дар манбаи асосӣ санҷида шавад.

Дар мисоли тасвир барои кам кардани натиҷаҳои мусбати бардурӯғ аз се функсияи ҳеш истифода шудааст. Битҳои мувофиқи онҳо якҷоя санҷида мешаванд.

Агар ҳамаи битҳо 1 шаванд, чӣ мешавад?

Дақиқӣ хеле паст мешавад: филтр ба ҳама қиматҳо «эҳтимолан ҳаст» мегӯяд ва ҳар дафъа маҷбур мешавем ба пойгоҳи додаҳо муроҷиат кунем.

Дар чунин ҳолат метавон шумораи битҳоро зиёд карда, филтри нав сохт.

Агар додае ҳазф шавад, чӣ кор мекунем?

Битҳоро бевосита 0 карда наметавонем, зеро намедонем он бит танҳо ба додаи ҳазфшуда тааллуқ дорад ё бо додаҳои дигар муштарак аст.

Дар Bloom Filter-и анъанавӣ ҳазф дастгирӣ намешавад. Сохторҳои дигар, монанди Counting Bloom Filter ё Cuckoo Filter, имкони ҳазф доранд.

Дар шарҳи матн барои ҳисобкунии муроҷиатҳо ба ҷойи як бит адади бутун истифода мешавад ва ҳангоми илова кардани дода ҳисобкунак як воҳид зиёд мегардад. Бо ин роҳ ҳазф кардан мумкин мешавад, аммо хотираи бештар сарф мешавад.

То ин ҷо бо навъҳои индекс шинос шудем. Акнун ба қисми амалӣ мегузарем!

Таҳлили дархостҳо

Барои таҳлили дархостҳои PostgreSQL ва фаҳмидани он ки барои гирифтани додаҳо кадом марҳилаҳо иҷро мешаванд ва оё индекс истифода мешавад, аз инҳо истифода мебарем:

EXPLAIN  

ва:

EXPLAIN ANALYZE  

EXPLAIN танҳо нақшаи иҷрои дархостро нишон медиҳад.

EXPLAIN ANALYZE илова бар нақша ва тахминҳо, худи дархостро иҷро мекунад ва омори воқеиро нишон медиҳад.

Дар шарҳи намунаи EXPLAIN гуфта мешавад, ки амалиёти Seq Scan — хондани пайдарпайи ҷадвал иҷро шудааст. Муаллиф рақамҳои намунаи ғоибро чунин шарҳ медиҳад:

• арзиши ибтидоӣ 0;
• арзиши ниҳоӣ тақрибан 289 ва каме бештар;
• шумораи тахминии сатрҳо зиёда аз 12 миллион;
• андозаи миёнаи ҳар сатр 31 байт.

Андозаи сатр аз ҳаҷми майдонҳо ҳосил мешавад: масалан, 4 байт барои integer, 8 байт барои double ва ғайра.

Натиҷаи EXPLAIN ANALYZE инчунин нишон медиҳад, ки:

• банақшагирӣ чӣ қадар вақт гирифт;
• иҷрои дархост чӣ қадар вақт гирифт.

Нақшаҳо метавонанд аз ин хеле мураккабтар бошанд. Барои хуб фаҳмидани онҳо бояд худатон бо ин абзорҳо кор кунед.

Саволу ҷавоб

1. Кай индекс фоидаи зиёд надорад?

Мувофиқи матни аслӣ:

• вақте ҷадвал хурд аст;
• вақте кардиналияти сутун паст аст, масалан gender, status ё true/false.

2. Фарқи Covering Index ва Composite Index чист?

Дар индекси таркибӣ ё бисёрсутуна ҳамаи сутунҳои муайяншуда key column мебошанд. Индекс аз рӯйи онҳо сохта ва ба тартиб дароварда мешавад.

Дар индекси пӯшонанда танҳо сутунҳои калидӣ барои сохтор ва тартиби индекс истифода мешаванд. Қиматҳои сутунҳои ғайрикалидӣ ҳам дар индекс нигоҳ дошта мешаванд, то гирифтани онҳо тавассути Index Only Scan имконпазир гардад ва муроҷиат ба Heap кам шавад.

Дар шарҳи матн:

• индекси таркибӣ барои ҷустуҷӯ аз рӯйи чанд сутун истифода мешавад;
• индекси пӯшонанда барои ҳолатест, ки аз рӯйи сутунҳои калидӣ ҷустуҷӯ мекунем, аммо ҳамеша чанд майдони иловагӣ низ лозиманд.

Муаллиф илова мекунад, ки агар воситаи истифодашаванда индекси пӯшонандаро дастгирӣ накунад, метавон ба ҷойи он индекси таркибӣ сохт. Дар матни аслӣ Django ҳамчун мисол оварда шудааст.

Дар чунин ҳолат майдонҳои иловагӣ низ қисми калиди индекс мешаванд. Аз рӯйи шарҳи муаллиф, ин метавонад индекси вазнинтар созад, ҷойи бештар гирад ва нисбат ба истифодаи INCLUDE самаранокии камтар дошта бошад.