La unión hash es un ejemplo de un algoritmo de unión y se utiliza en la implementación de un sistema de gestión de bases de datos relacionales . Todas las variantes de los algoritmos de unión hash implican la creación de tablas hash a partir de las tuplas de una o ambas relaciones unidas y, posteriormente, el sondeo de esas tablas de modo que solo sea necesario comparar las tuplas con el mismo código hash para determinar su igualdad en las uniones equi.
Las uniones hash suelen ser más eficientes que las uniones de bucles anidados, excepto cuando el lado de sondeo de la unión es muy pequeño. Requieren un predicado de unión equitativa (un predicado que compara registros de una tabla con los de la otra tabla utilizando una conjunción de operadores de igualdad '=' en una o más columnas).
El algoritmo clásico de unión hash para una unión interna de dos relaciones procede de la siguiente manera:
La primera fase se suele denominar fase de "construcción" , mientras que la segunda se denomina fase de "prueba" . De manera similar, la relación de unión sobre la que se construye la tabla hash se denomina entrada de "construcción", mientras que la otra entrada se denomina entrada de "prueba".
Este algoritmo es simple, pero requiere que la relación de unión más pequeña quepa en la memoria, lo que a veces no sucede. Un enfoque simple para manejar esta situación es el siguiente:
En esencia, esto es lo mismo que el algoritmo de unión de bucles anidados en bloques . Este algoritmo puede escanear más veces de las necesarias.
Un enfoque mejor se conoce como "unión hash de gracia", en honor a la máquina de base de datos GRACE para la que se implementó por primera vez.
Este algoritmo evita volver a escanear toda la relación al particionar primero tanto y mediante una función hash, y escribir estas particiones en el disco. Luego, el algoritmo carga pares de particiones en la memoria, crea una tabla hash para la relación particionada más pequeña y sondea la otra relación para encontrar coincidencias con la tabla hash actual. Debido a que las particiones se formaron mediante el hash de la clave de unión, debe darse el caso de que todas las tuplas de salida de la unión pertenezcan a la misma partición.
Es posible que una o más de las particiones aún no quepan en la memoria disponible, en cuyo caso el algoritmo se aplica de forma recursiva: se elige una función hash ortogonal adicional para dividir la partición grande en subparticiones, que luego se procesan como antes. Como esto es costoso, el algoritmo intenta reducir la posibilidad de que esto ocurra formando las particiones más pequeñas posibles durante la fase de partición inicial.
El algoritmo de unión hash híbrida [1] es una combinación de la unión hash clásica y la unión hash de gracia. Utiliza una cantidad mínima de memoria para la partición como en la unión hash de gracia y utiliza la memoria restante para inicializar una unión hash clásica durante la fase de partición. Durante la fase de partición, la unión hash híbrida utiliza la memoria disponible para dos propósitos:
Debido a que la partición 0 nunca se escribe en el disco, la unión hash híbrida normalmente realiza menos operaciones de E/S que la unión hash de gracia. Cuando se ajusta casi por completo a la memoria, la unión hash híbrida tiene un comportamiento similar al de la unión hash clásica, lo que resulta más beneficioso. De lo contrario, la unión hash híbrida imita la unión hash de gracia.
Tenga en cuenta que este algoritmo es sensible a la memoria, porque hay dos demandas de memoria en competencia (la tabla hash para la partición 0 y los buffers de salida para las particiones restantes). Elegir una tabla hash demasiado grande para la partición 0 puede provocar que el algoritmo se repita porque una de las particiones distintas de cero es demasiado grande para caber en la memoria.
Las uniones hash también se pueden evaluar para un predicado anti-join (un predicado que selecciona valores de una tabla cuando no se encuentran valores relacionados en la otra). Según los tamaños de las tablas, se pueden aplicar diferentes algoritmos:
Esto es más eficiente cuando la tabla NOT IN es más pequeña que la tabla FROM .
Esto es más eficiente cuando la tabla NOT IN es más grande que la tabla FROM .
La unión semi-hash se utiliza para devolver los registros encontrados en la otra tabla. A diferencia de la unión simple, devuelve cada registro coincidente de la tabla principal solo una vez, independientemente de cuántas coincidencias haya en la tabla IN .
Al igual que la antiunión, la semiunión también puede ser izquierda y derecha:
Los registros se devuelven inmediatamente después de que se produce un resultado. Los registros reales de la tabla hash se ignoran.
Esto es más eficiente cuando la tabla IN es más pequeña que la tabla FROM .
Con este algoritmo, cada registro de la tabla hash (es decir, la tabla FROM ) solo se puede devolver una vez, ya que se elimina después de ser devuelto.
Esto es más eficiente cuando la tabla IN es más grande que la tabla FROM .
