Operadores de Execução de Consulta

Os operadores de execução de consulta são os algoritmos físicos — varreduras, seleções, projeções, ordenações, agregações e junções — que um motor de base de dados compõe num plano e executa para produzir o resultado de uma consulta.

Definition

Um operador de execução de consulta é uma implementação de uma operação de álgebra relacional como um algoritmo sobre fluxos de tuplos; os operadores são compostos numa árvore ou pipeline que, quando executado, calcula o resultado de uma consulta.

Scope

Este tópico abrange os operadores físicos de um motor de consulta e como são organizados para execução: o modelo iterador (abrir-próximo-fechar), o pipelining versus materialização, varreduras de tabela e índice, seleção e projeção, ordenação por intercalação externa, agrupamento e agregação, e eliminação de duplicados. Trata de como os operadores consomem e produzem fluxos de tuplos e como a memória e E/S afetam o seu custo. Exclui os detalhes dos algoritmos de junção e do otimizador que escolhe entre os operadores, que são tópicos adjacentes.

Core questions

• Como o modelo iterador (abrir-próximo-fechar) permite que os operadores sejam compostos num pipeline?
• Quando um resultado é processado em pipeline versus materializado em disco?
• Como a seleção, projeção e eliminação de duplicados são implementadas fisicamente?
• Como a ordenação por intercalação externa lida com dados maiores que a memória?
• Como o orçamento de memória e o custo de E/S moldam o desempenho do operador?

Key concepts

• modelo iterador / abrir-próximo-fechar
• varreduras de tabela e índice
• operadores de seleção e projeção
• ordenação por intercalação externa
• agrupamento baseado em hash
• operadores de agregação
• eliminação de duplicados
• pipelining versus materialização

Key theories

O modelo iterador (Volcano)

Cada operador expõe os métodos abrir, próximo e fechar e puxa tuplos dos seus filhos sob demanda; esta interface uniforme permite que operadores arbitrários sejam compostos em pipelines e é a base da maioria dos motores de consulta.

Pipelining versus materialização

Operadores em pipeline passam tuplos diretamente para o seu pai sem escrever resultados intermédios, economizando E/S, enquanto operadores de bloqueio, como a ordenação, devem materializar a sua entrada antes de produzir a saída; o otimizador equilibra os dois.

Ordenação e agregação externas

Quando os dados excedem a memória, a ordenação por intercalação externa e o agrupamento baseado em hash processam-nos em passagens sobre o disco; estes algoritmos subjazem a ORDER BY, GROUP BY, eliminação de duplicados e junções por ordenação-intercalação.

Clinical relevance

Os operadores de execução são onde o custo estimado de um plano de consulta se torna tempo de execução real: a escolha e implementação dos operadores, e quão bem utilizam a memória e evitam E/S de disco desnecessárias, determinam o rendimento e a latência de cada consulta que uma base de dados serve.

History

O modelo iterador foi cristalizado na estrutura de avaliação de consultas Volcano de Graefe e no seu levantamento de 1993 sobre técnicas de avaliação de consultas, que catalogou os operadores físicos utilizados pelos motores relacionais. A interface uniforme do modelo tornou os motores de consulta extensíveis e composíveis práticos e permanece um padrão, com trabalhos posteriores a adicionar execução vetorizada e compilada para maior eficiência.

Key figures

• Goetz Graefe
• Jeffrey D. Ullman

Seminal works

• graefe1993
• garciamolina2008

Frequently asked questions

O que é o modelo iterador?

É um projeto em que cada operador físico implementa a mesma interface — tipicamente abrir, próximo e fechar — e produz tuplos um de cada vez quando o seu pai chama próximo. Como todos os operadores partilham esta interface, podem ser conectados em árvores de plano arbitrárias, e os tuplos fluem pela árvore sob demanda.

Por que alguns operadores são chamados de bloqueadores?

Um operador bloqueador não pode produzir qualquer saída até ter consumido toda a sua entrada — a ordenação e certas agregações são exemplos, uma vez que o resultado final depende de cada tuplo de entrada. Operadores bloqueadores devem materializar a sua entrada, enquanto operadores em pipeline, como a seleção, podem emitir resultados à medida que avançam.