Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Глупый вопрос по hash join  [new]
Коттини
Guest
Добрый вечер господа,
объясните зачем Sql Server заморачиватся на ресурсоемкий Hash join (расчет значения hash функции), при join по int полям. Ведь при соединении по int полям (без хэшей) издержек вроде меньше. Прошу прощения если вопрос слишком глупый.
10 дек 15, 19:26    [18542510]     Ответить | Цитировать Сообщить модератору
 Re: Глупый вопрос по hash join  [new]
invm
Member

Откуда: Москва
Сообщений: 9915
При hash-join по единственному int'у хеш не рассчитывается, хешем будет само значение этого int'а.
10 дек 15, 19:46    [18542612]     Ответить | Цитировать Сообщить модератору
 Re: Глупый вопрос по hash join  [new]
Коттини
Guest
invm,

Спасибо
10 дек 15, 19:51    [18542631]     Ответить | Цитировать Сообщить модератору
 Re: Глупый вопрос по hash join  [new]
SomewhereSomehow
Member

Откуда: Moscow
Сообщений: 2480
Блог
invm
При hash-join по единственному int'у хеш не рассчитывается, хешем будет само значение этого int'а.

Можно ли как-то это посмотреть?
10 дек 15, 21:43    [18543077]     Ответить | Цитировать Сообщить модератору
 Re: Глупый вопрос по hash join  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34709
Коттини
Добрый вечер господа,
объясните зачем Sql Server заморачиватся на ресурсоемкий Hash join (расчет значения hash функции), при join по int полям. Ведь при соединении по int полям (без хэшей) издержек вроде меньше. Прошу прощения если вопрос слишком глупый.


Вся магия в волшебном слове "вроде"...
10 дек 15, 21:45    [18543086]     Ответить | Цитировать Сообщить модератору
 Re: Глупый вопрос по hash join  [new]
invm
Member

Откуда: Москва
Сообщений: 9915
SomewhereSomehow
Можно ли как-то это посмотреть?
Не знаю.
Я про это вычитал то ли у Paul White, то ли у Paul Randal. Но ссылку на статью пока найти не могу :(
Как найду - опубликую.
10 дек 15, 22:57    [18543387]     Ответить | Цитировать Сообщить модератору
 Re: Глупый вопрос по hash join  [new]
SomewhereSomehow
Member

Откуда: Moscow
Сообщений: 2480
Блог
invm,

Поэтому и спросил. Я знаю, есть такая оптимизация, когда сервер знает, что коллизий быть не может и ему не нужно выполнять дополнительных проверок по linked list (бакету), когда туда помещается значение. Это называется "unique hash optimization". Но вот про саму хэш функцию, чтоб именно само значение использовалось - не помню/не видел (и вообще подробностей про то какая именно хэш функция используется не видел). Если найдете, опубликуйте, будет интересно.
10 дек 15, 23:10    [18543466]     Ответить | Цитировать Сообщить модератору
 Re: Глупый вопрос по hash join  [new]
invm
Member

Откуда: Москва
Сообщений: 9915
SomewhereSomehow,

В общем, прямого подтверждения не нашел.
Так что это оказалось всего лишь моим предположением, возможно ошибочным, основанным на
http://sqlblog.com/blogs/paul_white/archive/2011/07/19/join-performance-implicit-conversions-and-residuals.aspx
If the join is on a single column typed as TINYINT, SMALLINT or INTEGER and if both columns are constrained to be NOT NULL, the hash function is ‘perfect’ – meaning there is no chance of a hash collision, and the query processor does not have to check the values again to ensure they really match.
Т.е., описана упомянутая вам оптимизация.
А самая простая "perfect hash function" для tinyint, smallint и int - сами их значения.
13 дек 15, 22:33    [18555048]     Ответить | Цитировать Сообщить модератору
 Re: Глупый вопрос по hash join  [new]
Mike_za
Member

Откуда: Москва
Сообщений: 1176
А зачем в случае нуллабле тиниинт дополнительная проверка?
Понятно, что уж для 256+1 значений разработчики выход хеш функции знают и коллизий там нет?
14 дек 15, 10:50    [18556208]     Ответить | Цитировать Сообщить модератору
 Re: Глупый вопрос по hash join  [new]
SomewhereSomehow
Member

Откуда: Moscow
Сообщений: 2480
Блог
Mike_za,

Соединение хэшированием выполняет соединение, упрощенного говоря, делая две проверки.

Первая, это разбросать строки по хэш бакетам, вторая проверить, что строки, попавшие в один хэш бакет, соединяются на самом деле.

На простом примере.

Допустим, у нас есть две таблицы: A = {1, 2, 3, 4, 5}, B = {2, 3, 4, 5, 6}. Как мы можем получить A join B (для простоты внутреннее экви соединение)?

Самое первое что приходит в голову, тупой перебор, взять первое значение из А, взять первое значение из В, проверить равенство, если равны – вернуть строку, если нет, взять следующее значение. Это получается алгоритм Nested Loops (NL), т.е. в двух вложенных циклам проходим по таблицам. Сложность пропорциональная числу соединяемых элементов. Часто, не самый эффективный способ.

Хэш-соединение делает по-другому.

Сравнение 1. По меньшей из таблиц строится хэш-таблица, для простоты пусть хэш-функция HASH(x) = x%3. Берем HASH(A) = {1, 2, 0, 1, 2} , три разных значения, грубо говоря, три бакета.
HashTable:
Bucket 0: 3
Bucket 1: 1,4
Bucket 2: 2, 5

Сравнение 2. Теперь берем таблицу B и применяем ту же функцию. Первое значение 2. Hash(2) = 2%3 = 2. Значение попадает во второй бакет.

Но во втором бакете у нас есть два значения 2 и 3. Чтобы проверить, с каким действительно значением идет соединение, в рамках бакета выполняется перебор, берем первое – 2. 2=2? Да. Возвращаем строку, берем второе 2=5? Нет, отбрасываем.

Вот псевдо код:
http://blogs.msdn.com/b/craigfr/archive/2006/08/10/687630.aspx
for each row R1 in the build table
    begin
        calculate hash value on R1 join key(s)
        insert R1 into the appropriate hash bucket
    end
for each row R2 in the probe table
    begin
        calculate hash value on R2 join key(s)
        for each row R1 in the corresponding hash bucket
            if R1 joins with R2
                return (R1, R2)
    end


Т.е. хэш-соединение как бы уменьшает себе работу по перебору до значений в рамках одного бакета, вместо всей таблицы, как в случае NL.

В случае «unique hash optimization», сервер «знает», что при данных значениях данной хэш-функции невозможна ситуация, при которой, в одном бакете окажутся разные значения и пропускает этап номер два.

Но вот что это за функция, почему такая особенная обработка нулл, почему это не работает с bigint, я не знаю и точного описания не встречал. Расковырять самому, в принципе, можно, но, на мой взгляд, не целесообразно, т.к. цепочка довольно сложная, а полученные знания о конкретном методе хэширования не выглядят сильно полезными. Так что я не могу точно сказать используется литам какая-то функция или берутся сами значения (еще можно спросить у Пола, автора статьи, которую привел invm, знает ли он конкретный метод или назвал эту ситуацию «perfect hash function» условно).

Сообщение было отредактировано: 14 дек 15, 13:20
14 дек 15, 11:47    [18556527]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить