Resumo

  • O otimizador do System R escolhia o menor custo estimado entre os planos que sua enumeração alcançava. A fórmula ponderava páginas lidas e chamadas à interface de armazenamento; não media antecipadamente o tempo de execução.
  • Seletividade alimentava cardinalidade, e cardinalidade alterava caminho de acesso, ordem de junção e operador físico. As “ordens interessantes” preservavam rotas mais caras no curto prazo quando elas podiam evitar trabalho posterior.
  • Selinger organizou uma contribuição de equipe assinada com Morton Astrahan, Donald Chamberlin, Raymond Lorie e Thomas Price. O legado é uma arquitetura em que premissa, decisão e observação continuam separadas e auditáveis.

A decisão vem antes da prova

Pense em uma consulta que relaciona pedidos, clientes e regiões, filtra o mês corrente e agrega a receita. Um índice seletivo pode encontrar poucas linhas já ordenadas para a próxima etapa. Uma varredura pode ler a tabela inteira, produzir um intermediário grande e exigir ordenação. Se ambas implementam corretamente a expressão relacional, entregam o mesmo resultado.

O sistema precisa escolher antes de saber quantas páginas estarão no cache, como os valores do filtro se distribuem naquele instante, quanto trabalho concorrente disputará I/O ou se um operador extrapolará memória. Não existe ainda uma duração real dessa execução para consultar.

O otimizador usa uma representação: estatísticas de catálogo, hipóteses de seletividade, fórmulas de operadores, pesos de hardware e um conjunto de alternativas que conseguiu explorar. “Mais barato” significa vencedor nessa comparação. Só depois a execução oferece linhas, leituras, CPU, memória e tempo observados.

Esse limite costuma desaparecer na conversa operacional. Um número no plano ganha aparência de medida. O caminho escolhido passa a ser chamado de ótimo sem que se informe o objetivo ou o espaço de busca. A arquitetura original era mais honesta: ela tomava uma decisão explícita sob incerteza.

A promessa declarativa transferiu autoridade

SQL permite descrever o resultado desejado sem ordenar operações de armazenamento. A consulta continua válida quando o banco cresce, surgem índices ou o equipamento muda. A contrapartida é delegar ao mecanismo de otimização a escolha física.

O artigo de 1979, Access Path Selection in a Relational Database Management System, descreve quatro fases. A análise produz uma representação da consulta. A otimização escolhe uma especificação de acesso. A geração cria código. A execução vem por último. A sequência define o contrato: a rota é escolhida antes que a corrida possa fornecer evidência própria.

Uma especificação de acesso registra qual relação vem primeiro, se uma varredura ou índice será usado, qual ordem de junção será seguida e quais propriedades de ordenação merecem sobreviver. Não é uma segunda definição do significado.

Correção e economia física são questões distintas. Resultado errado é falha semântica. Resultado certo, mas tardio, pode revelar erro de estimativa, de planejamento ou de comportamento em execução. Uma rota rápida com um parâmetro e cache quente não prova que será a melhor para outros valores e condições.

O catálogo não era um espelho perfeito

O System R mantinha estatísticas como NCARD, quantidade de tuplas; TCARD, páginas ocupadas; P, ocupação de páginas; ICARD, chaves distintas em um índice; e NINDX, páginas do índice. Com esse resumo, era possível comparar caminhos sem ler tudo primeiro.

As estatísticas eram inicializadas e atualizadas periodicamente por UPDATE STATISTICS. O texto explica por que não acompanhavam cada mudança: escrita de catálogo e bloqueios cobrariam um preço alto. A imagem do banco era deliberadamente econômica.

Uma estatística comprime a realidade. Aumentar frequência e detalhe melhora a observação, mas custa processamento, armazenamento e coordenação. Coletar pouco reduz esse custo e aumenta o risco de descrever um estado antigo. A questão não é apenas se a manutenção “foi feita”; é qual informação valeu a pena conservar.

Essa troca permanece atual. Amostra, histograma, correlação entre colunas, diferenças por partição e momento da coleta definem o que o planejador consegue enxergar. Mesmo uma estatística nova continua aproximada.

Seletividade não é cardinalidade

Para cada predicado, o System R estimava uma seletividade: a fração provável de tuplas aprovadas. Uma igualdade apoiada por índice podia usar a quantidade de chaves distintas. Sem evidência melhor, havia padrões práticos. O artigo menciona um décimo para igualdade sem índice, um terço para intervalo aberto e um quarto para intervalo fechado.

Os autores dizem que esses números não têm significado além de produzir uma ordem aproximada. Não são leis dos dados. São escolhas para que a decisão continue quando a informação termina.

Condições conectadas por AND podiam ter suas seletividades multiplicadas. Isso embute independência. Em bases reais, cidade e CEP, tipo de produto e preço, modalidade de contrato e duração se correlacionam. O produto de probabilidades marginais pode imaginar raridade onde existe concentração.

Cardinalidade é a quantidade resultante de linhas. O raciocínio QCARD combina tamanho das relações e fatores de seletividade. Esse volume previsto entra no custo dos operadores seguintes. Se o lado externo de uma junção é subestimado, um laço aninhado parece repetir pouco trabalho; na prática, pode repeti-lo milhões de vezes. Se um filtro é superestimado, um índice eficiente parece caro.

Portanto, seletividade é proporção e cardinalidade é contagem. O erro passa de uma para outra e se multiplica ao longo das junções. Muda intermediários, memória, método físico e ordem.

Leis e coautores mostraram em 2015 que erros de cardinalidade normalmente prejudicavam mais os planos do que pequenas falhas na função de custo. A retrospectiva de 2025 ainda aponta cardinalidade, robustez e adaptação como questões abertas. O elo frágil identificado pela arquitetura continua relevante.

Uma moeda comum para recursos diferentes

A fórmula publicada foi:

COST = PAGE FETCHES + W × (RSI CALLS)

Leituras de página representavam entrada e saída. Chamadas à Research Storage Interface aproximavam trabalho de CPU. O peso W dizia quanto um componente valia diante do outro. Incluir CPU foi um avanço, mas o total não era expresso em segundos.

O modelo não conhecia perfeitamente cache, sequencialidade, contenção, derramamento para disco, comportamento do equipamento ou quanto do resultado o cliente consumiria. A função fornecia uma moeda para classificar alternativas heterogêneas.

O menor valor é legitimamente o menor custo dentro do modelo. Ser mais rápido é uma hipótese derivada. Ser globalmente ótimo exigiria que objetivo e universo de alternativas fossem completos e declarados.

Hoje, a documentação do PostgreSQL mantém a diferença visível. Os custos são unidades convencionais dependentes da plataforma, não milissegundos. EXPLAIN mostra estimativas sem executar; EXPLAIN ANALYZE executa e adiciona linhas e tempos reais. Previsão e veredito ocupam saídas diferentes.

O que existe dentro de um plano

Caminho de acesso responde como chegar a uma relação-base: varredura, índice ou outra rota disponível. Operador físico responde como juntar, ordenar ou agregar. Ordem de junção responde quais relações serão combinadas antes e quais intermediários alimentarão o restante.

Um índice pode filtrar e também fornecer ordem. Uma junção seletiva realizada cedo diminui todo o fluxo posterior. Um operador adequado a uma entrada pequena quebra quando a cardinalidade real é grande. Uma ordenação aparentemente cara pode evitar outra mais adiante.

Essas decisões se influenciam, mas não são sinônimas. Ao investigar um plano, é útil perguntar se o problema nasceu da ausência de um caminho, da estimativa que trocou a ordem, do limiar de um operador ou da perda de uma propriedade física.

Equivalência relacional garante o significado sob as regras do idioma. Não garante equivalência de recursos. O planejador atua justamente no espaço entre as duas afirmações.

A opção guardada por uma ordem interessante

Um acesso por índice pode custar mais do que varrer a relação agora, mas entregar linhas ordenadas pela chave de uma próxima junção, de um GROUP BY ou do ORDER BY final. Essa propriedade pode eliminar uma ordenação futura.

O System R conservava o plano não ordenado mais barato e o melhor plano para cada “ordem interessante”. Produzir as mesmas linhas não bastava para que dois planos parciais fossem intercambiáveis: suas propriedades físicas alteravam o custo restante.

Uma ordem tem valor de opção. Pagar mais em uma etapa preserva uma possibilidade futura. Se o sistema mantivesse apenas o vencedor local, confundiria preço imediato com consequência total.

