== Датотечни системи и организација на податоци - Индекси

=== Вовед

Експериментите се изведени во MySQL 8.0.43. Оригиналната `airportdb` база се користеше само за читање, а сите експериментални индекси беа креирани во изолираната `airportdb_index_lab`.

Во тест околината:
* `booking` има 54,304,619 записи
* `weatherdata` има 4,626,432 записи

InnoDB ги организира податоците во 16 KiB pages кои се кешираат во buffer pool. PRIMARY KEY претставува clustered структура за чување на редовите, додека нормалните PRIMARY и secondary индекси се организирани како B+ tree структури погодни за пребарување по еднаквост и опсег.

Secondary index содржи indexed key и PRIMARY KEY вредност. Composite index содржи повеќе колони во точно определен редослед, а covering index е индекс кој ги содржи сите податоци што му се потребни на конкретен прашалник.

=== 1. Secondary index - пребарување на резервации по патник

Сценарио: оператор пребарува резервации за конкретен патник.

{{{
SELECT booking_id, flight_id, seat, price
FROM airportdb_index_lab.booking
WHERE passenger_id = 10001;
}}}

Најпрво прашалникот беше извршен без secondary index на `passenger_id`.

|| '''Мерка''' || '''Без secondary index''' || '''idx_exp_booking_passenger''' ||
|| Access type || `ALL` || `ref` ||
|| Обработени / matching rows || ~54.3M || 1,436 ||
|| Benchmark median || 13.62 s || 0.005 s ||
|| Дополнителен storage / build || - || 847,233,024 B / 61.97 s ||

[[Image(3.PNG)]]

'''Слика 1.''' Без passenger index, MySQL користи `ALL` и проценува дека треба да обработи 54,163,080 редови.

Потоа беше креиран:

{{{
CREATE INDEX idx_exp_booking_passenger
ON airportdb_index_lab.booking(passenger_id);
}}}

[[Image(4.PNG)]]

'''Слика 2.''' Со passenger index, пристапот станува index lookup и се добиваат 1,436 записи.

Индексот значително ја намалува количината на работа за овој selective lookup. Сепак, индексот не е covering за `flight_id`, `seat` и `price`, па за тие колони се потребни дополнителни пристапи до clustered редовите.

Прикажаниот benchmark median е добиен од повторени нормални извршувања на прашалникот. Времето од `EXPLAIN ANALYZE` е посебна instrumentation мерка и не се користи како директна замена за benchmark времето.

=== 2. Composite index - редослед на колоните

Кај composite index редоследот на колоните е важен. За тестирање беше користен следниот прашалник:

{{{
SELECT COUNT(*) AS measurement_count
FROM airportdb_index_lab.weatherdata
WHERE station = 1
  AND time >= '08:00:00'
  AND time < '09:00:00';
}}}

Беа споредени:

{{{
(station, time, log_date)
}}}

и

{{{
(time, station, log_date)
}}}

|| '''Index''' || '''Прочитани index entries''' || '''Вратени редови''' || '''Benchmark median''' ||
|| `(station,time,log_date)` || 48,192 || 48,192 || 19.94 ms ||
|| `(time,station,log_date)` || 192,768 || 48,192 || 69.21 ms ||

[[Image(6.PNG)]]

'''Слика 3.''' Equality-first редослед: прво се ограничува `station = 1`, а потоа се пребарува временскиот опсег.

[[Image(7.PNG)]]

'''Слика 4.''' Range-first редослед: индексот почнува од `time`, па се читаат записи за сите четири stations пред да се филтрира `station = 1`.

Вториот индекс чита 4 пати повеќе index entries и има приближно 3.47 пати подолго измерено време. Ова практично го покажува значењето на leftmost-prefix правилото и пристапот equality-before-range.

=== 3. Covering index и однесување на optimizer-от

За едномесечен weather workload беше спореден потесниот индексен пристап со covering index:

{{{
(station, log_date, time, temp, humidity)
}}}

|| '''Weather workload''' || '''Narrow / PRIMARY path''' || '''Covering index''' ||
|| Structural rows / median || 35,712 / 12.47 ms || 8,928 / 5.62 ms ||
|| Analytical median (31 groups) || 11.29 ms || 4.55 ms ||
|| INDEX_LENGTH || 83,476,480 B || 109,740,032 B ||

Covering index-от овозможува потребните колони да се прочитаат директно од индексот и во execution plan се појавува `Using index`. Со тоа се избегнуваат дополнителни clustered-row reads, но операциите како `AVG`, `MIN`, `MAX` и `GROUP BY` сепак мора да се извршат.

Експериментот покажа и дека постоење на индекс не значи дека optimizer-от мора да го избере. Кај едномесечниот weather query, `(station,log_date,time)` беше прикажан во `possible_keys`, но MySQL сепак го избра PRIMARY индексот бидејќи го процени како поевтин план.

