Unión por ordenación y fusión

La unión por ordenación y fusión (también conocida como unión por fusión) es un algoritmo de unión que se utiliza en la implementación de un sistema de gestión de bases de datos relacionales .

El problema fundamental de un algoritmo de unión consiste en encontrar, para cada valor distinto del atributo de unión, el conjunto de tuplas en cada relación que presenten dicho valor. La idea clave del algoritmo de ordenación y fusión es ordenar primero las relaciones según el atributo de unión, de modo que los escaneos lineales intercalados encuentren estos conjuntos simultáneamente.

En la práctica, la parte más costosa de realizar una unión de ordenación y fusión es lograr que ambas entradas al algoritmo se presenten en orden ordenado. Esto se puede conseguir mediante una operación de ordenación explícita (a menudo una ordenación externa ) o aprovechando un orden preexistente en una o ambas relaciones de unión. ^{[ 1 ]} Esta última condición, denominada orden interesante, puede darse porque una entrada a la unión podría ser producida por un escaneo de índice de un índice basado en árbol, otra unión de fusión o algún otro operador de plan que produzca una salida ordenada por una clave apropiada. Los órdenes interesantes no tienen por qué ser fortuitos: el optimizador puede buscar esta posibilidad y elegir un plan que sea subóptimo para una operación precedente específica si produce un orden interesante que uno o más nodos posteriores puedan aprovechar.

Dejar${\displaystyle R}$y${\displaystyle S}$ ser relaciones donde${\displaystyle |R|<|S|}$.${\displaystyle R}$encaja en${\displaystyle P_{r}}$páginas memoria y${\displaystyle S}$encaja en${\displaystyle P_{s}}$páginas de memoria. En el peor de los casos, una unión de ordenación y fusión se ejecutará en${\displaystyle O(P_{r}+P_{s})}$Operaciones de E/S. En el caso de que${\displaystyle R}$y${\displaystyle S}$Si no se ordenan, el costo de tiempo en el peor de los casos incluirá términos adicionales de tiempo de clasificación:${\displaystyle O(P_{r}+P_{s}+P_{r}\log(P_{r})+P_{s}\log(P_{s}))}$, lo cual es igual a${\displaystyle O(P_{r}\log(P_{r})+P_{s}\log(P_{s}))}$(Como los términos linealítricos tienen más peso que los términos lineales, véase la notación Big O – Órdenes de funciones comunes ).

Para simplificar, el algoritmo se describe en el caso de una unión interna de dos relaciones, izquierda y derecha . La generalización a otros tipos de unión es sencilla. El resultado del algoritmo contendrá únicamente las filas incluidas en las relaciones izquierda y derecha , y los duplicados formarán un producto cartesiano .

función Ordenar - Combinar Unir ( izquierda : Relación , derecha : Relación , comparador : Comparador ) { resultado = nueva Relación () // Asegurarse de que al menos un elemento esté presente if ( ! izquierda . hasNext () || ! derecha . hasNext ()) { return resultado } // Ordenar la relación izquierda y derecha con comparador izquierda . ordenar ( comparador ) derecha . ordenar ( comparador ) // Iniciar algoritmo Combinar Unir izquierdaFila izquierda = izquierda . siguiente () derechaFila derecha = derecha . siguiente () bucle externo Para siempre : mientras ( verdadero ) { mientras ( comparador . comparar ( izquierdaFila , derechaFila ) != 0 ) { if ( comparador . comparar ( izquierdaFila , derechaFila ) < 0 ) { // La fila izquierda es menor que la fila derecha if ( izquierda . hasNext ()) { // Avanzar a la siguiente fila izquierda izquierdaFila izquierda = izquierda . siguiente () } else { break outerForeverLoop } } else { // La fila izquierda es mayor que la fila derecha if ( right . hasNext ()) { // Avanzar a la siguiente fila derecha rightRow = right . next () } else { break outerForeverLoop } } } // Marcar la posición de la fila izquierda y mantener una copia de la fila izquierda actual left . mark () markedLeftRow = leftRow while ( true ) { while (comparator.compare ( leftRow , rightRow ) == 0 ) { // La fila izquierda y la fila derecha son iguales // Agregar filas al resultado result = add ( leftRow , rightRow ) // Avanzar a la siguiente fila izquierda leftRow = left.next ( ) // Comprobar si existe la fila izquierda if ( ! leftRow ) { // Continuar con el bucle infinito interno break } } if ( right.hasNext ( )) { // Avanzar a la siguiente fila derecha rightRow = right.next ( ) } else { break outerForeverLoop } if ( comparator.compare ( markedLeftRow , rightRow ) == 0 ) { // Restaurar la izquierda a la marca almacenada left.restoreMark ( ) leftRow = markedLeftRow } else { // Comprobar si existe la fila izquierda if ( ! leftRow ) { break outerForeverLoop } else { // Continuar con el bucle infinito externo break } } } } return result }

Dado que la lógica de comparación no es el aspecto central de este algoritmo, se oculta tras un comparador genérico y puede constar de varios criterios de comparación (por ejemplo, varias columnas). La función de comparación debe devolver si una fila es menor (-1) , igual (0) o mayor (1) que otra fila:

función comparar ( leftRow : RelationRow , rightRow : RelationRow ) : número { // Devuelve -1 si leftRow es menor que rightRow // Devuelve 0 si leftRow es igual a rightRow // Devuelve 1 si leftRow es mayor que rightRow }

Tenga en cuenta que una relación en términos de este pseudocódigo admite algunas operaciones básicas:

interface Relation { // Devuelve verdadero si la relación tiene una fila siguiente (de lo contrario, falso) hasNext () : boolean // Devuelve la siguiente fila de la relación (si la hay) next () : RelationRow // Ordena la relación con el comparador dado sort ( comparator : Comparator ) : void // Marca el índice de la fila actual mark () : void // Restaura el índice de la fila actual al índice de la fila marcada restoreMark () : void }

Tenga en cuenta que esta implementación asume que los atributos de unión son únicos, es decir, no es necesario generar varias tuplas para un valor dado de la clave.

public class MergeJoin { // Supongamos que izquierda y derecha ya están ordenadas public static Relation Merge ( Relation left , Relation right ) { Relation output = new Relation (); while ( ! left . IsPastEnd && ! right . IsPastEnd ) { if ( left . Key == right . Key ) { output . Add ( left . Key ); left . Advance (); right . Advance (); } else if ( left . Key < right . Key ) left . Advance (); else // if (left.Key > right.Key) right . Advance (); } return output ; } } public class Relation { private const int ENDPOS = - 1 ; private List < int > list ; private int position = 0 ;public Relación () { this . lista = new Lista < int > (); }public Relation ( List < int > list ) { this . list = list ; }público entero Posición => posición ;public int Clave => lista [ posición ];public bool IsPastEnd => position == ENDPOS ;public bool Advance ( ) { if ( position == list.Count - 1 || position == ENDPOS ) { position = ENDPOS ; return false ; } position ++ ; return true ; }​public void Agregar ( int clave ) { lista . Agregar ( clave ); }public void Print () { foreach ( int key in list ) Console . WriteLine ( key ); } }

• Hash join
• Unión de bucles anidados

Implementaciones en C# de diversos algoritmos de unión