Essa organização também limitava memória de busca. Não era necessário guardar tudo. Bastava preservar os representantes mais baratos das classes capazes de mudar as próximas decisões.

O espaço de busca precisava caber no tempo

O número de ordens de junção cresce combinatoriamente. Enumerar cada permutação aproxima um crescimento fatorial. O planejador poderia gastar mais tempo procurando do que a execução economizaria.

O System R usou programação dinâmica. Construiu planos para subconjuntos de relações, guardou os melhores representantes por propriedade de ordenação e reutilizou-os na expansão. Produtos cartesianos eram adiados sempre que possível, pois tendem a criar intermediários grandes sem condição de junção.

O artigo descreve a busca em termos de subconjuntos e ordens interessantes e relata otimização de junções com oito tabelas em segundos em um IBM 370/158. A disciplina tornou o método prático.

Ainda assim, poda não é prova de que toda forma física concebível foi vista. A programação dinâmica encontra o melhor candidato do espaço definido pelo enumerador, pelos operadores, pelas transformações e pelas regras de retenção. “Ótimo global” sem essas condições é uma afirmação maior do que a evidência.

Tempo de otimização e tempo de execução também precisam de contas separadas. Uma busca ampla pode valer a pena para análise cara e ser desperdício para consulta curta repetida. Planos genéricos preparados economizam planejamento, porém podem falhar quando o melhor caminho depende muito do parâmetro.

A equipe publicou a incerteza

A conclusão de 1979 reconhece que custos previstos frequentemente eram imprecisos como valores absolutos. Também relata que o melhor caminho testado era escolhido na maioria dos casos e solicita mais validação. Um ranking pode funcionar sem prever com exatidão a duração.

Em 1986, Mackert e Lohman compararam estimativas do R* com uso real de recursos. Boa parte do modelo de I/O se sustentou, mas CPU precisava de detalhe; hipóteses sobre buffers importavam; e laços aninhados eram difíceis porque cardinalidade da junção, cardinalidade externa e páginas disponíveis interagiam.

O teste empírico é parte do valor do modelo. Fórmulas não recebem imunidade. Onde os desvios se acumulam, estatísticas, coeficientes, pressupostos de operadores e retorno da execução podem ser alterados.

O trabalho posterior da IBM sobre estatísticas just-in-time segue esse princípio. Quando uma estatística coletada separadamente está ausente ou velha, o otimizador pode adquirir informação direcionada ao descobrir sua necessidade. O objetivo não é saber tudo, e sim pagar por evidência onde ela muda a decisão.

Liderança com crédito coletivo

Patricia G. Selinger entrou na IBM Research em 1975. A história da IBM registra sua liderança no otimizador do System R, depois no R* e em organizações de tecnologia de banco de dados. Ela se tornou IBM Fellow em 1994, foi eleita para a National Academy of Engineering dos Estados Unidos em 1999 e se aposentou da IBM em 2018.

O artigo de 1979 tem cinco autores: P. Griffiths Selinger em parceria com Morton M. Astrahan; também Donald D. Chamberlin, além de Raymond A. Lorie e, por fim, Thomas G. Price. Na história oral do Computer History Museum, Chamberlin diz que Selinger organizou o trabalho e o artigo decisivo, ao mesmo tempo em que destaca Lorie, Price e Astrahan. A história mais ampla inclui o modelo relacional de Edgar Codd, o SQL de Chamberlin e Raymond Boyce, o compilador de Lorie e o programa System R.

Crédito coletivo torna a liderança mais precisa. Selinger reuniu estatísticas, estimativas, propriedades e busca em um contrato implementável. Não é necessário chamá-lo de inteligência artificial nem transformar uma arquitetura de equipe em biografia de inventora solitária.

A fronteira que permitiu evolução

O resultado duradouro não foi uma rota definitiva. Foi separar significado lógico de método físico. Estatísticas podem enriquecer, correlações podem ser modeladas, pesos podem mudar, operadores podem surgir e retorno de execução pode provocar novo planejamento sem reescrever a intenção declarada.

O plano escolhido é uma previsão autorizada: venceu a comparação que o sistema realizou com a evidência disponível. Ainda não venceu a realidade. Guardar a previsão e a observação permite aprender com a diferença.

Um otimizador maduro não promete nunca errar. Ele deixa claro o que supôs, o que escolheu e o que aconteceu.

Fontes