Changes between Version 3 and Version 4 of Indexing

Timestamp:

09/10/26 22:50:42 (6 hours ago)

Author:

222004

Comment:

--

Indexing

@@ -1 +1 @@
 == Датотечни системи и организација на податоци - Индекси
 
-=== Преглед на шемата на AirportDB\\
-
-Во нашите case-сценарија табелата booking со ~3.5 милиони редови е главната цел за индексирање. Повеќето сценарија ја вклучуваат.\\
-
-=== Типови на индекси во MySql
-**B-Tree (BTree) index — default индекс во MySql**\\
-Најчест тип. Работи добро за: = , <, >, BETWEEN, LIKE 'prefix%', ORDER BY, GROUP BY.\\
-\\
-**Composite index**
-Покрива повеќе услови. Редоследот во овој тип на индекс е критичен — индексот може да даде подобри перформанси амо ако WHERE ги содржи условите одлево надесно (leftmost prefix rule).
+=== Вовед
+
+Експериментите се изведени во 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)
+}}}
+
 Пример:
-{{{
-
-CREATE INDEX idx_comp ON tabela (col_a, col_b, col_c);
-
-}}}
-
-Може да се користи за:\\
-   WHERE col_a = ?\\
-   WHERE col_a = ? AND col_b = ?\\
-   WHERE col_a = ? AND col_b = ? AND col_c = ?\\
-   WHERE col_a = ? ORDER BY col_b\\
- НЕ може за:\\
-   WHERE col_b = ?        \\  
-   WHERE col_c = ?          \\
-
-\\
-
-**Covering Index**\\
-Индекс кој ги содржи сите колони од еден прашалник. Ако индексот ги има сите тие колони, MySQL не мора воопшто да ја чита самата табела (clustered data).
-Се што му треба, го зема директно од индексот. - Со овој тип на индекс се намалува бројот на И/О операции, што доведува до побрзо извршување, но е поголем индекс што зафаќа повеќе простор и ги успорува сите INSERT/UPDATE операции.\\
-Пример за креирање:
-{{{
-
-CREATE INDEX idx_cov ON booking (flight_id, price, seat);
-
-}}}
-\\
-**Hash индекс**\\
-Само за точна еднаквост (=). Не поддржува range, ORDER BY, GROUP BY. Во MySQL InnoDB НЕ може да се креира рачно - InnoDB го прави адаптивен hash автоматски. Може рачно само во MEMORY engine.\\
-Пример за креирање:\\
-{{{
-
-CREATE TABLE temp_lookup (
-  id INT NOT NULL,
-  val VARCHAR(50),
-  PRIMARY KEY (id)
-) ENGINE=MEMORY;
- 
-CREATE INDEX idx_hash ON temp_lookup (vrednost) USING HASH;
-
-}}}
-
-Некои други типови: FULLTEXT индекс (за пребарување на текст), SPATIAL индекс (геолокациски).\\
-\\
-
-== Сценарија и индексирање на прашалници
-=== Сценарио 1:  Агент на шалтер го пребарува целото патничко досие за конкретен патник
-Табели: booking JOIN flight JOIN passengerdetails\\
-Цел: B-Tree индекс на еден столбец (booking.passenger_id)\\
-\\
-Најпрво, за тестирање, ќе ја извршиме следната скрипта која безбедно ќе ги избрише сите предефинирани индекси кои веќе ги има во Airportdb од страна на MySql, без нарушување на foreign-key constraints://
-
-[wiki:Script1 Погледни ја скриптата овде]
-//
-**Прашалник без индекс:**
-{{{
- 
-EXPLAIN ANALYZE
-SELECT
-    b.booking_id,
-    b.seat,
-    b.price,
-    f.flightno,
-    f.departure,
-    f.arrival,
-    pd.firstname,
-    pd.lastname,
-    pd.country
-FROM booking b
-JOIN flight f         ON b.flight_id    = f.flight_id
-JOIN passengerdetails pd ON b.passenger_id = pd.passenger_id
-WHERE b.passenger_id = 10001
-ORDER BY f.departure DESC;
-
-}}}
-
-
-
-
+
+{{{
+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.