Hello, freemanzav!
freemanzav wrote:
А вроде битовый массив создается. Для
чего сортировать номера записей?
чтобы выбирать записи с диска в наиболее
оптимальном порядке. Ключи отсортированы
по своему, а записи лежат как попало.
Если номера записей, полученные из ключей
не сортировать, то тогда при выборке по индексу
сервер будет "скакать" по страницам.
Эти "скачки" происходят при
ORDER BY по индексу, когда сервер вынужден
перебирать ключи в порядке индекса и по мере
перебора вытаскивать записи с диска.
Поэтому примерно в половине случаев ORDER BY
по индексу хуже чем ORDER BY с сортировкой -
при order by по индексу при большом числе
записей страницы вытесняются из кэша, и конечный
IO может быть много выше чем прямая сортировка.
у меня есть пример под это дело, я публиковал
его на sql.ru:
Производительность сортировки и выборки в порядке индекса
----------------------------------------------------------
Давайте попробуем на практике проверить тезисы, которые были выдвинуты в
конце предыдущего раздела. Для сравнения взята таблица с 14 миллионами
записей (средний размер записи 117 байт, общий объем таблицы 1.86
гигабайт). По данной таблице есть 2 индекса с разной селективностью
(информация скопирована из IBAnalyst. тест проводился на Firebird 1.5.2 SS)
Index Depth Keys Key Len Max Dup Total Dup Uniques Selectivity Size, mb
A 3 14287963 0.00 4827799 14286515 1448 0.0006906 82.03
B 3 14287963 1.00 100 6573235 7714728 0.0000001 99.52
Как видно из таблицы, индексы A и B по объему примерно одинаковы (по
числу ключей они идентичны), однако по числу уникальных ключей сильно
отличаются. Индекс B имеет большое число разных ключей и высокую
селективность, а индекс A - всего 1448 разных значений ключей. Причем,
индекс A при равномерном распределении этих уникальных значений имел бы
по ~10 тысяч одинаковых ключей (для каждого уникального значения -
Keys/Uniques), однако наблюдается явный перекос, то есть число ключей в
этом индексе с каким-то одним значением равно ~4.8 миллионов (MaxDup) -
это треть от общего числа ключей.
У индекса B максимальное количество одинаковых ключей равно 100, поэтому
относительно общего числа ключей этот индекс можно считать почти уникальным.
Для начала имеет смысл выполнить запрос
select count(*) from table
который не будет использовать индексы и даст возможность оценить время
выполнения запросов с использованием индексов.
Prepare time = 0ms
Execute time = 42s 500ms
Avg fetch time = 42 500.00 ms
Current memory = 1 095 520
Max memory = 19 360 784
Memory buffers = 2 048
Reads from disk to cache = 118 792
Writes from cache to disk = 6
Fetches from cache = 28 814 893
Теперь выполним 2 запроса, которые для группировки будут использовать
индексы A и B (планы запросов выбирает сервер). Эти запросы "тяжелее"
простого count по всей таблице, т.к. им нужно подсчитать число
одинаковых записей по каждой группе разных значений столбца:
SELECT A, COUNT(A)
FROM TABLE
GROUP BY A
PLAN (TABLE ORDER A)
Prepare time = 0ms
Execute time = 45m 55s 469ms
Avg fetch time = 153 081.61 ms
Current memory = 19 225 868
Max memory = 19 275 704
Memory buffers = 2 048
Reads from disk to cache = 3 733 434
Writes from cache to disk = 0
Fetches from cache = 42 869 143
SELECT B, COUNT(B)
FROM TABLE
GROUP BY B
PLAN (TABLE ORDER B)
Prepare time = 0ms
Execute time = 63ms
Avg fetch time = 3.50 ms
Current memory = 1 105 516
Max memory = 19 360 784
Memory buffers = 2 048
Reads from disk to cache = 48
Writes from cache to disk = 0
Fetches from cache = 12 495
Разница кажется фантастической. Обратите внимание, что в первом случае
сервер произвел 3.7 миллионов чтений страниц с диска, когда сама таблица
занимает на диске 118.7 тысяч страниц, а индекс - 5250 страниц. Об этом
эффекте было сказано в начале данного раздела - чтение в порядке индекса
приводит к постоянному вытеснению страниц из кэша, и ускорить этот
запрос можно только усовершенствованием дисковой подсистемы сервера.
Одновременно мы имеем обратный эффект - уникальных значений в индексе A
всего 1448, поэтому после того как запрос выполнился, он, фактически,
выдал нам сразу весь результат. Второй запрос, с выборкой в порядке
индекса B, несмотря на мгновенность выполнения выдает только часть
записей в grid, поэтому то же самое считывание страниц и их вытеснение
из кэша может начаться по мере того, как пользователь будет нажимать в
DBGrid кнопку PageDn (или стрелку вниз). То есть, первый запрос работает
дольше, но выдает весь результат почти сразу, а второй запрос работает
моментально, но будет "тормозить" по мере выдаче результата.
Теперь попробуем отключить использование индекса в первом запросе, и
посмотреть - будет ли быстрее и эффективнее использование файла
сортировки. Все равно этот запрос уже показал себя как "медленно
выдающий результат", а явная сортировка записей как раз и будет иметь
этот эффект из-за нескольких фаз выполнения такого запроса (считывание,
сортировка, выдача результата).
SELECT A+0, COUNT(A)
FROM TABLE
GROUP BY 1
Если во время выполнения первого и второго запросов сервер занимал 58
мегабайт памяти, то при выполнении он занял 102 мегабайта (задействованы
другие механизмы). И, что самое главное, целиком запрос выполнился за 2
минуты!
PLAN SORT ((A NATURAL))
------ Performance info ------
Prepare time = 0ms
Execute time = 2m 5s 485ms
Avg fetch time = 6 971.39 ms
Current memory = 1 098 708
Max memory = 19 360 784
Memory buffers = 2 048
Reads from disk to cache = 118 757
Writes from cache to disk = 0
Fetches from cache = 28 813 410
Обратите внимание на статистику - она практически идентична запросу,
который осуществляет select count по всей таблице без группировки. Но -
когда мы получаем первую запись из этого запроса, никакого "торможения"
при выдаче остальных записей уже нет и быть не может (в отличие от
запроса с группировкой по B). То есть, сортировка "на диске" явно
эффективнее выборки в порядке индекса. В процессе сортировки сервер
создал на диске временный файл размером 322 мегабайта
Теперь повторим запрос для столбца B, который возвращает порядка 7-ми
миллионов записей (число уникальных значений в этом столбце), и для
которого, понятно, умолчательного размера сортировки в памяти не хватит:
SELECT B+0, COUNT(B)
FROM TABLE
GROUP BY 1
Статистика запроса практически идентичная (план тоже), я даже не буду
здесь ее приводить. Разница между этим и предыдущим запросом только в
том, что в случае столбца A группировка привела к образованию малого
количества записей (результат группировки помещается в память), и файл
сортировки был удален сервером в момент выдачи первой записи запроса. В
случае столбца B, поскольку количество выдаваемых записей велико (7
миллионов), файл сортировки (того же размера, что и в предыдущем случае)
остается на диске до тех пор, пока все записи не будут выбраны, или
запрос не будет закрыт.
--
Dmitri Kouzmenko, www.ibase.ru, (495) 953-13-34
