Производительность сортировки и выборки в порядке индекса

Запросы, планы, оптимизация запросов, ...

Модераторы: kdv, CyberMax

Ответить
kdv
Forum Admin
Сообщения: 6595
Зарегистрирован: 25 окт 2004, 18:07

Производительность сортировки и выборки в порядке индекса

Сообщение kdv » 25 дек 2007, 18:20

Это не вопрос. Это один кусочек статьи.

Производительность сортировки и выборки в порядке индекса

Давайте попробуем на практике проверить тезисы, которые были выдвинуты в конце предыдущего раздела. Для сравнения взята таблица с 14 миллионами записей (средний размер записи 117 байт, общий объем таблицы 1.86 гигабайт). По данной таблице есть 2 индекса с разной селективностью (информация скопирована из IBAnalyst. тест проводился на Firebird 1.5.2 SS)

Код: Выделить всё

Index Depth Keys  KeyLen  MaxDup TotalDup  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, поэтому то же самое считывание страниц и их вытеснение из кэша может начаться по мере того, как пользователь будет нажимать в grid кнопку 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 миллионов), файл сортировки (того же размера, что и в предыдущем случае) остается на диске до тех пор, пока все записи не будут выбраны, или запрос не будет закрыт.

kdv
Forum Admin
Сообщения: 6595
Зарегистрирован: 25 окт 2004, 18:07

Сообщение kdv » 25 дек 2007, 18:33

резюме для тех, кто не понял смысл:

1. сортировка большого количества записей на диске эффективнее и меньше нагружает сервер, чем выборка в порядке индекса
2. сортировка на диске занимает некоторое время, но не нагружает ввод-вывод при получении результата
3. выборка "в порядке индекса" моментально выдает первую порцию записей, но "тормозит" и создает высокий дисковый ввод-вывод по мере выборки остальных записей
4. для небольшого количества записей "стоимость" сортировки на диске или выборки в порядке индекса может быть одинаковой.

marcodor
Сообщения: 9
Зарегистрирован: 09 мар 2010, 23:49

Re: Производительность сортировки и выборки в порядке индекса

Сообщение marcodor » 11 мар 2010, 12:57

SELECT A, COUNT(A)
FROM TABLE
GROUP BY A
PLAN (TABLE ORDER A)
Видим что занимает 42мин. А почему собственно он не считает каунт по индексу а сначала сортирует данные и потом считает каунт по данных?
Здесь пример более теоретический, врядли придется такое делать, на таком массиве данных. Для других целей, индекс по А может по полному оправдовать себя ;)

kdv
Forum Admin
Сообщения: 6595
Зарегистрирован: 25 окт 2004, 18:07

Re: Производительность сортировки и выборки в порядке индекса

Сообщение kdv » 11 мар 2010, 15:46

А почему собственно он не считает каунт по индексу
потому что в ключах индекса нет информации о транзакциях, и невозможно понять, какую запись (версию) можно видеть этой транзакции, а какую - нет.
Здесь пример более теоретический, врядли придется такое делать, на таком массиве данных.
пример не теоретический, а упрощенный. в реальной жизни вполне встречается.
Для других целей, индекс по А может по полному оправдовать себя
может, я с этим не спорю. Я объяснил механизмы, и как они влияют на производительность.

marcodor
Сообщения: 9
Зарегистрирован: 09 мар 2010, 23:49

Re: Производительность сортировки и выборки в порядке индекс

Сообщение marcodor » 12 мар 2010, 11:22

потому что в ключах индекса нет информации о транзакциях
Хм... Я думал что есть. Получается, что когда движок читает по индексу и ищет запись в секторе данных то могут быть и холостые попытки ;) если транзакций / изменений много.

kdv
Forum Admin
Сообщения: 6595
Зарегистрирован: 25 окт 2004, 18:07

Re: Производительность сортировки и выборки в порядке индекс

Сообщение kdv » 12 мар 2010, 11:53

не в секторе а в странице, но да.

берем n записей, и индексированный столбец. удаляем, commit. Ищем по индексу - если мусор еще никем не убран (есть транзакция snapshot, стартовавшая до удаления), то все ключи на месте, и индекс будет использоваться, но только при просмотре записей новые транзакции обнаружат, что записи уже удалены.

Ответить