'

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

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

Who is Mr. Aksenov?


Слайд 2


Слайд 3

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


Слайд 4

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


Слайд 5


Слайд 6

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


Слайд 7


Слайд 8

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


Слайд 9


Слайд 10

<


Слайд 11

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


Слайд 12

free open source search


Слайд 13

<< free :(


Слайд 14


Слайд 15

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


Слайд 16

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


Слайд 17


Слайд 18

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


Слайд 19

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


Слайд 20

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


Слайд 21

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


Слайд 22


Слайд 23

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


Слайд 24


Слайд 25


Слайд 26

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


Слайд 27

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


Слайд 28


Слайд 29


Слайд 30

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


Слайд 31

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


Слайд 32

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


Слайд 33

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


Слайд 34

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


Слайд 35

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


Слайд 36

SELECT * FROM users WHERE id=123


Слайд 37

SELECT * FROM users WHERE lastname=‘Pupkin’


Слайд 38

SELECT * FROM users WHERE lastname LIKE ‘Pu%’


Слайд 39

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


Слайд 40

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


Слайд 41


Слайд 42

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


Слайд 43

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


Слайд 44

нас спасут…


Слайд 45


Слайд 46

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


Слайд 47

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


Слайд 48

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


Слайд 49


Слайд 50


Слайд 51


Слайд 52


Слайд 53


Слайд 54

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


Слайд 55

hash index


Слайд 56

R-tree index


Слайд 57

full-text index


Слайд 58

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


Слайд 59

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


Слайд 60

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


Слайд 61

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


Слайд 62


Слайд 63


Слайд 64


Слайд 65


Слайд 66

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


Слайд 67

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


Слайд 68

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


Слайд 69

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


Слайд 70

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


Слайд 71

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


Слайд 72

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


Слайд 73

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


Слайд 74

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


Слайд 75

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


Слайд 76


Слайд 77


Слайд 78


Слайд 79


Слайд 80


Слайд 81


Слайд 82

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


Слайд 83

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


Слайд 84

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


Слайд 85


Слайд 86

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


Слайд 87

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


Слайд 88

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


Слайд 89

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


Слайд 90

вставляем…


Слайд 91

вставляем…


Слайд 92

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


Слайд 93

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


Слайд 94

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


Слайд 95

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


Слайд 96

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


Слайд 97


Слайд 98

B-tree Kung Fu!!!


Слайд 99

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


Слайд 100

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


Слайд 101

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


Слайд 102

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


Слайд 103

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


Слайд 104


Слайд 105


Слайд 106

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


Слайд 107


Слайд 108

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


Слайд 109

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


Слайд 110


Слайд 111

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


Слайд 112

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


Слайд 113

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


Слайд 114

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


Слайд 115

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


Слайд 116

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


Слайд 117


Слайд 118

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


Слайд 119

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


Слайд 120

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


Слайд 121

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


Слайд 122

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


Слайд 123

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


Слайд 124


Слайд 125

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


Слайд 126

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


Слайд 127

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


Слайд 128

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


Слайд 129

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


Слайд 130

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


Слайд 131

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


Слайд 132

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


Слайд 133


Слайд 134

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


Слайд 135

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


Слайд 136

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


Слайд 137

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


Слайд 138

sort ( 10K * [ hotness, rowptr ] )


Слайд 139

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


Слайд 140

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


Слайд 141

PROFIT?


Слайд 142

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


Слайд 143

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


Слайд 144

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


Слайд 145

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


Слайд 146

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


Слайд 147

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


Слайд 148

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


Слайд 149

welcome to real world


Слайд 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) )


Слайд 151

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


Слайд 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)


Слайд 153

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


Слайд 154

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


Слайд 155

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


Слайд 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)


Слайд 157

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


Слайд 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)


Слайд 159

причина?


Слайд 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)


Слайд 161

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


Слайд 162

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


Слайд 163

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


Слайд 164

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


Слайд 165

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


Слайд 166

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


Слайд 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)


Слайд 168

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


Слайд 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)


Слайд 170

итого


Слайд 171

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


Слайд 172

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


Слайд 173

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


Слайд 174

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


Слайд 175

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


Слайд 176

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


Слайд 177

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


Слайд 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)


Слайд 179

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


Слайд 180

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


Слайд 181

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


Слайд 182

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


Слайд 183


Слайд 184


Слайд 185

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


Слайд 186


Слайд 187

или просто double buffer


Слайд 188


Слайд 189


Слайд 190

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


Слайд 191

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


Слайд 192

LIMIT 130,10 – надо 140


Слайд 193

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


Слайд 194

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


Слайд 195

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


Слайд 196


Слайд 197

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


Слайд 198


Слайд 199

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


Слайд 200

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


Слайд 201

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


Слайд 202

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


Слайд 203

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


Слайд 204

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


Слайд 205

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


Слайд 206

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


Слайд 207

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


Слайд 208

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


Слайд 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


Слайд 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


Слайд 211

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


Слайд 212

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


Слайд 213

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


Слайд 214

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


Слайд 215

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


Слайд 216


Слайд 217

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


Слайд 218

“did we learn something today?”


Слайд 219


Слайд 220

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


Слайд 221

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


Слайд 222

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


Слайд 223

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


Слайд 224

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


Слайд 225

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


Слайд 226

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


Слайд 227

а толку?!


Слайд 228

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


Слайд 229

чего не ждать


Слайд 230

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


Слайд 231

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


Слайд 232


Слайд 233

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


Слайд 234


Слайд 235

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


Слайд 236

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


×

HTML:





Ссылка: