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

Вовед

Експериментите се изведени во 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

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

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

CREATE INDEX idx_exp_booking_passenger
ON airportdb_index_lab.booking(passenger_id);

Слика 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

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

Слика 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-от.

Слика 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.

Слика 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.