8. Procesamiento y optimización de consultas



Descargar 37,65 Kb.
Fecha de conversión14.03.2017
Tamaño37,65 Kb.

8. Procesamiento y optimización de consultas

  • Objetivos
  • Comprender las tareas de procesamiento y optimización de consultas realizadas por un sistema gestor de bases de datos relacional.
  • Conocer reglas heurísticas y de transformación de expresiones del álgebra relacional y cómo aplicarlas para mejorar la eficiencia de una consulta.
  • Conocer diferentes estrategias de implementación de operaciones relacionales, en particular la de reunión (join), y cómo evaluar el coste estimado de cada estrategia.
  • Identificar la información estadística de la base de datos necesaria para estimar el coste de ejecución de las operaciones del álgebra relacional.

8. Procesamiento y Optimización de Consultas

  • Contenidos
  • 8.1. Conceptos generales y objetivos del procesamiento y la optimización de consultas
  • 8.2. Pasos del procesamiento de una consulta
    • 1. Análisis léxico, sintáctico y validación
    • 2. Optimización
  • 8.3. Reglas generales de transformación de expresiones y reglas heurísticas
  • 8.4. Implementación de operaciones relacionales
  • Anexo. Otros enfoques de la optimización: optimización semántica

8. Procesamiento y optimización de consultas

  • Bibliografía
  • [EN 2002] Elmasri, R.; Navathe, S.B.: Fundamentos de Sistemas de Bases de Datos. 3ª Edición. Addison-Wesley. (Cap. 18)
  • [EN 1997] Elmasri, R.; Navathe, S.B.: Sistemas de bases de datos. Conceptos fundamentales. 2ª Ed. Addison-Wesley Iberoamericana. (Cap. 16)
  • [CBS 1998] Connolly et al.: Database Systems: A Practical Approach to Design, Implementation and Management. 2nd Ed. Addison-Wesley (Cap. 18)
  • Crítica a los primeros sistemas basados en el modelo relacional:
    • bajo rendimiento de las consultas
  • Investigación y desarrollo de algoritmos eficientes para procesar consultas
  • En un sistema no relacional...
    • Consultas expresadas en lenguaje procedural de bajo nivel (embebido, norm.)
    • El usuario (programador) selecciona la estrategia de ejecución optimización “manual”
      • Decide las operaciones necesarias y su orden de ejecución
      • Si se equivoca, el sistema no puede mejorar la situación por sí solo
      • Debe tener conocimientos de programación (si no los tiene, no se beneficiará de la posibilidad de consultas más óptimas)
  • En un sistema relacional...
    • Consultas expresadas con SQL: QUÉ datos y no CÓMO recuperarlos
    • El SGBD selecciona la mejor estrategia de ejecución
    • y tiene mayor control sobre el rendimiento del sistema optimización “automática”
  • 8.1 Conceptos generales y objetivos
  • La optimización [automática es...
    • Un reto: obligatorio si se debe lograr un tiempo de ejecución de consultas aceptable
    • Una oportunidad: el alto nivel semántico de una expresión relacional permite su optimización antes de la ejecución
  • Procesamiento de Consultas
  • Actividades involucradas en la recuperación de datos de la BD
  • Optimización de Consultas
  • Elección de una estrategia de ejecución eficaz para procesar cada consulta sobre la base de datos
  • 8.1 Conceptos generales y objetivos
  • Objetivos del procesamiento de consultas
  • Transformar una consulta SQL en una estrategia de ejecución eficaz, expresada en un lenguaje de bajo nivel
  • Ejecutar dicha estrategia para recuperar los datos requeridos
  • Objetivo de la optimización de consultas
  • Elegir la estrategia de ejecución que minimiza el uso de los recursos
  • Existen muchas transformaciones equivalentes para una misma consulta
  • En general, no se garantiza que la estrategia elegida por el SGBD sea la óptima, pero seguro que será una estrategia razonablemente eficiente
  • 8.1 Conceptos generales y objetivos
  • Ventajas de la optimización automática
    • El usuario no se preocupa de cómo formular la consulta
    • El Módulo Optimizador trabajamejor” que el programador, pues:
      • Dispone de información estadística en el diccionario de datos del SGBD
        • mayor precisión al estimar la eficiencia de cada posible estrategia...
        • y así (con mayor probabilidad) elegirá la más eficiente
      • Si cambian las estadísticas (tras reorganización física del esquema de BD,...)
      • Re-optimización (quizá ahora convenga elegir otra estrategia)
        • SGBD Relacional: (trivial) El Optimizador re-procesa la consulta original
        • SGBD No Relacional: modificación del programa!
      • El Optimizador es un programa
      • tiene más paciencia que un programador: considera más estrategias
      • El Optimizador es el compendio de aptitudes y servicios de los mejores programadores
  • 8.1 Conceptos generales y objetivos
  • Análisis léxico, sintáctico y validación
  • Optimización
  • Generación de código
  • Ejecución
  • Estudiaremos con detalle los dos primeros pasos
  • 8.2 Pasos del procesamiento de una consulta
  • Análisis léxico
    • Identificar los componentes (léxicos) en el texto de la consulta (SQL)
  • Análisis sintáctico
    • Revisar la sintaxis de la consulta (corrección gramática)
  • Validación semántica
    • Verificar la validez de los nombres de las tablas, vistas, columnas, etc. y si tienen sentido
  • Traducción de la consulta a una representación interna
    • que la máquina manipula mejor,
    • eliminando peculiaridades del lenguaje de alto nivel empleado (SQL),
    • El formalismo base de la representación interna debe ser...
      • rico, para representar toda consulta posible
      • neutral, sin predisponer a ciertas opciones de optimización
    • La mejor elección: Álgebra Relacional
  • 1. Análisis léxico, sintáctico y validación
  • 8.2 Pasos del procesamiento de una consulta
  • Nombres de los empleados que trabajan en el proyecto nº 2 SELECT nombrep FROM Empleado E, Trabaja_en T WHERE E.nss = T.nsse AND T.nump=2 ;
  • resultado
  • proyectar(E.nombrep)
  • restringir(T.nump = 2)
  • reunir(E.nss = T.nsse)
  •  
  • EMPLEADO(E) TRABAJA_EN(T)
  • Árbol de Consulta
  • (o árbol sintáctico abstracto)
  • es la representación de una expresión algebraica
  • nombrep(nump=2(EMPLEADO nss=nsseTRABAJA_EN))
  • 1. Análisis léxico, sintáctico y validación (y 2)
  • 8.2 Pasos del procesamiento de una consulta
  • El Optimizador de Consultas suele combinar varias técnicas
  • Las técnicas principales son las siguientes:
    • Optimización heurística
      • Ordenar las operaciones de la consulta para incrementar la eficiencia de su ejecución
    • Estimación de costes
      • Estimar sistemáticamente el costo de cada estrategia de ejecución y
      • Elegir el plan (estrategia) con el menor costo estimado
  • 2. Optimización
  • 8.2 Pasos del procesamiento de una consulta
  • Varias expresiones del Álgebra Relacional pueden corresponder a la misma consulta
  • Lenguajes de consulta, como SQL permiten expresar una misma consulta de muchas formas diferentes, pero el rendimiento no debe depender de cómo sea expresada la consulta
  • Optimización Heurística Aplicación de reglas de transformación y heurísticas para modificar la representación interna de una consulta (Álgebra Relacional o Árbol de consulta) a fin de mejorar su rendimiento
  • 2. Optimización (2)
  • 8.2 Pasos del procesamiento de una consulta
  • El Analizador Sintáctico genera árbol de consulta inicial
    • sin optimización  ejecución ineficiente
  • El Optimizador de Consultas transforma el árbol de consulta inicial en árbol de consulta final equivalente y eficiente
    • Aplicación de reglas de transformación guiadas por reglas heurísticas
  • Conversión de la consulta en su forma canónica equivalente
  • 2. Optimización (3)
  • 8.2 Pasos del procesamiento de una consulta
  • Estimación sistemática de costes: Estimación y comparación de los costes de ejecutar una consulta con diferentes estrategias, y elegir la estrategia con menor coste estimado
  • Obtenida la forma canónica de la consulta, el Optimizador decide cómo evaluarla
  • El punto de partida es considerar la consulta como una serie de operaciones elementales interdependientes
    • Operaciones del Álgebra Relacional:
      • JOIN, PROYECCIÓN, RESTRICCIÓN, UNION, INTERSECCIÓN ...
  • 2. Optimización (4)
  • 8.2 Pasos del procesamiento de una consulta
  • El Optimizador tiene un conjunto de técnicas para realizar cada operación
    • Ejemplo: técnicas para implementar la operación de Restricción
    • Búsqueda Lineal
    • Búsqueda Binaria
    • Empleo de Índice Primario o Clave de Dispersión
    • Empleo de Índice de Agrupamiento
    • Empleo de Índice Secundario
  • ¿Cómo elige el Optimizador las técnicas adecuadas en cada caso?
  • 2. Optimización (5)
  • 8.2 Pasos del procesamiento de una consulta
  • Información Estadística
  • (diccionario de datos)
  • Información sobre la interdependencia entre las operaciones de bajo nivel
  • Elección de varias técnicas
  • candidatas para cada operación
  • OPTIMIZADOR
  • 2. Optimización (6)
  • 8.2 Pasos del procesamiento de una consulta
  • Información estadística
    • Para cada tabla
      • Cardinalidad (nº de filas),
      • Factor de bloques (nº de filas que caben en un bloque),
      • Nº de bloques ocupados,
      • Método de acceso primario y otras estructuras de acceso (hash,índices,etc.),
      • Columnas indexadas, de dispersión, de ordenamiento (físico o no), etc.
    • Para cada columna
      • Nº de valores distintos almacenados,
      • Valores máximo y mínimo, etc.
    • Nº de niveles de cada índice de múltiples niveles
    • El éxito de la estimación del tamaño y del coste de las operaciones incluidas en una consulta, depende de la cantidad y actualidad de la información estadística almacenada en el diccionario de datos del SGBD
  • 2. Optimización (7)
  • 8.2 Pasos del procesamiento de una consulta
  • El Optimizador genera varios planes de ejecución
  • Plan de Ejecución = combinación de técnicas candidatas
    •  una técnica por cada operación elemental de la consulta
  • Cada técnica tendrá asociada una estimación del coste
  • Coste(técnicai) = nº accesos a bloque de disco necesarios
    • Medida en número de transferencias de bloques memoria  disco
    • La estimación precisa de costes es difícil, pues para estimar el nº de accesos a bloque es necesario estimar el tamaño de las tablas (base o generadas como resultados intermedios), lo cual depende de los valores actuales de los datos
  • 2. Optimización (8)
  • 8.2 Pasos del procesamiento de una consulta
  • El Optimizador elige el plan de ejecución más económico
  • Para ello formula una función de coste que se debe minimizar
  • Coste (planp)  i coste (técnicaip )
  • En general, existen muchos (¡demasiados!) posibles planes de ejecución para una consulta
  • La tarea de obtener el plan más económico, tendría un coste prohibitivo…
    • Se suele hacer uso de técnicas heurísticas para mantener el conjunto de planes de consulta generados dentro de unos límites razonables: reducción del ‘espacio de evaluación’
  • 2. Optimización (y 9)
  • 8.2 Pasos del procesamiento de una consulta
  • 1. Una secuencia de restricciones sobre una tabla A puede transformarse en una sola restricción
    • C1(C2(A ))  C1 AND C2(A )
  • 2. En una secuencia de proyecciones contra una tabla A pueden ignorarse todas, salvo la última (si cada columna mencionado en la última, también aparece en las demás)
    • P2(P1(A ))  P2(A ), sii P2  P1
  • 3. Una restricción de una proyección puede transformarse en una proyección de una restricción
    • C(P(A ))  P (C(A ))
  • 8.3 Reglas de transformación de expresiones
  • Reglas generales de transformación
  • Es una buena idea hacer restricción antes que proyección, pues la restricción reduce el tamaño de la entrada para la proyección (el número de filas que considerar)
  • 4.  es distributivo respecto de la UNIÓN, INTERSECCIÓN y DIFERENCIA
    • C (RS)  (C (R))  (C (S))
    • donde   { , ,  }
  • 5.  es distributivo respecto de la UNIÓN
    • P (RS)  (P (R))  (P (S))
  • 8.3 Reglas de transformación de expresiones
  • Reglas generales de transformación (2)
  •  Distributividad
    • Sea f un operador unario y  un operador binario,
    • f es distributivo respecto de  si f(A  B) = f(A)  f(B)
  • se reduce el número de filas examinadas en la siguiente operación en secuencia:  (así, esa operación será más rápida y también producirá menos filas)
  • 6.  es distributivo respecto de REUNIÓN (JOIN) si la condición de selección c...
    • contiene columnas que sólo pertenecen a una tabla
    • nump=2(EMPLEADO nss=nsseTRABAJA_EN)  EMPLEADO nss=nsse(nump=2(TRABAJA_EN))
    • o puede escribirse como (c1 AND c2), y en c1 sólo intervienen columnas de R1 y en c2 sólo hay columnas de R2
    • c(R1 J R2)  (c1(R1)) J (c2(R2))
  • 8.3 Reglas de transformación de expresiones
  • Reglas generales de transformación (3)
  • se reduce el número de filas examinadas en la siguiente operación en secuencia: join (así, esa operación será más rápida y también producirá menos filas)
  • 7.  es distributivo respecto de JOIN si en la condición de reunión J sólo intervienen columnas incluidos en la lista de proyección P
    • P(R1 J R2)  (P_R1(R1 )) J (P_R2(R2 ))
    • sii P= (P_R1  P_R2) y P incluye toda columna de reunión que aparece en J
  • 8.3 Reglas de transformación de expresiones
  • Reglas generales de transformación (4)
  • se reduce el nº de columnas que tratar en la siguiente operación en secuencia: join (por tanto, esa operación necesitará menos tiempo para su ejecución y producirá menos columnas )
  • 8. En Álgebra Relacional, son conmutativas: UNIÓN, INTERSECCIÓN y JOIN
  • y no conmutativas: DIFERENCIA y DIVISIÓN
  • 9. En Álgebra Relacional, son asociativas: UNIÓN, INTERSECCIÓN y JOIN
  • y no asociativas: DIFERENCIA y DIVISIÓN
  • 10. En Álgebra relacional, son idempotentes : UNIÓN, INTERSECCIÓN y JOIN
  • y no idempotentes: DIFERENCIA y DIVISIÓN
  •  Conmutatividad
  • Sea  un operador binario,  es conmutativo si A  B = B  A ,  A,B
  •  Asociatividad
  • Sea  un operador binario,  es asociativo si A  (BC)= (AB)  C ,  A,B,C
  •  Idempotencia
  • Sea  un operador binario,  es idempotente si A  A = A,  A
  • 8.3 Reglas de transformación de expresiones
  • Reglas generales de transformación (5)
  • Expresiones de cómputo escalar
    • El Optimizador debe conocer reglas de transformación de expresiones aritméticas, pues aparecen en las consultas
    • Reglas de transformación basadas en propiedades Conmutativa, Asociativa y Distributiva
  • Expresiones condicionales (booleanas)
  • 8.3 Reglas de transformación de expresiones
  • Reglas generales de transformación (6)
  • Sean a y b columnas de dos relaciones distintas, R(...a...) y S(...b...)
    • R (a>b AND b>3) S
  • la condición (a>b AND b>3) equivale a (a>b) AND (b>3) AND (a>3)
  • por ser “>” un operador transitivo
    • la “nueva” condición (a>3), permite realizar una restricción (sobre R) antes del JOIN entre R y S ( join necesario para evaluar (a>b) )
    • (a>3(R )) a>b (b>3(S ))
  • Sean las columnas a, b, c, d, e, f
  • La condición ( a>b OR (c=d AND e ) equivale a
    • ( a>b OR c=d ) AND ( a>b OR e
  • puesto que OR es distributivo respecto de AND
  • 8.3 Reglas de transformación de expresiones
  • Reglas generales de transformación (7)
  • Toda expresión condicional puede transformarse en su Forma Normal Conjuntiva (FNC)
  • Forma normal conjuntiva
  • Una expresión en FNC tiene la forma
  • C1 AND C2 AND ... Cn
  • donde cada Ci no incluye ningún AND
    • Es TRUE si todo Ci es TRUE, y es FALSE si algún Ci es FALSE
  • Ventajas de la FNC
    • Ya que AND es conmutativo, el Optimizador puede evaluar cada Ci en cualquier orden (por ejemplo, en orden creciente en dificultad). En cuanto un Ci dé FALSE, el proceso puede acabar
    • En un entorno de procesamiento paralelo, sería posible evaluar todos los Ci a la vez. En cuanto uno diera FALSE, el proceso acabaría
  • 8.3 Reglas de transformación de expresiones
  • Reglas generales de transformación (y 8)
  • Algunas buenas heurísticas que pueden ser aplicadas durante el procesamiento de consultas
  • Ejecutar operaciones de restricción tan pronto como sea posible
  • Ejecutar primero las restricciones más restrictivas (las que producen menor nº de filas)
  • Combinar un producto cartesiano con una restricción  subsiguiente cuya condición represente una condición de reunión, convirtiéndolas en un join
  • Ejecutar las operaciones de proyección tan pronto como sea posible
  • 8.3 Reglas de transformación de expresiones
  • Reglas heurísticas
  • Las técnicas para realizar una reunión pueden ser las siguientes:
    • 1. Fuerza Bruta
    • 2. Búsqueda por Índice
    • 3. Búsqueda Hash
    • 4. Mezcla
    • 5. Hash
    • 6. Combinaciones de las anteriores
  • Daremos alguna indicación del cálculo del coste, en términos de número de accesos a bloques de disco
  • 8.4 Implementación de operac. relacionales
  • Implementación de la reunión (JOIN)

Por simplicidad y claridad, los algoritmos han sido codificados con los siguientes supuestos:

  • Por simplicidad y claridad, los algoritmos han sido codificados con los siguientes supuestos:
  • La tabla R tiene m filas y la tabla S tiene n filas en total.
  • La columna de reunión es simple, se llama C, y se denomina igual en ambas tablas.
  • Se considera que las filas de cierta tabla están almacenadas en un array con igual nombre que la tabla.
  • Cada fila está contenida en una posición del array.
  • La reunión de dos filas se expresa mediante el producto de dichas filas (operador * entre posiciones del array).
  • 8.4 Implementación de operac. relacionales
  • Implementación de la reunión (JOIN)
  • Examinar todas las posibles combinaciones de filas de R y S
  • Para cada fila de R, obtener todas las de S y probar si satisfacen la condición de reunión
      • for ( i = 1 ; i  m ; i++ )
      • for ( j = 1 ; j  n ; j++ )
      • if ( R[ i ].C == S[ j ].C ) añadir la fila reunida R[ i ] * S[ j ] al resultado;
  • Cálculo del coste
  • 1. Operaciones de lectura de filas = m * n
  • 2. Operaciones de escritura de filas = cardinalidad del join resultado
    • 2.a Caso de join uno-a-muchos (es decir, clave candidata / clave externa)
      • cardinalidad del join resultado = cardinalidad de la tabla con la clave externa (m ó n)
    • 2.b Caso de join muchos-a-muchos
      • Sea dCR = nº valores distintos de la columna de reunión C en la tabla R y
      • dCS = nº valores distintos de la columna de reunión C en la tabla S
    • (estimación suponiendo una distribución uniforme de los valores de la columna C)
    • Dos puntos de vista: (ver transparencia siguiente)
  • 8.4 Implementación de operac. relacionales
  • Implementación de JOIN por fuerza bruta
      • a. Para cada fila de R habrá filas de S con el mismo valor de C,
      • nº total de filas en el join = (a)
      • b. Para cada fila de S habrá filas de R con el mismo valor de C
      • nº total de filas en el join = (b)
    • Si dCS  dCR, las estimaciones (a) y (b) son diferentes
      • Existe algún valor de C que ocurra en R pero no en S, o viceversa
      • Cardinalidad del join resultado = menor estimador
    • En la práctica interesa el acceso L/E a bloques (no a filas)
      • Sea bS (y bR) el nº filas de S (o R) en un bloque
      • R ocupa bloques y S ocupa bloques de disco
      • Lecturas de bloques: ejemplo con m=100, n=10.000, bR=1 y bS=10
        • · R exterior, S interior
        • · S exterior, R interior
      • Conviene que la tabla del bucle exterior sea la menor (la q ocupa menos bloques)
  • 8.4 Implementación de operac. relacionales
  • Implementación de JOIN por fuerza bruta (y 2)
  • Existe un índice X sobre la columna S.C de la tabla interior S
    • for ( i = 1 ; i  m ; i++ ) /* bucle exterior */
    • /* existen k entradas de índice X[1] .. X[k]
    • con el valor de la columna indexada igual a R[ i ].C */
    • for ( j = 1 ; j  k ; j++ ) /* bucle interior */
    • /* sea S[ j ] la fila de S indexada por X[ j ] */
    • añadir la fila reunida R[ i ] * S[ j ] al resultado;
  • Ventaja sobre la fuerza bruta: acceso directo (vía índice) a las filas de S relacionadas con cada fila de R
    • Nº total de filas leídas de R y S = cardinalidad del resultado
    • peor de los casos: cada fila leída de S está en un bloque diferente del disco
    • Nº total de bloques leídos =
    • Si m=100, n=10.000, bR=1, bS=10 y dCS=100, el total de bloques leídos es 10.100
  • 8.4 Implementación de operac. relacionales
  • Implementación de JOIN por búsqueda por índice
  • Además, si las filas de S se almacenan en secuencia ordenada según valor de la columna de reunión C, las lecturas de bloque se reducen a
    • ventaja de mantener almacenadas las relaciones en una buena secuencia física
  • Sobrecarga por el acceso al índice X:
    • Peor caso: cada fila de R necesita una búsqueda completa en X para encontrar las filas correspondientes en S  lectura de 1 bloque en cada nivel de X
    • Si X tiene L niveles, son m * L lecturas extras de bloques
    • En la práctica L  3 y el nivel superior de X reside en Memoria Principal (menos lecturas)
  • 8.4 Implementación de operac. relacionales
  • Implementación de JOIN por búsqueda por índice (y 2)
  • 8.4 Implementación de operac. relacionales
  • Implementación de JOIN por búsqueda hashing
  • La organización primaria de S es direccionamiento directo, es decir, las filas de S están almacenadas en un fichero organizado según la técnica hashing (aunque en el algoritmo se representa como un array)
  • El algoritmo es similar a la búsqueda por índice, pero el camino de acceso a S según la columna de reunión S.C es una tabla hash y no un índice
    • /*supuesta una tabla hash H sobre S.C*/
    • for (i = 1 ; i  m ; i++) { /*bucle exterior*/
    • k= hash( R[ i ].C ); /* existen h filas S[1] .. S[h] almacenadas en H[ k ] */
    • for (j = 1 ; j  h ; j++) /*bucle interior*/
    • if ( S[ j ].C == R[ i ].C )
    • añadir la fila reunida R[ i ] * S[ j ] al resultado;
    • }
  • Considera R y S almacenadas en orden según valores de la columna de reunión C
    • Ambas pueden examinarse según el orden físico y de forma sincronizada
    • El JOIN completo puede realizarse en una única pasada sobre los datos
    • Técnica óptima
      • Cada bloque se ‘toca’ una sola vez (join uno-a-muchos)
      • Nº bloques leídos
  • /* supuesto un JOIN muchos-a-muchos */
    • r = s = 1;
    • while ( rm && sn ) { /*bucle exterior*/
    • v = R[ r ].C;
    • for ( j = s ; S[ j ].C < v ; j++ ) ;
    • s = j;
    • for ( j = s ; S[ j ].C == v ; j++ ) /*bucle interior principal*/
    • for ( i=r ; R[ i ].C == v ) añadir la fila reunida R[ i ] * S[ j ] al resultado;
    • s = j;
    • for ( i = r ; R[ i ].C == v ; i++ ) ;
    • r = i; }
  • 8.4 Implementación de operac. relacionales
  • Implementación de JOIN por mezcla
  • Factor crítico del rendimiento:
  • Agrupamiento físico de datos relacionados lógicamente (ficheros ordenados)
  • En ausencia del agrupamiento, ordenar una o ambas relaciones en tiempo de ejecución y mezclarlas (agrupamiento dinámico: técnica sort/merge)
  • Necesita una única pasada sobre los datos de cada tabla
    • 1er Paso: Construir tabla hash H para S sobre S.C
    • Cada entrada de H contiene:
      • Valor de S.C y (opcional) valores de otras columnas de S
      • Puntero a la fila correspondiente
    • 2º Paso: Examinar R y aplicar la misma función hash sobre R.C
      • Si una fila de R colisiona en H con filas de S, entonces
      • si S.C = R.C, se generan las filas reunidas adecuadas
  • Ventaja sobre la técnica de mezcla:
    • Las relaciones R y S no tienen por qué estar almacenadas en ningún orden,
    • tampoco es necesario ordenarlas dinámicamente
  • 8.4 Implementación de operac. relacionales
  • Implementación de JOIN por hash
  • /* construir una tabla hash H sobre S.C */
    • for ( j = 1 ; j  n ; j++ ) {
    • k = hash ( S[ j ].C ) ;
    • añadir S[ j ].C /* y quizá algún valor de columna más */ y un puntero a la fila S[ j ] a la entrada H[ k ] de tabla hash ;
    • }
  • /* búsqueda hashing sobre R */
    • for ( i = 1 ; i  m ; i++ ) {
      • k= hash ( R[ i ].C ); /* existen h filas S[ 1 ] .. S[ h ] en H[ k ] */
      • for ( j = 1 ; j  h ; j++ )
      • if ( S[ j ].C == R[ i ].C )
      • añadir la fila reunida R[ i ] * S[ j ] al resultado;
      • }
  • 8.4 Implementación de operac. relacionales
  • Implementación de JOIN por hash (y 2)
  • Enfoque diferente que puede combinarse con los que hemos visto
  • Transformación semántica: la que sólo es válida debido a cierta restricción de integridad (de tipo cualquiera, no sólo R.I. Referencial)
  • Optimización semántica: proceso de transformar una consulta en otra equivalente (cualitativamente diferente pero que garantiza el mismo resultado) y más eficiente, gracias a que los datos satisfacen restricciones de integridad especificadas sobre el esquema de base de datos
  • Con la aparición de las bases de datos de conocimiento y los sistemas expertos, es posible que esta técnica se incorpore a los SGBD futuros
  • Anexo. Otros enfoques de la optimización
  • Optimización semántica
  • Ejemplo:
  • « Obtener los nss de los empleados que trabajan en algún proyecto »
    • SELECT nss
    • FROM EMPLEADO, TRABAJA_EN
    • WHERE nss=nsse;
    •  nss(EMPLEADO nss=nsseTRABAJA_EN)
    • El JOIN hace corresponder una clave externa (nsse en TRABAJA_EN, que es NOT NULL, por ser parte de la PK) con su correspondiente clave candidata (nss en EMPLEADO),
    • Cada fila de TRABAJA_EN siempre tiene como contrapartida alguna de EMPLEADO,
    • así que cada fila de TRABAJA_EN contribuye con un valor de nsse al resultado global,
    • Para el resultado no se pide ninguna columna que “sólo esté” en EMPLEADO.
  • Anexo. Otros enfoques de la optimización
  • Optimización semántica (2)
    • ¡¡ No se necesita el JOIN !! y la consulta anterior equivale a:
    • SELECT DISTINCT nss
    • FROM TRABAJA_EN ;
    •  nsse(TRABAJA_EN)
  • Transformación válida sólo por la semántica de la situación
    • Cada fila de TRABAJA_EN corresponde a una fila en EMPLEADO, debido a la restricción de integridad referencial y a la de entidad
    • En general, cada operando de un JOIN contiene filas sin contrapartida en el otro operando y por tanto, que no contribuyen al resultado; en estos casos, transformaciones como la del ejemplo no son válidas
  • Anexo. Otros enfoques de la optimización
  • Optimización semántica (y 3)



Compartir con tus amigos:


La base de datos está protegida por derechos de autor ©absta.info 2019
enviar mensaje

    Página principal