PDF de programación - Elección de Caminos de Acceso en Optimizadores de Bases de Datos - Un Lenguaje de Patrones

Elección de Caminos de Acceso en Optimizadores de Bases
de Datos - Un Lenguaje de Patrones

HORACIO PEÑAFIEL – Universidad Nacional de La Plata

Abstract
El subsistema de optimización de consultas SQL es parte hoy en día de todo sistema de

administración de bases de datos relacional (RDBMS). Dada una petición al servidor, resolver el

problema de la elección de un “Camino de Acceso” (“Access Path” en inglès) es de gran

importancia para dicho componente, ya que se trata de seleccionar una serie finita de pasos para

retornar un conjunto de tuplas (filas) de una o más relaciones (tablas o vistas). Con este objetivo, el

optimizador cuenta con algoritmos, heurísticas, índices, y otras técnicas más puntuales.

En este trabajo, enunciaremos un Lenguaje de Patrones para resolver este problema. Para ello,

nos basaremos en la teoría específica acerca del tema, así como en las diversas impl ementaciones

que los distintos RDBMSs existentes en el mercado hicieron al respecto. Tal como lo hace el

mismo optimizador, no pretenderemos obtener una única respuesta óptima, sino que buscaremos

guías que nos ayuden a comprender la arquitectura y el diseño de esta parte tan importante de los

optimizadores de SQL.


Categories and Subject Descriptors: D.2.11 [Software Engineering] Software Architectures–
Patterns  [Databases] Performance and Optimization
General Terms: Databases; Access Paths; Patterns
Additional Key Words and Phrases: Optimizer, Performance, Architectural Patterns


Patrón: Elector de Caminos de Acceso



Problema:

Cuando un Servidor de Bases de Datos Relacional recibe una consulta SQL, se desea saber qué

pasos realiza para devolver el resultado correcto, con el menor costo, en un tiempo razonable, y

haciendo el uso más eficiente de los recursos que cuenta.



Fuerzas:

Se trata de un problema de optimización de recursos, los cuales en el caso de un motor de bases

de datos son: CPU, Memoria y Disco (I/O). Nos encontramos que, en la práctica, al intentar

optimizar el uso de uno de estos elementos, incurrimos en un mayor costo de uso de alguno de los

restantes.

De los tres mencionados arriba, el acceso y transferencia de datos de y hacia disco es el que sea

más notorio como posible cuello de botella. A nivel físico, cuestiones como la latencia (movimiento

del cabezal para una búsqueda de un dato en particular), y la velocidad de los canales de acceso



Elección de Caminos de Acceso en Optimizadores de Bases de Datos - Un Lenguaje de Patrones – Pág. 1

(transferencia de datos), pueden afectar en forma directa a la performance de un servidor de bases

de datos. Sin embargo, este almacenamiento secundario nos brinda la ventaja de que el espacio

disponible es ampliamente mayor que el que disponemos en Memoria o en los registros internos

de

la CPU. Para ciertas operaciones, será necesario recurrir al disco, no sólo como

almacenamiento definitivo, sino también como un espacio temporal donde se pueda leer y escribir

información de transacciones que están siendo procesadas (buffers). Del recurso “Disco” nos

interesará observar el Tiempo de Acceso (Latencia).

En cuanto a la Memoria (almacenamiento primario), nos encontramos con que la velocidad de

acceso es muy superior a la del disco (aunque no tanto como los registros y/o caché del

procesador). Debido a que es un recurso crítico y escaso en el servidor, sólo se almacena

permanentemente un conjunto limitado de páginas de datos e índices en los buffers. El riesgo es

saturar al equipo provocando que dichas páginas se deban bajar a disco temporalmente para

liberar espacio, y luego volver a subirlas a memoria cuando sea necesario. Este fenómeno ,

amplificado en forma inversamente proporcional a la cantidad de memoria libre del si stema, se

denomina “trashing”, y se da no sólo en los sistemas de bases de datos sino que también

aparece a nivel de los sistemas operativos con memoria virtual – el resultado observable es que la

mayor parte del tiempo de procesamiento se pierde subiendo y bajando páginas de memoria a

disco y viceversa. Asimismo, no debemos olvidar el importante hecho de que el mismo DBMS es

una aplicación en sí misma, y que los módulos ejecutables requieren espacio adicional donde

residir. Por lo tanto, será de nuestro interés optimizar el Espacio Utilizado en Memoria (como

puntualizamos anteriormente, menos memoria libre aumenta el riesgo de “trashing”), así como

