Algoritmos de unión (Join Algorithms)

Los algoritmos de unión son los métodos físicos —bucle anidado, fusión por ordenación y unión por hash— que combinan tuplas de dos o más relaciones según una condición de unión, y suelen ser los operadores más críticos para el rendimiento en un plan de consulta.

Definition

Un algoritmo de unión es un operador físico que calcula la unión de dos relaciones sobre un predicado, emparejando sistemáticamente tuplas que satisfacen la condición, utilizando iteración anidada, fusión ordenada o hashing para encontrar tuplas coincidentes de manera eficiente.

Scope

Este tema cubre los algoritmos principales para evaluar uniones: uniones de bucle anidado simples, por bloques y por índice; unión por fusión por ordenación y su sinergia con entradas ya ordenadas; y unión por hash, incluyendo las variantes grace e híbrida que manejan entradas más grandes que la memoria. Analiza su costo de E/S y requisitos de memoria, así como las condiciones bajo las cuales se prefiere cada uno. Excluye la enumeración de órdenes de unión del optimizador, que se trata en la optimización de consultas basada en costos.

Core questions

• ¿Cómo difieren los enfoques y costos de las uniones por bucle anidado, fusión por ordenación y hash?
• ¿Cuándo supera una unión por bucle anidado con índice a las alternativas?
• ¿Cómo manejan las uniones por hash grace e híbridas las entradas más grandes que la memoria?
• ¿Cómo se analiza el costo de E/S de cada método de unión en términos de páginas y pasadas?
• ¿Qué condición de unión (igualdad versus desigualdad) requiere cada algoritmo?

Key concepts

• unión por bucle anidado
• unión por bucle anidado por bloques
• unión por bucle anidado con índice
• unión por fusión por ordenación
• unión por hash
• unión por hash grace e híbrida
• equijoin versus theta join
• análisis de costos de E/S

Key theories

Uniones por bucle anidado

Para cada tupla de una relación, el algoritmo escanea la otra en busca de coincidencias; el bucle anidado por bloques reduce la E/S al almacenar páginas en búfer, y el bucle anidado con índice reemplaza el escaneo interno con una búsqueda de índice cuando hay uno disponible, lo que lo hace eficiente para uniones selectivas.

Unión por fusión por ordenación

Ambas entradas se ordenan según el atributo de unión y luego se fusionan en una única pasada coordinada; es especialmente atractiva cuando las entradas ya están ordenadas o cuando la salida debe estar ordenada, y maneja las uniones de igualdad de manera eficiente.

Unión por hash

Una unión de igualdad se calcula construyendo una tabla hash en memoria sobre la relación más pequeña y probándola con la más grande; las variantes grace e híbrida particionan ambas entradas en disco cuando exceden la memoria, lo que proporciona un rendimiento sólido para grandes equijoins.

Clinical relevance

Las uniones dominan el costo de las consultas analíticas y de informes que combinan múltiples tablas, por lo que la elección del algoritmo de unión —a menudo la decisión más importante en un plan— determina si dichas consultas son interactivas o tardan horas, lo que hace que estos algoritmos sean fundamentales para el rendimiento de la base de datos.

History

Las uniones por fusión por ordenación y por bucle anidado datan de los primeros sistemas relacionales. La unión por hash y sus variantes grace e híbrida se desarrollaron en la década de 1980, notablemente en la investigación de bases de datos paralelas, y se demostró que superaban a la fusión por ordenación para muchas equijoin grandes. La encuesta de Graefe de 1993 consolidó el análisis de estos algoritmos que los textos de bases de datos aún siguen.

Key figures

• Goetz Graefe
• David DeWitt

Seminal works

• graefe1993
• garciamolina2008

Frequently asked questions

¿Qué algoritmo de unión es el más rápido?

Depende de las entradas. La unión por hash suele ser la mejor para grandes equijoins cuando ninguna de las entradas está ordenada; la fusión por ordenación gana cuando las entradas ya están ordenadas o la salida debe estar ordenada; y el bucle anidado con índice es el mejor cuando una entrada es pequeña y la otra tiene un índice selectivo en la columna de unión. El optimizador elige basándose en el costo estimado.

¿Por qué la unión por hash no puede manejar condiciones de desigualdad?

La unión por hash agrupa las tuplas por el hash de la clave de unión para que solo las tuplas con claves iguales caigan en el mismo cubo. Eso funciona para condiciones de igualdad (equijoin) pero no para desigualdades como 'menor que', que requieren comparar tuplas entre cubos; estas se manejan con métodos de estilo bucle anidado o fusión por ordenación.