Дополнително беше тестиран и invisible index. Кога индексот е invisible, тој и понатаму физички постои, зафаќа простор и се одржува при промени, но optimizer-от го игнорира при нормален избор на план.

=== 4. Посложен аналитички workload

Следното сценарио го анализира ефектот на индексите врз посложен аналитички прашалник: top revenue routes по ден за периодот `2015-07-01` – `2015-07-03`.

Логичкиот тек е:

{{{
flight departure range
    -> flight / booking JOIN
    -> COUNT / SUM / AVG
    -> route_metrics CTE
    -> DENSE_RANK()
    -> top 5 routes per day
}}}

Во тестот се обработуваат:
* 14,858 flights
* приближно 1.74M joined bookings
* 14,858 route groups
* 15 final rows

Baseline без соодветен booking index беше анализиран само со `EXPLAIN`: `booking` имаше `ALL` access со проценка од приближно 54M редови. За baseline не беше мерено реално runtime.

Беа споредени следните два индекси:

|| '''Booking index''' || '''Access''' || '''Benchmark median''' || '''INDEX_LENGTH во lab''' ||
|| `(flight_id)` || non-covering lookup || 41.23 s || 1,694,466,048 B ||
|| `(flight_id,price)` || covering lookup || 1.89 s || 2,007,990,272 B ||

Со додавање на `price` во индексот, вредностите потребни за `SUM(price)` и `AVG(price)` се достапни директно од индексот.

Во оваа тест околина median времето се намали приближно 21.78 пати, но поширокиот индекс користи дополнителни 313,524,224 B во однос на потесниот.

Aggregation, CTE materialization, ranking и sorting и понатаму остануваат дел од execution plan-от.

[[Image(17.PNG)]]

'''Слика 5.''' Посложен CTE/window query и дел од неговиот execution tree.

=== 5. FULLTEXT index

Покрај B+ tree индексите, MySQL поддржува и други типови на пребарување.

Во `airplane_type` веќе постои:

{{{
FULLTEXT description_full(identifier, description)
}}}

Пример:

{{{
SELECT type_id, identifier,
       MATCH(identifier, description)
       AGAINST('Boeing' IN NATURAL LANGUAGE MODE) AS relevance
FROM airportdb.airplane_type
WHERE MATCH(identifier, description)
      AGAINST('Boeing' IN NATURAL LANGUAGE MODE)
ORDER BY relevance DESC, type_id;
}}}

Прашалникот врати 36 редови, а execution plan-от покажа `Full-text index search`.

[[Image(16.PNG)]]

'''Слика 6.''' FULLTEXT пребарување со `MATCH ... AGAINST` и `Full-text index search`.

FULLTEXT индексот е наменет за пребарување на текст според зборови и relevance, а не за обично B+ tree пребарување по еднаквост или опсег.

SPATIAL индексите се користат за просторни податоци. Explicit HASH индекс не е нормална user-defined опција за InnoDB табелите во овој проект; таков индекс може директно да се користи, на пример, кај MEMORY engine.

=== 6. Read / write / storage tradeoff

Индексите го забрзуваат читањето, но имаат цена при INSERT, UPDATE и DELETE бидејќи мора да се одржуваат дополнителни index структури.

За контролираниот INSERT тест:

|| '''Мерка''' || '''PRIMARY only''' || '''PRIMARY + passenger index''' ||
|| Inserted rows || 197,129 || 197,129 ||
|| Duration || 1.363 s || 1.913 s ||
|| Additional secondary storage || - || 3,686,400 B ||

Со passenger secondary index истиот INSERT batch беше 40.32% побавен бидејќи InnoDB мора да ги ажурира и clustered PRIMARY и secondary B+ tree структурата.

Од друга страна, за passenger lookup истиот индекс го намали времето од 13.62 s на приближно 0.005 s. Затоа користа од индекс зависи од односот меѓу read и write операции и од достапниот storage.

=== Заклучок

Од тестовите се гледа дека индексите имаат најголем ефект кога се избрани според конкретниот начин на користење на податоците.

Кај пребарувањето по `passenger_id`, secondary index го намали пристапот од околу 54.3M записи на 1,436. Кај composite index, редоследот на колоните влијаеше директно врз бројот на прочитани index entries. Covering index дополнително го намали пристапот до clustered редовите, а во дел од тестовите MySQL избра друг индекс иако постоеше дополнителен кандидат.

Пошироките индекси зафаќаат повеќе простор и го зголемуваат трошокот при INSERT, UPDATE и DELETE. Затоа при избор на индекс треба да се споредат execution plan, бројот на обработени редови, времето на извршување и дополнителниот storage/write cost.