Зачем знать алгоритмы


The Presentation inside:

Slide 0

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


Slide 1

Who is Mr. Aksenov?


Slide 2


Slide 3

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


Slide 4

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


Slide 5


Slide 6

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


Slide 7


Slide 8

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


Slide 9


Slide 10

<


Slide 11

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


Slide 12

free open source search


Slide 13

<< free :(


Slide 14


Slide 15

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


Slide 16

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


Slide 17


Slide 18

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


Slide 19

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


Slide 20

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


Slide 21

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


Slide 22


Slide 23

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


Slide 24


Slide 25


Slide 26

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


Slide 27

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


Slide 28


Slide 29


Slide 30

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


Slide 31

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


Slide 32

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


Slide 33

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


Slide 34

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


Slide 35

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


Slide 36

SELECT * FROM users WHERE id=123


Slide 37

SELECT * FROM users WHERE lastname=‘Pupkin’


Slide 38

SELECT * FROM users WHERE lastname LIKE ‘Pu%’


Slide 39

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


Slide 40

SELECT * FROM users WHERE sex=‘F’ AND age>=18 AND age<=25


Slide 41


Slide 42

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


Slide 43

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


Slide 44

нас спасут…


Slide 45


Slide 46

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


Slide 47

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


Slide 48

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


Slide 49


Slide 50


Slide 51


Slide 52


Slide 53


Slide 54

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


Slide 55

hash index


Slide 56

R-tree index


Slide 57

full-text index


Slide 58

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


Slide 59

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


Slide 60

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


Slide 61

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


Slide 62


Slide 63


Slide 64


Slide 65


Slide 66

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


Slide 67

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


Slide 68

(B-дерево; странички; масштаб 1:72)


Slide 69

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


Slide 70

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


Slide 71

Листовые = ключи + соотв-е им данные (eg. row_offset) { key1, data1, key2, data2, … }


Slide 72

Промежуточные Листовые


Slide 73

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


Slide 74

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


Slide 75

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


Slide 76


Slide 77


Slide 78


Slide 79


Slide 80


Slide 81


Slide 82

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


Slide 83

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


Slide 84

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


Slide 85


Slide 86

– В жизни – под 1000 (а не 3) записей на страничку – Два уровня страничек – 1000*1000 – миллион – Три уровня – миллиард… – Итого 2-3 странички max – практически всегда


Slide 87

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


Slide 88

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


Slide 89

странички обычно НЕ полны


Slide 90

вставляем…


Slide 91

вставляем…


Slide 92

вставляем… оп-па, некуда!!


Slide 93

создаем новую страничку


Slide 94

создаем новую страничку


Slide 95

…и суем “ее” в родителя


Slide 96

это все – тоже трогаем max 2-3 странички


Slide 97


Slide 98

B-tree Kung Fu!!!


Slide 99

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


Slide 100

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


Slide 101

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


Slide 102

SELECT * FROM users WHERE sex=‘F’ AND age>=18 AND age<=25


Slide 103

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


Slide 104


Slide 105


Slide 106

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


Slide 107


Slide 108

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


Slide 109

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


Slide 110


Slide 111

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


Slide 112

sex=‘F’ AND age>=18 AND age<=25 индекс “по лбу” по age?


Slide 113

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


Slide 114

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


Slide 115

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


Slide 116

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


Slide 117


Slide 118

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


Slide 119

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


Slide 120

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


Slide 121

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


Slide 122

SELECT * FROM users WHERE sex=‘F’ AND age>=18 AND age<=25 ORDER BY hotness DESC LIMIT 10


Slide 123

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


Slide 124


Slide 125

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


Slide 126

индекс данные сортировка результат


Slide 127

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


Slide 128

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


Slide 129

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


Slide 130

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


Slide 131

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


Slide 132

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


Slide 133


Slide 134

… sex=‘F’ AND age>=18 AND age<=25 ORDER BY hotness DESC LIMIT 10


Slide 135

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


Slide 136

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


Slide 137

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


Slide 138

sort ( 10K * [ hotness, rowptr ] )


Slide 139

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


Slide 140

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


Slide 141

PROFIT?


Slide 142

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


Slide 143

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


Slide 144

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


Slide 145

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


Slide 146

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


Slide 147

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


Slide 148

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


Slide 149

welcome to real world


Slide 150

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) )


Slide 151

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


Slide 152

mysql> explain select * from usertest where sex='f' and age>=18 and age<=25 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: 2 ref: const rows: 25119 Extra: Using where; Using filesort 1 row in set (0.00 sec)


Slide 153

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


Slide 154

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


Slide 155

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


Slide 156

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: 10386 Extra: Using where (bug #30733, 30 aug 2007?) 1 row in set (0.00 sec)


Slide 157

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


Slide 158

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


Slide 159

причина?


Slide 160

mysql> explain select * from usertest where sex='f' and age>=18 and age<=25 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: 2 ? используется только начало, поле “sex”!!! ref: const rows: 25119 Extra: Using where; Using filesort ? так и есть :( 1 row in set (0.00 sec)


Slide 161

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


Slide 162

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


Slide 163

1) в куске индекса sex=F, 18<=age<=25 порядок hotness desc НЕ гарантирован


Slide 164

2) optimizer лажанул, 18<=age<=25 считается НЕ по индексу (а могло бы)


Slide 165

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


Slide 166

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


Slide 167

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


Slide 168

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


Slide 169

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: 226072 Extra: Using where; Using filesort mysql> select * from usertest where sex='f' and hotness>0 order by age asc limit 10; ... 10 rows in set (0.25 sec)


Slide 170

итого


Slide 171

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


Slide 172

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


Slide 173

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


Slide 174

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


Slide 175

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


Slide 176

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


Slide 177

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


Slide 178

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


Slide 179

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


Slide 180

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


Slide 181

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


Slide 182

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


Slide 183


Slide 184


Slide 185

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


Slide 186


Slide 187

или просто double buffer


Slide 188


Slide 189


Slide 190

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


Slide 191

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


Slide 192

LIMIT 130,10 – надо 140


Slide 193

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


Slide 194

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


Slide 195

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


Slide 196


Slide 197

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


Slide 198


Slide 199

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


Slide 200

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


Slide 201

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


Slide 202

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


Slide 203

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


Slide 204

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


Slide 205

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


Slide 206

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


Slide 207

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


Slide 208

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


Slide 209

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


Slide 210

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


Slide 211

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


Slide 212

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


Slide 213

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


Slide 214

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


Slide 215

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


Slide 216


Slide 217

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


Slide 218

“did we learn something today?”


Slide 219


Slide 220

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


Slide 221

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


Slide 222

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


Slide 223

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


Slide 224

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


Slide 225

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


Slide 226

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


Slide 227

а толку?!


Slide 228

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


Slide 229

чего не ждать


Slide 230

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


Slide 231

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


Slide 232


Slide 233

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


Slide 234


Slide 235

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


Slide 236

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


×

HTML:





Ссылка: