Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Агрегаты Min, Max при группировке на "хорошем" индексе  [new]
Mnior
Member

Откуда: Кишинёв
Сообщений: 6723
Заранее звиняюсь за занудство и дотошный детский сад.
Есть индекс {[Group],[Date]} и запрос:
SELECT	 [Group]
	,Min([Date])
FROM	@Table
GROUP BY [Group]
На котором наблюдаем афигитительно неэффективную (на мой взгляд) работу - полное сканирование индекса. Т.е. начиная с первого элемента списка (или подобия его) индекса мы тупо next за next просматриваем его весь.
Теперь вспомним работу сика - пробежка вдоль всего B-tree (ну что-то наподобие его), т.е. делая условия на каждом уровне этого дерева, всё больше углубляемся до нужного элемента списка индекса. А теперь давайте расширим алхаридм его работы. Представим, что seek может остановиться на любом своём уровне. Далее он будет не входить дальше, а переходить "влево" к соседнему элементу дерева тогоже уровня, после окончания просмотра он может "вернуться" на уровень выше, и взяться за следующую подветку, и т.д. А теперь представим, что на нашем индексе, уровень грубины будет заканчиваться на [Group]. Далее, останавливаясь на каждом этом уровне [Group] он будет делать один единственный seek до конца, но потом сразу резко возвращаться назад, переходя к очередной ветке [Group]. Какой будет этот seek? А вот какой: в зависимости от условия Min или Max, воспользуемся стандартным механизмом Begin или End range seek. Замечательно то, что можно иметь предикат, типа имея Min([Date]) и [Date] >= @Date, можно "спускаться вдоль @Date".
Теперь вопрос, почему этого не наблюдается. Слишком сложно в реализации? Или вообще неприемлемо на основе каких-то неучтённых мной механизмов и структуры работы индекса (или ваще представление в корне неверно :) )? Или слишком сложно впихнуть этот механизм в математику оптимизации запросов или неоправданно расширяет комбинаторику выбора планов? Или простой коррелированный подзапрос не будет (особо) медленне, чем ентот мэханызм (не верю)?

Да, я понимаю, не всё так просто. При обычном seek-е, углублясь в дереве, не надо хранить ссылки всех его уровней (чтоб моно было "вернуться" назад на верхний уровень). Но, неужели механизм настолько громозкий или из-за глубины индекса надо отводить много памяти под стек ссылок (всех уровней [Group]), что легче просканить весь индекс (не верю)?
С другой стороны, если количество подветок [Date] для каждой ветки [Group] несопоставимо мало (например крайняк - по одному), то явно очевидно, что эти seek-и несравнимо дороги. Но есть же статистика, по ней моно определить грань, когда лучше полностью сканить, а кода "поверхностно".

А теперь "Ответьте на мной поставленый вопрос"! :)
Ну или пихните по нужной ссылке.
29 сен 08, 21:46    [6242812]     Ответить | Цитировать Сообщить модератору
 Re: Агрегаты Min, Max при группировке на "хорошем" индексе  [new]
tpg
Member

Откуда: Novosibirsk
Сообщений: 23902
Mnior
На котором наблюдаем афигитительно неэффективную (на мой взгляд) работу - полное сканирование индекса.
А чо странного то? Условия отбора у вас в запросе нигде не наблюдается.

https://www.sql.ru/articles/mssql/03013101Indexes.shtml

Сообщение было отредактировано: 30 сен 08, 06:24
30 сен 08, 06:24    [6243304]     Ответить | Цитировать Сообщить модератору
 Re: Агрегаты Min, Max при группировке на "хорошем" индексе  [new]
Glory
Member

Откуда:
Сообщений: 104760
Mnior
Какой будет этот seek? А вот какой: в зависимости от условия Min или Max, воспользуемся стандартным механизмом Begin или End range seek. Замечательно то, что можно иметь предикат, типа имея Min([Date]) и [Date] >= @Date, можно "спускаться вдоль @Date".
Теперь вопрос, почему этого не наблюдается. Слишком сложно в реализации? Или вообще неприемлемо на основе каких-то неучтённых мной механизмов и структуры работы индекса (или ваще представление в корне неверно :) )?

По-моему, то, что вы предлагаете, называется рекурсией. Реализовать ее не сложно. Только будет ли она выгоднеее в плане ресурсов простого сканирования, по-моему не факт. Ведь стек вызова придется хранить, промежуточные результаты тоже. А при сканировании знай себе читай индекс
30 сен 08, 10:11    [6243782]     Ответить | Цитировать Сообщить модератору
 Re: Агрегаты Min, Max при группировке на "хорошем" индексе  [new]
Mnior
Member

Откуда: Кишинёв
Сообщений: 6723
Кажись, даже если программисты захотят добавить это в функционал, то всё равно в релиз не попадёт. А смысл, если это моно просто обойти. Да, отхватит лишний кусок памяти винтов и оперативы, ну и что - они дешёвые, зато готовый механизм есть: индексы на вьюхах. Чтение будет мгновенным, хотя изменение данных притормозятся.
А как же стремление уменьшить размер использования дискового пространства за счёт процессорного времени и оперативы (архивацию данных в массы). А так на основе уже имеющегося индекса и алгоритма - и овцы и волки... Нет, маркетологи это всё задавят ...

tpg
Условия отбора у вас в запросе нигде не наблюдается.
https://www.sql.ru/articles/mssql/03013101Indexes.shtml
"Условия отбора" не понял, но за ссылку спасибо. Ступил, надо было перечитать, подумать, а потом тему создавать.

Список сбалансирован, поэтому "уровень [Group]" и "линия разделения [Group]-[Date]" - это бред. Далее неизвестно - на этой 8k-ой странице индекса записи расположены в бинарном дереве или таблицей? Т.е. чтоб перейти к очередному [Group] надо "пройтись" по всем элементам страницы или юзать Bit-Tree? Если Bit-tree нету, то алгоритм более бесполезен. Ага, "переходы" от одного подключа [Group] к очередному могут "происходить" только на листьевых страницах индекса.

Так, опишу основной критерий полезности. Если при поиске очередного элемента [Group] часто пропускаются целые индексные страницы, то смысл ещё есть. А если большей частью "сканятся" все "листьевые" станицы индекса - то ну его этот метод. Т.е. если количество елементов [Group] намного меньше чем количество "листьевых" страниц индекса, то ещё не всё потеряно. :)
Как мы можем заранее узнать, что на дочерних страницах есть "переход"? Очень просто, если следующий элемент на этом уровне страницы индекса имеет отличный подключ [Group].

Допустим страница выглядит так:
Key
A1
A2
B3
B4
B5
D1
F2
F3
F4
Первое вхождение A1 читаем в любом случае, далее A2, потом B5 и D1. А B3, B4, F3, F4 нам не интересны. Где и какие "переходы":
KeyChange Sub-Key
A1NULL-A
A2A-B
B3Skip
B4Skip
B5B-C-D
D1D-E-F
F2Skip
F3Skip
F4Skip
Такой метод надо использовать на всех не листьевых страницах, а на листьевых меняем только одно, считываем запись если предыдущий (а не следующий) подкдюч отличен. Ну, зависит от порядка сортировки (Min или Мах).

Каков ещё нужен критерий - средная процесорно-оперативная стоимость поиска одного "перехода" должно быть дешевле, чем топорное сканирование среднего количества "пропущеных" страниц. А тут ещё замешано среднее попадание в кеш страниц. А ещё математика блокировок. Ну это задача для "нобелей". :)
Всё, пора сделать паузу.

Что ещё не учтено в обновлённой схеме алхоридма?
30 сен 08, 17:56    [6247437]     Ответить | Цитировать Сообщить модератору
 Re: Агрегаты Min, Max при группировке на "хорошем" индексе  [new]
