Optimización de consultas en sistemas centralizados
Una vez que se derivan las rutas de acceso alternativas para el cálculo de una expresión de álgebra relacional, se determina la ruta de acceso óptima. En este capítulo, veremos la optimización de consultas en un sistema centralizado, mientras que en el próximo capítulo estudiaremos la optimización de consultas en un sistema distribuido.
En un sistema centralizado, el procesamiento de consultas se realiza con el siguiente objetivo:
Minimización del tiempo de respuesta de la consulta (tiempo necesario para producir los resultados a la consulta del usuario).
Maximice el rendimiento del sistema (la cantidad de solicitudes que se procesan en un período de tiempo determinado).
Reduzca la cantidad de memoria y almacenamiento necesarios para el procesamiento.
Incrementar el paralelismo.
Análisis y traducción de consultas
Inicialmente, se analiza la consulta SQL. Luego se analiza para buscar errores sintácticos y la corrección de los tipos de datos. Si la consulta pasa este paso, la consulta se descompone en bloques de consulta más pequeños. Luego, cada bloque se traduce a una expresión de álgebra relacional equivalente.
Pasos para la optimización de consultas
La optimización de consultas implica tres pasos, a saber, generación de árboles de consultas, generación de planes y generación de códigos de planes de consultas.
Step 1 − Query Tree Generation
Un árbol de consulta es una estructura de datos de árbol que representa una expresión de álgebra relacional. Las tablas de la consulta se representan como nodos hoja. Las operaciones de álgebra relacional se representan como los nodos internos. La raíz representa la consulta como un todo.
Durante la ejecución, un nodo interno se ejecuta siempre que sus tablas de operandos estén disponibles. Luego, el nodo se reemplaza por la tabla de resultados. Este proceso continúa para todos los nodos internos hasta que el nodo raíz se ejecuta y se reemplaza por la tabla de resultados.
Por ejemplo, consideremos los siguientes esquemas:
EMPLEADO
| EmpID | Nombre | Salario | DeptNo | Fecha de inscripción |
DEPARTAMENTO
| No | DName | Ubicación |
Ejemplo 1
Consideremos la consulta como la siguiente.
$$ \ pi_ {EmpID} (\ sigma_ {EName = \ small "ArunKumar"} {(EMPLOYEE)}) $$
El árbol de consulta correspondiente será:
Ejemplo 2
Consideremos otra consulta que involucra una combinación.
$ \ pi_ {EName, Salary} (\ sigma_ {DName = \ small "Marketing"} {(DEPARTMENT)}) \ bowtie_ {DNo = DeptNo} {(EMPLOYEE)} $
A continuación se muestra el árbol de consultas para la consulta anterior.
Step 2 − Query Plan Generation
Una vez generado el árbol de consultas, se realiza un plan de consultas. Un plan de consulta es un árbol de consulta extendido que incluye rutas de acceso para todas las operaciones en el árbol de consulta. Las rutas de acceso especifican cómo se deben realizar las operaciones relacionales en el árbol. Por ejemplo, una operación de selección puede tener una ruta de acceso que proporcione detalles sobre el uso del índice de árbol B + para la selección.
Además, un plan de consulta también establece cómo se deben pasar las tablas intermedias de un operador al siguiente, cómo se deben usar las tablas temporales y cómo se deben canalizar / combinar las operaciones.
Step 3− Code Generation
La generación de código es el paso final en la optimización de consultas. Es la forma ejecutable de la consulta, cuya forma depende del tipo de sistema operativo subyacente. Una vez que se genera el código de consulta, Execution Manager lo ejecuta y produce los resultados.
Enfoques para la optimización de consultas
Entre los enfoques para la optimización de consultas, se utilizan principalmente búsquedas exhaustivas y algoritmos basados en heurística.
Optimización de búsqueda exhaustiva
En estas técnicas, para una consulta, inicialmente se generan todos los planes de consulta posibles y luego se selecciona el mejor plan. Aunque estas técnicas brindan la mejor solución, tiene una complejidad temporal y espacial exponencial debido al gran espacio de solución. Por ejemplo, técnica de programación dinámica.
Optimización basada en heurística
La optimización basada en heurística utiliza enfoques de optimización basados en reglas para la optimización de consultas. Estos algoritmos tienen una complejidad polinomial de tiempo y espacio, que es menor que la complejidad exponencial de los algoritmos exhaustivos basados en búsquedas. Sin embargo, estos algoritmos no producen necesariamente el mejor plan de consulta.
Algunas de las reglas heurísticas comunes son:
Realice operaciones de selección y proyecto antes de las operaciones de unión. Esto se hace moviendo las operaciones de selección y proyecto hacia abajo en el árbol de consultas. Esto reduce el número de tuplas disponibles para unirse.
Realice las operaciones de selección / proyecto más restrictivas al principio antes que las otras operaciones.
Evite la operación entre productos, ya que dan como resultado mesas intermedias de gran tamaño.