'

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

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





Слайд 1

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


Слайд 2

Who is Mr. Aksenov?


Слайд 3


Слайд 4

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


Слайд 5

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


Слайд 6


Слайд 7

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


Слайд 8


Слайд 9

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


Слайд 10


Слайд 11

<


Слайд 12

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


Слайд 13

free open source search


Слайд 14

<< free :(


Слайд 15


Слайд 16

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


Слайд 17

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


Слайд 18


Слайд 19

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


Слайд 20

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


Слайд 21

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


Слайд 22

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


Слайд 23


Слайд 24

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


Слайд 25


Слайд 26


Слайд 27

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


Слайд 28

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


Слайд 29


Слайд 30


Слайд 31

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


Слайд 32

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


Слайд 33

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


Слайд 34

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


Слайд 35

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


Слайд 36

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


Слайд 37

SELECT * FROM users WHERE id=123


Слайд 38

SELECT * FROM users WHERE lastname=‘Pupkin’


Слайд 39

SELECT * FROM users WHERE lastname LIKE ‘Pu%’


Слайд 40

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


Слайд 41

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


Слайд 42


Слайд 43

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


Слайд 44

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


Слайд 45

нас спасут…


Слайд 46


Слайд 47

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


Слайд 48

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


Слайд 49

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


Слайд 50


Слайд 51


Слайд 52


Слайд 53


Слайд 54


Слайд 55

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


Слайд 56

hash index


Слайд 57

R-tree index


Слайд 58

full-text index


Слайд 59

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


Слайд 60

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


Слайд 61

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


Слайд 62

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


Слайд 63


Слайд 64


Слайд 65


Слайд 66


Слайд 67

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


Слайд 68

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


Слайд 69

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


Слайд 70

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


Слайд 71

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


Слайд 72

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


Слайд 73

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


Слайд 74

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


Слайд 75

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


Слайд 76

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


Слайд 77


Слайд 78


Слайд 79


Слайд 80


Слайд 81


Слайд 82


Слайд 83

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


Слайд 84

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


Слайд 85

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


Слайд 86


Слайд 87

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


Слайд 88

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


Слайд 89

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


Слайд 90

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


Слайд 91

вставляем…


Слайд 92

вставляем…


Слайд 93

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


Слайд 94

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


Слайд 95

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


Слайд 96

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


Слайд 97

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


Слайд 98


Слайд 99

B-tree Kung Fu!!!


Слайд 100

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


Слайд 101

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


Слайд 102

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


Слайд 103

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


Слайд 104

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


Слайд 105


Слайд 106


Слайд 107

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


Слайд 108


Слайд 109

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


Слайд 110

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


Слайд 111


Слайд 112

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


Слайд 113

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


Слайд 114

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


Слайд 115

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


Слайд 116

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


Слайд 117

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


Слайд 118


Слайд 119

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


Слайд 120

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


Слайд 121

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


Слайд 122

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


Слайд 123

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


Слайд 124

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


Слайд 125


Слайд 126

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


Слайд 127

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


Слайд 128

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


Слайд 129

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


Слайд 130

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


Слайд 131

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


Слайд 132

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


Слайд 133

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


Слайд 134


Слайд 135

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


Слайд 136

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


Слайд 137

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


Слайд 138

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


Слайд 139

sort ( 10K * [ hotness, rowptr ] )


Слайд 140

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


Слайд 141

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


Слайд 142

PROFIT?


Слайд 143

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


Слайд 144

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


Слайд 145

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


Слайд 146

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


Слайд 147

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


Слайд 148

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


Слайд 149

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


Слайд 150

welcome to real world


Слайд 151

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


Слайд 152

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


Слайд 153

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)


Слайд 154

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


Слайд 155

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


Слайд 156

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


Слайд 157

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)


Слайд 158

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


Слайд 159

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)


Слайд 160

причина?


Слайд 161

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)


Слайд 162

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


Слайд 163

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


Слайд 164

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


Слайд 165

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


Слайд 166

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


Слайд 167

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


Слайд 168

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)


Слайд 169

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


Слайд 170

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)


Слайд 171

итого


Слайд 172

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


Слайд 173

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


Слайд 174

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


Слайд 175

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


Слайд 176

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


Слайд 177

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


Слайд 178

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


Слайд 179

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)


Слайд 180

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


Слайд 181

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


Слайд 182

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


Слайд 183

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


Слайд 184


Слайд 185


Слайд 186

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


Слайд 187


Слайд 188

или просто double buffer


Слайд 189


Слайд 190


Слайд 191

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


Слайд 192

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


Слайд 193

LIMIT 130,10 – надо 140


Слайд 194

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


Слайд 195

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


Слайд 196

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


Слайд 197


Слайд 198

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


Слайд 199


Слайд 200

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


Слайд 201

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


Слайд 202

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


Слайд 203

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


Слайд 204

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


Слайд 205

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


Слайд 206

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


Слайд 207

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


Слайд 208

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


Слайд 209

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


Слайд 210

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


Слайд 211

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


Слайд 212

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


Слайд 213

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


Слайд 214

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


Слайд 215

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


Слайд 216

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


Слайд 217


Слайд 218

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


Слайд 219

“did we learn something today?”


Слайд 220


Слайд 221

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


Слайд 222

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


Слайд 223

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


Слайд 224

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


Слайд 225

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


Слайд 226

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


Слайд 227

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


Слайд 228

а толку?!


Слайд 229

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


Слайд 230

чего не ждать


Слайд 231

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


Слайд 232

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


Слайд 233


Слайд 234

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


Слайд 235


Слайд 236

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


Слайд 237

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


×

HTML:





Ссылка: