Зачем знать алгоритмы Андрей Аксенов Sphinx Technologies Inc. Highload++2009

Who is Mr. Aksenov?

честно листал все!

не прочитал ни одной :(

делал веб-сайты и веб-движок

делал игры и 3D движок

делаю поисковой движок

free open source search

что могу рассказать?

как устроены всякие движки

на пальцах, не по книжке! (см. не читатель)

про движок СУБД (любой)

Система Управления Базой Данных

данные – это таблицы. из строк

строки – нужно где-то хранить

это, кстати, данные – без индексов

добавляем PK, и брюки превращаются…

почему так? разные стратегии хранения строк

MyISAM – в порядке поступления (в конец файла)

InnoDB – хранит постранично, внутри странички – в порядке PK

(InnoDB, после добавления PK)

MyISAM – обычное хранение InnoDB – т.н. кластерное

умеем хранить – теперь нужно быстро искать!

SELECT * FROM users WHERE id=123

SELECT * FROM users WHERE lastname=Pupkin

SELECT * FROM users WHERE lastname LIKE Pu%

SELECT * FROM goods WHERE MATCH(ipod) ORDER BY price ASC

SELECT * FROM users WHERE sex=F AND age>=18 AND age

как выполнять запрос?

полный перебор? мееедленно

нас спасут…

индексы! алгоритмы уже спешат на помощь!

смысл любого вида индекса?

быстрый поиск по ключу(-ам)

видов индексов – тоже много

hash index

R-tree index

full-text index

индекс общего назначения – типично B-tree

поиск – по равенству, диапазону (чисел, строк, и т.п.)

дискует – страничками (хорошо!)

используется – всеми

используется несмотря ни на что!!!

как устроено?

keyid Аня3 Боря141 Ваня592 keyid Гоша653 Дима589 Ева793 keyid Женя238 Зина462 Ира643 keyid Коля383 Лена279 Маша502 АняГошаЕваЖеняКоляМаша АняЖеняМаша (B-дерево; странички; масштаб 1:72)

два вида страничек

Промежуточные = ключи + указатели на другие странички АняЖеняМаша { key1, ptr1, key2, ptr2, …, keyN }

Аня3Боря141Ваня592 Листовые = ключи + соотв-е им данные (eg. row_offset) { key1, data1, key2, data2, … } keyid Аня3 Боря141 Ваня592

Промежуточные Листовые keyid Аня3 Боря141 Ваня592 keyid Гоша653 Дима589 Ева793 keyid Женя238 Зина462 Ира643 keyid Коля383 Лена279 Маша502 АняГошаЕваЖеняКоляМаша АняЖеняМаша

почему все используют этот ужас?!

во-1х – легко искать по ключу

пример – ищем Зину

keyid Аня3 Боря141 Ваня592 keyid Гоша653 Дима589 Ева793 keyid Женя238 Зина462 Ира643 keyid Коля383 Лена279 Маша502 АняГошаЕваЖеняКоляМаша АняЖеняМаша

keyid Аня3 Боря141 Ваня592 keyid Гоша653 Дима589 Ева793 keyid Женя238 Зина462 Ира643 keyid Коля383 Лена279 Маша502 АняГошаЕваЖеняКоляМаша АняЖеняМаша

keyid Аня3 Боря141 Ваня592 keyid Гоша653 Дима589 Ева793 keyid Женя238 Зина462 Ира643 keyid Коля383 Лена279 Маша502 АняГошаЕваЖеняКоляМаша АняЖеняМаша

keyid Аня3 Боря141 Ваня592 keyid Гоша653 Дима589 Ева793 keyid Женя238 Зина462 Ира643 keyid Коля383 Лена279 Маша502 АняГошаЕваЖеняКоляМаша АняЖеняМаша

keyid Аня3 Боря141 Ваня592 keyid Гоша653 Дима589 Ева793 keyid Женя238 Зина462 Ира643 keyid Коля383 Лена279 Маша502 АняГошаЕваЖеняКоляМаша АняЖеняМаша

keyid Аня3 Боря141 Ваня592 keyid Гоша653 Дима589 Ева793 keyid Женя238 Зина462 Ира643 keyid Коля383 Лена279 Маша502 АняГошаЕваЖеняКоляМаша АняЖеняМаша

ура – Зина нашлась!!!

хорошо – поиск работает…

…но он чё, всегда такой резкий?

keyid Аня3 Боря141 Ваня592 keyid Гоша653 Дима589 Ева793 keyid Женя238 Зина462 Ира643 keyid Коля383 Лена279 Маша502 АняГошаЕваЖеняКоляМаша АняЖеняМаша – В жизни – под 1000 (а не 3) записей на страничку – Два уровня страничек – 1000*1000 – миллион – Три уровня – миллиард… – Итого 2-3 странички max – практически всегда

почему все используют этот ужас?!

во-2х – легко обновлять

keyid Аня3 ?? ?? странички обычно НЕ полны

keyid Аня3 Боря141 ?? вставляем…

keyid Аня3 Боря141 Ваня592 вставляем…

keyid Аня3 Боря141 Ваня592 Гоша653 вставляем… оп-па, некуда!!

keyid Аня3 Боря141 Ваня592 Гоша653 keyid ?? ?? ?? ?? создаем новую страничку

keyid Аня3 Боря141 ?? keyid Ваня592 Гоша653 ?? создаем новую страничку

keyid Аня3 Боря141 ?? keyid Ваня592 Гоша653 ?? …и суем ее в родителя

keyid Аня3 Боря141 ?? keyid Ваня592 Гоша653 ?? это все – тоже трогаем max 2-3 странички

B-tree Kung Fu!!!

вернемся к запросам?

SELECT * FROM users WHERE id= Ищем Зину (rowoffset по id=123) 2. seek(rowoffset) в файле строк (.MYD) 3. read(rowdata) из файла 4. и… все – результат готов

усложним – добавим условий

SELECT * FROM users WHERE sex=F AND age>=18 AND age

индекс в лоб по sex?

keyid F12345 F12346 F12347 F12348 F12349 F12350 F12351 F12352 keyid F12353 F12354 F12355 F12356 F12357 F12358 F12359 F12360 keyid F12361 F12362 F12363 F12364 F12365 F12366 F12367 F12368 keyid F12369 F12370 F12371 F12372 F12373 F12374 F12375 F12376

keyid F12345 F12346 F12347 F12348 F12349 F12350 F12351 F12352 keyid F12353 F12354 F12355 F12356 F12357 F12358 F12359 F12360 keyid F12361 F12362 F12363 F12364 F12365 F12366 F12367 F12368 keyid F12369 F12370 F12371 F12372 F12373 F12374 F12375 F12376

они ВСЕ подходят по условию F!

…и нам надо прочитать с диска (!) 5,000,000+ строк…

…и для каждой лично проверить паспорт и age>=18 and age

keyid F12345 F12346 F12347 F12348 F12349 F12350 F12351 F12352 keyid F12353 F12354 F12355 F12356 F12357 F12358 F12359 F12360 keyid F12361 F12362 F12363 F12364 F12365 F12366 F12367 F12368 keyid F12369 F12370 F12371 F12372 F12373 F12374 F12375 F12376

неселективный индекс – косяк и западло!

sex=F AND age>=18 AND age

keyid keyid keyid но – вдруг это мужики?!

мужики нам не нужны!!!

либо опять читать ненужные строки (мужиков) – либо…

покрывающий (covering) индекс по обоим полям

keyid F, F, F, F, F, F, F, F, keyid F, F, F, F, F, M, M, M, keyid M, M, M, M, M, M, M, M,

список нужных строк – ясен сразу

чтений с диска – минимум скорости – максимум

бонус – сортировка по age

кстати, про сортировку…

SELECT * FROM users WHERE sex=F AND age>=18 AND age

как выполнять? есть варианты

налево – read_index(WHERE) + read_rows + sort_rows(ORDER)

keyid F, F, F, F, F, F, F, F, idnameCountry 12350Лена ИвановаRu 24523Шараф ХудайбердыевUz … дырка на 1000 записей … 24624Мацал КошекCz 12347Маша ПетроваUa 80356Ли Си ЦынCn … дырка еще на 2000 записей … 12351Нина СидороваRu 10756Федор ШтынRu индексданные сортировка результат

read_index – мало и быстро

10K*( bytes ) = 130 KB 5-10 ms/seek, 50+ MB/s read

read_random_rows – медленно! 10K*5-10 ms/seek = sec…

sort_rows – обычно быстро 10K*0.1-1 KB/row = 1-10 MB (in RAM)

мораль – все зло от random rows!

(еще от sort_rows, если их много)

… sex=F AND age>=18 AND age

направо – read_fat_index(WHERE) + sort_index(ORDER) + LIMIT + read_less_rows + sort_rows

нужен утолщенный INDEX ( sex, age, hotness )

вместе с поиском по sex, age – сразу узнаем hotness (+40 KB)

sort ( 10K * [ hotness, rowptr ] )

read_rows – почти не нужен (10 строк результата…)

sort_rows – вообще не нужен

PROFIT?

не панацея – даже в теории

INDEX ( sex, age, hotness ) WHERE sex=F ORDER BY hotness LIMIT 10

в теории – обработать 50% индекса затем – прочитать 10 строк (пф!)

INDEX ( sex, age, hotness ) 1M rows, ~20 MB, 50% = ~10 MB

INDEX ( sex, age, hotness ) WHERE sex=F AND hotness>0 ORDER BY age LIMIT 10

в теории – читаем индекс линейно – пока не заполним limit

что на практике?

welcome to real world

CREATE TABLE usertest ( id INTEGER PRIMARY KEY NOT NULL, sex ENUM ('m','f'), age INTEGER NOT NULL, hotness INTEGER NOT NULL, name VARCHAR(255) NOT NULL, INDEX(sex,age,hotness) )

500,000 записей 56 MB данных (.ibd файл) 32 MB innodb_buffer_pool age \in [ ] hotness \in [-5.. 5]

mysql> explain select * from usertest where sex='f' and age>=18 and age

filesort – НЕ про временный файл filesort – про сортировку строк

Using where – проверка условия НЕ по индексу – ?!!

запрос проще, точно по индексу?

mysql> explain select * from usertest where sex='f' and age=18 order by hotness desc limit 10 \G *************************** 1. row *************************** id: 1 select_type: SIMPLE table: usertest type: ref possible_keys: sex key: sex key_len: 6 ref: const,const rows: Extra: Using where (bug #30733, 30 aug 2007?) 1 row in set (0.00 sec)

проверим экспериментально!!!

mysql> select * from usertest where sex='f' and age>=18 and age select * from usertest where sex='f' and age=18 order by hotness desc limit 10; rows in set (0.05 sec)

причина?

mysql> explain select * from usertest where sex='f' and age>=18 and age

MySQL не умеет сортировать элементы индекса :(

сортировка по индексу – только если индекс гарантирует порядок

1) в куске индекса sex=F, 18

2) optimizer лажанул, 18

(теория говорит – можно лучше!)

проверяем дальше!

mysql> explain select * from usertest where sex='f' order by hotness desc limit 10 \G... key: sex key_len: 2 ref: const rows: Extra: Using where; Using filesort mysql> explain select * from usertest where sex='f' order by hotness desc limit 10 \G rows in set (20.25 sec)

и последний запрос

mysql> explain select * from usertest where sex='f' and hotness>0 order by age asc limit 10 \G... key: sex key_len: 2 ref: const rows: Extra: Using where; Using filesort mysql> select * from usertestwhere sex='f' and hotness>0 order by age asc limit 10; rows in set (0.25 sec)

итого SexAgeHotnessTimeOptimal Const=FRange=18..25Order23.05HELL NO Const=FConst=18Order0.05OK Const=F–Order20.25HELL NO Const=FOrderCond>00.25KINDA OK

теория была оптимистична…

…реальность внесла коррективы.

не учли детали реализации

1. нету досортировки индекса (MySQL specific)

2. limit обрабатывается… так себе (MySQL specific)

3. optimizer ошибается (везде и у всех)

про ошибки optimizer и спасительный full-scan

mysql> select * from usertest where sex='f' order by hotness desc limit 10; rows in set (20.25 sec) mysql> select * from usertest ignore index(sex) where sex='f' order by hotness desc limit 10; rows in set (0.55 sec)

10,000 x 10 ms = 100 sec 100,000 x 1KB / 50 M/s = 2 sec

мораль: random IO очень плохо (водка яд водка яд водка яд)

про обработку limit

теория – приоритетная очередь

приоритетная!!

технически – heap

или просто double buffer

ключевое свойство – в памяти храним только top-N

LIMIT 10 – надо хранить 10 строк

LIMIT 130,10 – надо 140

практика – MySQL vs. LIMIT

выбрать и отсортировать ВСЕ (*) * – всегда, когда индекс не гарантирует точный порядок

выбрать OK – избежать нельзя

сортировать все плохо…

лишний удар по CPU/RAM/IO :(

как убирать mysql сортировку?

строить более другие индексы

ставить более другой софт

умеет и обычный поиск!

трюки про WHERE вместо LIMIT (я не пробовал, но говорят, возможно)

…именно в таком порядке.

более практический пример?

импортируем дамп Wikipedia

XML дамп 2 толстые таблицы хочется – а) одну б) тонкую!

INSERT INTO mycontent SELECT t.old_id, p.page_id, UNIX_TIMESTAMP(p.page_touched), p.page_len, p.page_title, COMPRESS(t.old_text) FROM text t, page p WHERE t.old_id=p.page_latest AND page_namespace=0 AND page_is_redirect=0; 15 GB text, 0.5 GB page, ~4.5M rows tps=~200, bi/bo=~1 MB/sec ~200 MB.MYD in ~20 mins, ETA 10+ hrs

mysql> EXPLAIN SELECT t.old_id,... \G ********************** 1. row ********************** table: page type: ref key: name_title ref: const rows: Extra: Using where ********************** 2. row ********************** table: text type: eq_ref key: PRIMARY ref: wiki.p.page_latest rows: 1

что хотим? scan 15 GB text, join 0.5 GB page

почему не выходит? … FROM text t, page p WHERE t.old_id=p.page_latest

решение – index(page_latest)

еще пришлось STRAIGHT_JOIN (optimizer опять лажанул!)

результат – 40 минут, включая CREATE INDEX

так зачем же знать алгоритмы?

did we learn something today?

как устроено B-дерево

как работает индекс

как работают выборки

зачем нужны full-scans

как работает сортировка с LIMIT

чего можно добиться в идеале – в теории

…и как оно, бывает, не работает – на практике!

а толку?!

чего ждать от БД

чего не ждать

как и что тестировать

как объяснять потом результаты

в итоге – как заставлять таки работать

…БЫСТРО работать.

это все (с) вопросы?!