Operadores de Ejecución de Consultas

Los operadores de ejecución de consultas son los algoritmos físicos — escaneos, selecciones, proyecciones, ordenamientos, agregaciones y uniones — que un motor de base de datos compone en un plan y ejecuta para producir el resultado de una consulta.

Definition

Un operador de ejecución de consultas es una implementación de una operación de álgebra relacional como un algoritmo sobre flujos de tuplas; los operadores se componen en un árbol o tubería que, al ejecutarse, calcula el resultado de una consulta.

Scope

Este tema cubre los operadores físicos de un motor de consultas y cómo se organizan para la ejecución: el modelo iterador (abrir-siguiente-cerrar), la tubería (pipelining) versus la materialización, los escaneos de tablas e índices, la selección y proyección, la ordenación por mezcla externa, la agrupación y agregación, y la eliminación de duplicados. Se aborda cómo los operadores consumen y producen flujos de tuplas y cómo la memoria y la E/S afectan su costo. Se excluyen los detalles específicos de los algoritmos de unión y el optimizador que elige entre los operadores, que son temas adyacentes.

Core questions

• ¿Cómo permite el modelo iterador (abrir-siguiente-cerrar) que los operadores se compongan en una tubería?
• ¿Cuándo se canaliza (pipelined) un resultado versus se materializa en el disco?
• ¿Cómo se implementan físicamente la selección, la proyección y la eliminación de duplicados?
• ¿Cómo maneja la ordenación por mezcla externa datos más grandes que la memoria?
• ¿Cómo influyen el presupuesto de memoria y el costo de E/S en el rendimiento del operador?

Key concepts

• modelo iterador / abrir-siguiente-cerrar
• escaneos de tablas e índices
• operadores de selección y proyección
• ordenación por mezcla externa
• agrupación basada en hash
• operadores de agregación
• eliminación de duplicados
• tubería (pipelining) versus materialización

Key theories

El modelo iterador (Volcano)

Cada operador expone los métodos abrir, siguiente y cerrar, y extrae tuplas de sus hijos bajo demanda; esta interfaz uniforme permite que operadores arbitrarios se compongan en tuberías y es la base de la mayoría de los motores de consultas.

Tubería (pipelining) versus materialización

Los operadores en tubería pasan las tuplas directamente a su padre sin escribir resultados intermedios, ahorrando E/S, mientras que los operadores de bloqueo, como la ordenación, deben materializar su entrada antes de producir la salida; el optimizador equilibra ambos.

Ordenación y agregación externas

Cuando los datos exceden la memoria, la ordenación por mezcla externa y la agrupación basada en hash los procesan en pasadas sobre el disco; estos algoritmos subyacen a ORDER BY, GROUP BY, la eliminación de duplicados y las uniones por ordenación-mezcla.

Clinical relevance

Los operadores de ejecución son donde el costo estimado de un plan de consulta se convierte en tiempo de ejecución real: la elección e implementación de los operadores, y qué tan bien utilizan la memoria y evitan E/S de disco innecesarias, determinan el rendimiento y la latencia de cada consulta que una base de datos atiende.

History

El modelo iterador se cristalizó en el marco de evaluación de consultas Volcano de Graefe y en su estudio de 1993 sobre técnicas de evaluación de consultas, que catalogó los operadores físicos utilizados por los motores relacionales. La interfaz uniforme del modelo hizo que los motores de consultas extensibles y componibles fueran prácticos y sigue siendo estándar, con trabajos posteriores que añadieron ejecución vectorizada y compilada para una mayor eficiencia.

Key figures

• Goetz Graefe
• Jeffrey D. Ullman

Seminal works

• graefe1993
• garciamolina2008

Frequently asked questions

¿Qué es el modelo iterador?

Es un diseño en el que cada operador físico implementa la misma interfaz —típicamente abrir, siguiente y cerrar— y produce tuplas una a la vez cuando su padre llama a siguiente. Debido a que todos los operadores comparten esta interfaz, se pueden conectar para formar árboles de planes arbitrarios, y las tuplas fluyen por el árbol bajo demanda.

¿Por qué algunos operadores se denominan de bloqueo?

Un operador de bloqueo no puede producir ninguna salida hasta que haya consumido toda su entrada —la ordenación y ciertas agregaciones son ejemplos, ya que el resultado final depende de cada tupla de entrada. Los operadores de bloqueo deben materializar su entrada, mientras que los operadores en tubería, como la selección, pueden emitir resultados a medida que avanzan.