exploysТеоретически Хэширование при соединении таблиц и группировки имеет несколько приемуществ:
хэш-функция
1. получая на вход значение ключа, на выходе дает адрес строки или указателя на строку
2. вырабатывает меньшее значение
3. равномерно распределеяет данные

Вопрос в следующем, каким образом практически реализуется 1, т.е. кто-нибуть может конкретный привести пример такой функции?
Раньше я думал, что если соединение на равенство, и одна табла из соединяемых малая, то эту малую таблу скачивать в память моно один раз, и Хэширование сократит число циклов, за счет того, что значение сравнивается по значению только с одной группой записей, с которой совпал Хэш ключ.
Допустим, эта малая табла разбита на 16 таких групп. Например, там 16 000 записей. Значение из второй таблы по ключу сравнивается с 15, и по конкретному значению только с той в которой совпал ключ. Т.е. вместо 16 000 цикл соствил 1000 + 15.
А поскольку вся табла первая в памяти, то на этом все и исчерпывается.

Но если первая табла не вся в памяти, то потребовалось бы считывать повторно блоки и из второй таблы, и хэширование могло потерять свои преимущества так как повторное чтение, могло бы, убить все это премущество.
Если в условии соединения неравенства, то это преимущество не работает.

vadiminfo,
Яж писал, про то что если ведомая таблица не помещается в памяти
exploysЧто группировка по хэш значениям это второстепенная задача. Когда хэш-таблица становиться слишком большой тогда действительно она делиться на группы по хэш-функции выполняющей роль двухуровневого дерева. [/quot]
Ну я писал, что думал так ранее. Т.е. если а малая таблица ("ведомая" ли "ведущая" ли ) не помещается в памяти, то преимущества хэш при соединении становятся менее очевидными. Т.е., возможно, нужно уже смотреть и другие алгоритмы с целью повышения производительности и сравнивать.
Т.е. выразил сомнения в преимуществах хэширования для СУБД у которых данные БД на дисках.


У Вашей СУБД есть отимизатор? Ну посмотрите планы запросов для разных ситуаций.

exploysMasterZiv, vadiminfo,

MS SQL BOL
авторРекурсия хэша возникает, когда входные данные не помещаются в доступную память, что приводит к разбиению их на несколько отдельно обрабатываемых секций. Если какая-либо из этих секций все же не помещается в доступную память, она разбивается на подсекции, которые также обрабатываются отдельно. Процесс разбиения продолжается, либо пока все секции не будут помещаться в доступную память, либо пока не будет достигнут максимальный уровень рекурсии


Ну, хорошо. Я же не говорю, что хэш не возможен. Я же предполагаю, что утрачиваются преимущества, возможно, драмматично в количестве считываний блоков. Ведь теперь блоки второй - большой таблы придется считывать с дисков по новой? Ить их нельзя было сравнить с теми что были не в памяти? Либо держать их и малые многократно считывать? Могут оказаться алгоритмы, которые обеспечат меньшее кол-во считываний. А количество считываний как правило самое критичное для СУБД такого типа хранения данных. Иначе бы в планах запросов мы вседа бы видели хэш - алгоритмы. "Но этого не происходит"(C)

exploysvadiminfo Могут оказаться алгоритмы, которые обеспечат меньшее кол-во считываний.
Это например какие алгоритмы?
исключая:
MERGE - только когда обе таблицы проиндексированы
NESTED LOOP - только когда одна из таблиц крайне мала, а большая проиндексирована
К слову в MS SQL только эти 3 алгоритма. Так какие же ещё ценные алгоритмы соединений они упустили?

Ну, Ви там в MS SQL если хотите, то исключайте SORT MERGE и NESTED LOOP.
А в Оракле, думау, все алгоритмы, включая перечисленные Вами, и так чрезмерно Вами ценимый алгоритм хэшированием (ить с ним надо сравнивать по Вашему только "ценные алгоритмы"), и в дополнение Cartesian еще какое-то время послужат.
Ну, по крайней мере, до тех пока Вы не откроете, что даже приведенные Вами случаи? када такие алгоритмы имеют преимущество, более не представляют интереса для практики.

А ить в соединении где в условиях могут быть неравенства.
А есть соедиения, где надо вернуть только первую строку (Например в SQL выражениях типа EXISTS).

Кроме того, если таблы малы? и их можно отсортировать в ОП, то SORT MERGE посему не проканает?

Наконец, кроме этого соединения в запросе могут быть другие операции, для которых все равно нужна сортировка.

Кста, хотел бы обратить внимание Ваше, что NESTED LOOP - пока еще самый общий, и потому незаменимый алгоритм. При помощи соединения вложенными циклами можно реализовать любое условие соединения.

И как и раньше, думау, что есль соединяемые таблы очень большие, то хэширование, возможно, с каког-то момента их увеличения, возможно, не буит иметь преимуществ перед не "ценным" NESTED LOOP, а если отсортировано то SORT MERGE. На крайняк все окажутся не приемлемыми, и придется как-то по другому разруливать.

Понятие "ценные алгоритмы" не совсем ясно, так как не сталкивался с делением алгоритмов, используемых при оптимизации запросов по ценностной шкале. Потому, плиз, не нуно мне ниче подобного приписыть. Я ни про какие ценные и не ценные не говорил. Говорил про другие.

exploysvadiminfo, какой-то бессвязный набор букв.

Мы рассматриваем Хэширование. Соединение хэшированием применяется когда нету индексов. Вы высказали мнение, что если обе таблицы не поместятся в памяти то хэширование не оптимально.
Т.е. в этом случае, когда нету индексов и обе таблицы не помещаются в памяти по вашему оптимальнее будет использовать SORT MERGE и NESTED LOOP?
А уж как вы решили соединение хэшированием заменить картезианом вообще непонятно.
А когда есть индексы "Соединение хэшированием" не применимо? А планы в Оракле с хэшированием для индексированных попадаются.

Я вроде высказал, что может терять преимущества. Т.е. может оказаться не оптимальным, а не оказывается обязательно не отимальным. Это даже не означет в общем случае что, кто-то луче, Это означет, что ОНО не луче. Например, все плохи. Вы и в правду, как-то не совсем удачно связываете буквы.

Уточню что хотел сказать тада есче раз:
Я хотел сказать, что признау, что хэширование саммый эффективный способ при относительно небольшом размере меньшей таблы. Особенно када она помещается в памяти. Не зависимо ни от наличия или отсутсвия индексов или чего либо еще.
Но чем больше меньшая табла, тем более эти преимущества более утрачиваются с момента как она не помещается в памяти. Эта эффективность тает.
И не исключаю, что SORT MERGE и NESTED LOOP могут быть как минимум не хуже.



Про "нету индексов" я ниче не говорил. С какой стати? Не знау зачем их не создавать, если речь об оптимизации, и они могут помочь.

Не нуно, плиз, приписывать мне ниче такого.

Если бы Вы нашли бы связи в буквах, то типа я там приводил и др случаи када хэширование не канает.