reducir los Tiempos de Alocación (el tiempo que se requiere para obtener un bloque de memoria).

Finalmente, debemos decir que el primer recurso, la CPU, puede ser un cuello de botella debido a

varias causas. Los sistemas de bases de datos aplican en forma recurrente un amplio conjunto de

algoritmos que son procesador-intensivos. Si bien los procesadores cuentan con almacenamiento

primario adicional (en forma de caches de primer nivel), nos interesa tomar como medida de

performance de la CPU el Tiempo de Procesamiento.



La conjetura RUM

En su trabajo “The RUM Conjecture (La conjetura RUM)”, [Athanass01] proporciona un enfoque

alternativo al que detallamos arriba, basándose en esta hipótesis:

“El desafío que enfrenta el Optimizador … se basa en minimizar: 1) los tiempos de lectura (R); 2)

los costos de actualizar los datos (U); y 3) el espacio en memoria requerido (M). Se plantea que al

optimizar dos de éstos factores, se obtiene un impacto negativo sobre la performance del tercero.”

Basándonos en este trabajo, podemos graficar la interacción de las Lecturas, Escrituras y Memoria

(RUM) como dimensiones que deben estar balanceadas:



Elección de Caminos de Acceso en Optimizadores de Bases de Datos - Un Lenguaje de Patrones – Pág. 2





Lecturas (R)



Escrituras (U)



Memoria/Disco (M)



Algunos ejemplos.

 Si se trata de optimizar la velocidad de las lecturas (R), podemos agregar un Indice B+ -

Tree. Este cambio requiere sin embargo un costo adicional al actualizar los datos (U), ya

que se deberá escribir tanto en las páginas de datos como en las del nuevo índice.

Asimismo, dicha estructura de árbol tiene que mantenerse en disco y/o en memoria para

ser utilizado (M).

 Si queremos optimizar para el uso de poca memoria, podemos calcular información en

lugar de almacenarla (M). Esto ocasiona una carga mayor a la CPU (R), y posiblemente al

disco (U).

 Otra forma de optimizar las lecturas (R) es replicando o particionando la información. En el

primer caso, tenemos accesos más rápidos a un costo de datos redundantes (U/M),

mientras que al particionar nos encontramos con una carga a la CPU (U) a la hora de

administrar dicho sistemas distribuídos.

En resumen, podemos decir que no hay “balas de plata”. En lo que sigue de este trabajo,

trataremos de enfocar estos problemas mediante una arquitectura flexible del Optimizador de SQL.



Solución:

Se implementa un componente en el Optimizador del RDBMS denominado “Optimizador de

Caminos de Acceso”. Llamamos “Camino de Acceso” a una serie de pasos concretos que el

Optimizador ejecuta sobre el Motor de Almacenamiento, con el fin de obtener un conjunto de tuplas

(filas) de una o más relaciones (tablas o vistas), con el menor costo posible, y haciendo uso

eficiente de los recursos disponibles. Para realizar esta tarea, cuenta con información acerca de la

estructura de la base de datos, así como estadísticas de uso de cada componente de la misma.

También recibe de otro componente, llamado “Algebrizer”, un árbol de sintaxis que representa la

consulta a ejecutar, obtenido a partir del SQL original.

El resultado de la ejecución del Optimizador será un “Plan de Ejecución Fìsico” o “Camino de

Acceso”, que le dicta al Motor de Almacenamiento la serie de pasos y estrategias a utilizar para

llevar a cabo la ejecución física de la petición. Es importante aclarar en este punto, que dicho Plan

de Ejecución en sí también consume recursos, por lo que la tarea de Elección del Camino de



Elección de Caminos de Acceso en Optimizadores de Bases de Datos - Un Lenguaje de Patrones – Pág. 3

Acceso, se debe hacer en forma automática, en un tiempo razonablemente rápido, y con un costo

mínimo agregado.

Finalmente, debemos considerar que si se requiera que el DBA o la misma aplicación cliente

balanceen manualmente el uso de recursos requeridos, podemos encontrarnos con que esta tarea

es bastante tediosa y no siempre conducente a los resultados deseados, ya que la elección del

Camino de Acceso óptimo (de menor costo), depende en gran medida también de la consulta a

ejecutar. De aquí se deriva la necesidad de que dicho procedimiento de optimización quede bajo la

responsabilidad del Optimizador de SQL.