La combinación hash es un ejemplo de un algoritmo de combinación y se utiliza en la implementación de un sistema de administración de base de datos relacional . Todas las variantes de los algoritmos de combinación hash implican la creación de tablas hash a partir de las tuplas de una o ambas relaciones unidas y, posteriormente, sondear esas tablas para que solo las tuplas con el mismo código hash deban compararse para la igualdad en equijoins.
Las combinaciones hash suelen ser más eficientes que las combinaciones de bucles anidados, excepto cuando el lado de la sonda de la combinación es muy pequeño. Requieren un predicado de equijoin (un predicado que compara registros de una tabla con los de la otra tabla usando una conjunción de operadores de igualdad '=' en una o más columnas).
Unión hash clásica
El algoritmo clásico de combinación hash para una combinación interna de dos relaciones procede de la siguiente manera:
- Primero, prepare una tabla hash usando el contenido de una relación, idealmente la que sea más pequeña después de aplicar predicados locales. Esta relación se denomina lado de construcción de la unión. Las entradas de la tabla hash son asignaciones del valor del atributo de unión (compuesto) a los atributos restantes de esa fila (los que sean necesarios).
- Una vez que se construye la tabla hash , escanee la otra relación (el lado de la sonda). Para cada fila de la relación de la sonda, busque las filas relevantes de la relación de construcción mirando en la tabla hash .
La primera fase generalmente se denomina fase de "construcción" , mientras que la segunda se denomina fase de "prueba" . De manera similar, la relación de unión en la que se construye la tabla hash se denomina entrada "build", mientras que la otra entrada se denomina entrada "probe".
Este algoritmo es simple, pero requiere que la relación de unión más pequeña se ajuste a la memoria, lo que a veces no es el caso. Un enfoque simple para manejar esta situación procede de la siguiente manera:
- Para cada tupla en la entrada de compilación
- Agregar a la tabla hash en memoria
- Si el tamaño de la tabla hash es igual al tamaño máximo en memoria:
- Escanear la entrada de la sonda y agregue tuplas de unión coincidentes a la relación de salida
- Restablezca la tabla hash y continúe escaneando la entrada de compilación
- Hacer un escaneo final de la entrada de la sonda y agregue las tuplas de unión resultantes a la relación de salida
Esto es esencialmente lo mismo que el algoritmo de unión de bucle anidado en bloque . Este algoritmo escanea eventualmente más veces de las necesarias.
Grace hash join
Un mejor enfoque 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 todo relación dividiendo primero ambos y mediante una función hash y escribiendo estas particiones en el disco. Luego, el algoritmo carga pares de particiones en la memoria, construye una tabla hash para la relación particionada más pequeña y prueba la otra relación en busca de coincidencias con la tabla hash actual. Debido a que las particiones se formaron mediante hash en la clave de combinación, debe darse el caso de que cualquier tupla de salida de combinación pertenezca 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 de. Dado que esto es caro, el algoritmo intenta reducir la posibilidad de que ocurra formando las particiones más pequeñas posibles durante la fase de partición inicial.
Unión hash híbrida
El algoritmo de combinación de hash híbrido [1] es un refinamiento de la combinación de hash de gracia que aprovecha la mayor cantidad de memoria disponible. Durante la fase de partición, la combinación de hash híbrida utiliza la memoria disponible para dos propósitos:
- Para mantener la página del búfer de salida actual para cada uno de los particiones
- Para mantener una partición completa en la memoria, conocida como "partición 0"
Debido a que la partición 0 nunca se escribe ni se lee en el disco, la combinación de hash híbrida normalmente realiza menos operaciones de E / S que la combinación de 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 búferes de salida para las particiones restantes). La elección de una tabla hash demasiado grande puede hacer que el algoritmo se repita porque una de las particiones distintas de cero es demasiado grande para caber en la memoria.
Hash anti-unión
Las uniones hash también se pueden evaluar para un predicado anti-unión (un predicado que selecciona valores de una tabla cuando no se encuentran valores relacionados en la otra). Dependiendo del tamaño de las tablas, se pueden aplicar diferentes algoritmos:
Hash izquierdo anti-unión
- Prepare una tabla hash para el lado NOT IN de la combinación.
- Escanee la otra tabla, seleccionando cualquier fila donde el atributo de unión se convierta en una entrada vacía en la tabla hash.
Esto es más eficiente cuando la tabla NOT IN es más pequeña que la tabla FROM
Hash derecho anti-unión
- Prepare una tabla hash para el lado DESDE de la combinación.
- Escanee la tabla NOT IN , eliminando los registros correspondientes de la tabla hash en cada golpe de hash
- Devuelve todo lo que quedó en la tabla hash
Esto es más eficiente cuando la tabla NOT IN es más grande que la tabla FROM
Semifusión hash
La semifusión hash se utiliza para devolver los registros que se encuentran en la otra tabla. A diferencia de la unión simple, devuelve cada registro coincidente de la tabla principal solo una vez, sin tener en cuenta cuántas coincidencias hay en la tabla IN .
Al igual que con el anti-join, el semi-join también puede ser a la izquierda y a la derecha:
Hash a la izquierda semiunión
- Prepare una tabla hash para el lado IN de la combinación.
- Escanee la otra tabla, devolviendo cualquier fila que produzca un acierto de hash.
Los registros se devuelven inmediatamente después de producir un éxito. 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
Hash de semiunión a la derecha
- Prepare una tabla hash para el lado DESDE de la combinación.
- Escanee la tabla IN , devuelva los registros correspondientes de la tabla hash y elimínelos
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
Ver también
Referencias
- ^ DeWitt, DJ; Katz, R .; Olken, F .; Shapiro, L .; Stonebraker, M .; Wood, D. (junio de 1984). "Técnicas de implementación para sistemas de bases de datos de memoria principal". Proc. ACM SIGMOD Conf . 14 (4): 1–8. doi : 10.1145 / 971697.602261 .
enlaces externos
- Hansjörg Zeller; Jim Gray (1990). "Un algoritmo de combinación de hash adaptable para entornos multiusuario" (PDF) . Actas de la 16ª conferencia de VLDB . Brisbane: 186-197. Archivado desde el original (PDF) el 11 de marzo de 2012 . Consultado el 21 de septiembre de 2008 .