Mnior
Member

Откуда: Кишинёв
Сообщений: 6723
Mnior
готовый механизм есть: индексы на вьюхах
Ха. Совсем забыл, индекс на вьюхе не должен содержать Min/Max! Так что аргументов за существование мэханизма больше.

Кто у нас знает буржуйский и сможет написать предложение (feedback) микрософту?
7 окт 08, 14:05    [6273980]     Ответить | Цитировать Сообщить модератору
 Re: Агрегаты Min, Max при группировке на "хорошем" индексе  [new]
Maxx
Member [скрыт]

Откуда:
Сообщений: 24290
Жжеш, прочитай ссылку которую дали
потом составляй письма турецкому султану (па добраму ессно)
-------------------------------------
Jedem Das Seine
7 окт 08, 14:11    [6274019]     Ответить | Цитировать Сообщить модератору
 Re: Агрегаты Min, Max при группировке на "хорошем" индексе  [new]
Mnior
Member

Откуда: Кишинёв
Сообщений: 6723
Maxx
Жжеш, прочитай ссылку которую дали
Скорострел ты наш, сам"Жжеш", если бы ты был внимательным и не торопливым, ты б понял, что: во первых, я повторно читал по вышеуказаной ссылке, во вторых спросил канкретна "Что ещё не учтено?".
7 окт 08, 15:58    [6274822]     Ответить | Цитировать Сообщить модератору
 Re: Агрегаты Min, Max при группировке на "хорошем" индексе  [new]
Mnior
Member

Откуда: Кишинёв
Сообщений: 6723
Ой прости Maxx, я не сразу посмотрел, в каких форумах ты ошиваешься - тогдась просто проигнорировал.
7 окт 08, 16:00    [6274848]     Ответить | Цитировать Сообщить модератору
 Re: Агрегаты Min, Max при группировке на "хорошем" индексе  [new]
Кудряшка
Member

Откуда: Сидней
Сообщений: 2219
С этого места пож поподробнее - ушла за попкорном
7 окт 08, 16:18    [6275007]     Ответить | Цитировать Сообщить модератору
 Re: Агрегаты Min, Max при группировке на "хорошем" индексе  [new]
Гавриленко Сергей Алексеевич
Member

Откуда: Moscow
Сообщений: 37050
За "поподробнее" тему закрою. Так что не надо переходить на личности и устраивать здесь флуд.
7 окт 08, 16:19    [6275023]     Ответить | Цитировать Сообщить модератору
 Re: Агрегаты Min, Max при группировке на "хорошем" индексе  [new]
Mnior
Member

Откуда: Кишинёв
Сообщений: 6723
Кста, хотелось бы (губа не дура), услышать, что вы думаете, Гавриленко Сергей Алексеевич, по поводу темы? А то вот почти никто особо не вникает в её проблематику ...
7 окт 08, 16:43    [6275248]     Ответить | Цитировать Сообщить модератору
Между сообщениями интервал более 1 года.
 Re: Агрегаты Min, Max при группировке на "хорошем" индексе  [new]
Mnior
Member

Откуда: Кишинёв
Сообщений: 6723
По данному подходу есть тема "skip scan".
Есть даже Suggestion на connect: Implement Index Skip Scan
Спасибо SomewhereSomehow за наводку 13186561

Так что голосуем.
19 сен 12, 21:16    [13192159]     Ответить | Цитировать Сообщить модератору
 Re: Агрегаты Min, Max при группировке на "хорошем" индексе  [new]
step_ks
Member

Откуда:
Сообщений: 936
уже
19 сен 12, 23:28    [13192868]     Ответить | Цитировать Сообщить модератору
 Re: Агрегаты Min, Max при группировке на "хорошем" индексе  [new]
Mind
Member

Откуда: Лучший город на Земле
Сообщений: 2322
Давно уже проголосовали
20 сен 12, 01:33    [13193157]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить