Starburst
Optimização de Interrogações
Francisco Santos
Agenda







Introdução
Objectivo do Starburst
Processamento Interrogações
Query Graph Model
Reescrita de Interrogações
Optimização do Plano
Bibliografia
Introdução

O que é a optimização de interrogações?

SQL é uma linguagem declarativa e, como tal, não define o
“procedimento” para a execução de uma interrogação

No entanto, a linguagem permite expressar a mesma
interrogação de formas diferentes, podendo levar o SGBD
a escolher um procedimento de execução (plano) subóptimo

Opimização é o processo de escolha do plano mais
eficiente para a execução da interrogação
Introdução

Como optimizar uma interrogação?

O optimizador deve elaborar uma representação interna que lhe
permita conhecer a interrogação:

Quais as tabelas acedidas? Que predicados foram empregues?
Existe junção entre tabelas? Existe aninhamento de interrogações?

Usando a rep. interna, o optimizador transforma as interrogações
na sua forma mais declarativa possível

Tendo a interrogação na sua forma mais declarativa possível, é
escolhida a estratégia para a sua execução:

Exemplo: acesso ao ficheiro através de um Heap, Indice, Sequência;
Join usando o algoritmo de merge-sort, nested loops, hash join, …
Objectivo do Starburst

O objectivo do projecto Starburst (IBM) é o de:

“Analisar as mudanças necessárias aos SGBDs tradicionais de
forma a corresponder as necessidades das novas aplicações e
tecnologias.” - [SCFL+86]


Exemplos de ‘novas’ aplicações incluem: aplicações estatísticas,
CAD, GIS, sistemas gestão documental
Como responder às necessidades das novas aplicações
preservando as vantagens dos SGBDs tradicionais?

Controlo de concorrência, recuperação, linguagem especializada
para a formulação de interrogações
Processamento Interrogações
Query Graph Model
Exemplo:


alunos( aid:string, nome:string, idade:integer, media:real )
inscricoes( aid:string, cid:string, nota:integer )
aid FK Alunos

Q: “Quais são os alunos: aid e nome, cuja nota no TFC é igual
ou superior em três unidades à sua média de curso?”

SELECT Q1.aid, Q1.nome
FROM alunos Q1
WHERE Q1.aid IN
( SELECT Q3.aid
FROM inscricoes Q3
WHERE Q3.nota >= Q1.media + 3
AND Q3.cid = ‘TFC’ )
Query Graph Model
Construtores para o Query Graph Model (QGM):
Qi’s – iteradores, representam acessos a tabelas:
Setformers (F) – podem aparecer no resultado final
Quantifiers (, ) – usados para eliminar tuplos do resultado final
Conjunção de Predicados:
p1  p2  …  pn
p1
…
pn
Tabelas:
Mat.
Der.
Materializadas – existe na BD
Derivadas – gerada a partir de uma operação (interrogação)
Query Graph Model
T1 aid nome
OP1:
Q1(F)
Q2()
aid
T2
OP2:
Q3(F)
Q3.nota >=
Q1.media + 3
Q3.cid = ‘TFC’
Q1.aid = Q2.aid
…
…
alunos
inscricoes
Query Rewrite
Regra 1:
COND: existe no máximo um tuplo da sub-interrogação que
corresponde a cada tuplo da interrogação principal.
ACÇÃO: converter iterador do tipo ‘’ num iterador do tipo ‘F’.
Regra 2:
COND: OP1 é SELECT, OP2 é SELECT, Q2 iterador do tipo ‘F’,
política de eliminação de duplicados é compatível
ACÇÃO: juntar OP1 e OP2, se OP2 elimina duplicados então OP1
também elimina duplicados
Query Graph Model
head.distinct = true
T1 aid nome
OP1:
Q1(F)
Q2()
body.distinct = preserve
Q1.aid = Q2.aid
aid
T2
OP2:
Q3(F)
Q3.nota >=
Q1.media + 3
Q3.cid = ‘TFC’
head.distinct = true
body.distinct = preserve
…
…
alunos
inscricoes
Query Rewrite
aid nome
Q1.aid = Q3.aid
Q1(F)
Q3(F)
Q3.nota >= Q1.media + 3
Q3.cid = ‘TFC’
T1
OP1:
…
…
alunos
inscricoes
Plan Optimization





Optimizador escolhe o plano de menor custo para a execução
da interrogação anterior
Através de uma gramática, as operações de alto nível (caixas
do QGM) são convertidas em operações de baixo nível
Esta gramática é designada: Grammar of STrategy AlteRnatives
(STARs)
As operações de baixo nível são designadas por: LOw-LEvel
Plan OPerations (LOLEPOPs)
Exemplos:




ACCESS: converte uma tabela materializada numa cadeia de
tuplos
GET: aplica uma conjunção de predicados a um conjunto de tuplos
(ref.dos pelo seu TID) e projecta as colunas da tabela acedida
SORT: ordena uma cadeia de tuplos segundo um ou mais campos
JOIN: faz a junção de duas cadeias de tuplos, obedecendo a uma
conjunção de predicados
Passo 1 – Plano Acesso a Tabelas
Encontrar métodos eficientes para aceder aos ficheiros; guardar os melhores planos.
STARs para acesso aos ficheiros:
TableAccess(T,C,P) =
TableScan(T,C,P)
i I(T) GET(TableScan(i, {TID}, P), T, C, P ),
Cond1
TableScan(T,C,P) =
ACCESS(Heap, T, C, P),
Armazenamento = ‘Heap’
ACCESS(B+tree, T, C, P),
Armazenamento = ‘B+tree’
Passo 1 – Plano Acesso a Tabelas
Exemplo: relação ‘Inscricoes’, assumindo índice B+tree ‘Index1’ sobre as colunas
‘<aid,cid>’:
Apontadores para
definições alternativas
TableAccess
Inscricoes
Argumentos:
{aid, nota}
{cid = ‘TFC’}
Nome da Função
Passo 1 – Plano Acesso a Tabelas
Exemplo: relação ‘Inscricoes’, assumindo índice B+tree ‘Index1’ sobre as colunas
‘<aid,cid>’:
TableScan
GET
Inscricoes
{aid, nota}
Inscricoes
{cid = ‘TFC’}
{aid, nota}
{cid = ‘TFC’}
TableScan
Index1
{TID}
{cid = ‘TFC’}
Passo 1 – Plano Acesso a Tabelas
Exemplo: relação ‘Inscricoes’, assumindo índice B+tree ‘Index1’ sobre as colunas
‘<aid,cid>’:
Plano 2:
ACCESS
GET
-Ordenação segundo
‘<aid,cid>’
Heap
-{cid = ‘TFC’}
Inscricoes
Inscricoes
{aid, nota}
{aid, nota}
{cid = ‘TFC’}
{cid = ‘TFC’}
Plano 1:
-Tuplos desordenados
-{cid = ‘TFC’}
ACCESS
B+tree
Index1
{TID}
{cid = ‘TFC’}
Passo 2 – Plano Junção Tabelas
Encontrar métodos eficientes para juntar as tabelas
JoinMethod(T1,T2,P) =
JOIN(NL, Glue(T1, ), Glue(T2, JPIP), JP, P – (JPIP))
JOIN(HA, Glue(T1, ), Glue(T2, IP), HP, P – IP),







HP  
NL – nested loops join
HA – hash join
P – todos os predicados elegíveis
JP – predicados da junção
IP – predicados só elegíveis para a relação interior (i.e. só referem
colunas da relação interior)
HP – predicados da junção em forma de igualdade (ex.: T1.x = T2.y )
Glue(T, P) – acede aos tuplos da tabela ‘T’, que respeitam os
predicados ‘P’, usando o planos de menor custo
Passo 2 – Plano Junção Tabelas
Apontadores para
definições alternativas
JoinMethod
Alunos
Inscricoes
Argumentos:
{T1.aid = T2.aid,
T2.nota >= T1.media
+ 3, T2.cid = ‘TFC’}
Nome da Função
Passo 2 – Plano Junção Tabelas
JOIN
JOIN
NL
HA
Glue(T1, )
Glue(T1, )
Glue(T2, JPIP)
Glue(T2, IP)
JP
HP
P – (JPIP)
P – IP
Join predicates = JP = {T1.aid = T2.aid, T2.nota >= T1.nota + 3}
Inner predicates = IP = {T2.cid = ‘TFC’}
Hashable predicates = HP = {T1.aid = T2.aid}
Passo 2 – Plano Junção Tabelas
Exemplo: geração do plano para o algoritmo nested loops
JOIN
NL
Glue
Glue
Inscricoes
Alunos

JP
P – (JPIP) = 
JPIP
Join predicates = JP = {T1.aid = T2.aid, T2.nota >= T1.nota + 3}
Inner predicates = IP = {T2.cid = ‘TFC’}
Passo 2 – Plano Junção Tabelas
Exemplo: geração do plano para o algoritmo nested loops
JOIN
ACCESS
NL
GET
Heap
Inscricoes
Alunos
{aid, nome, media}

JP

{aid, nota}
JPIP
Index Nested Loop Join:
• para cada tuplo ‘Ta’ da tabela Alunos pesquisar
no índice dos tuplos ‘Ti’ da tabela Inscricoes
aqueles cujo aid coincide: Ta.aid = Ti.aid
• se Ti.cid = ‘TFC’ e Ti.nota >= Ta.media + 3,
adicionar tuplo <Ta.aid, Ta.nome> ao resultado
• Custo = balunos + nalunos * cindex1
ACCESS
B+tree
Index1
{TID}
JPIP
Passo 2 – Plano Junção Tabelas
Exemplo: geração do plano para o algoritmo hash join
JOIN
ACCESS
HA
ACCESS
Heap
Heap
Alunos
Inscricoes
{aid, nome, media}

HP
{aid, nota}
P – IP
IP
Hash Join:
• particionar Alunos e Inscricoes com uma função de hash ‘h’
sobre os atributos hashable da junção: HP = {T1.aid = T2.aid}
• construir um índice em memória para a relação mais pequena
• tuplos que satisfaçam a condição Ta.aid = Ti.aid, Ti.cid = ‘TFC’
e Ti.nota >= Ta.media + 3 adicionar ao resulado
• Custo = 3 * (balunos + binscricoes )
Bibliografia

[SCFL+86] - P. Schwarz, W. Chang, J. C. Freytag, G. Lohman, “Extensibility in the Starburst Database System”, IBM
Almaden Research Center, 1986

[HFLP89] - L. Haas, J. Freytag, G. Lohman, H. Pirahesh, “Extensible Query Processing in Starburst”, IBM Almaden
Research Center, 1989

[LFL88] – M. Lee, J. Freytag, G. Lohman, “Implementing an Interpreter for Functional Rules in a Query Optimizer”, IBM
Almaden Research Center, 1988

[PHH92] – H. Pirahesh, J. Hellerstein, W. Hasany, “Extensible/Rule Based Query Rewrite Optimization in Starburst”, IBM
Almaden Research Center, 1992

[Loh88] – G. Lohman, “Grammar-like Functional Rules for Representing Query Optimization Alternatives”, IBM Almaden
Research Center, 1988

[SKS06] - Silberschatz, Korth, Sudarshan, “Database System Concepts”, Cap. 2 e 13, McGraw-Hill, 5th edition, 2006

[RG03] – R. Ramakrishnan, J. Gehrke, “Database Management Systems”, Cap. 4, McGraw-Hill, 3rd edition, 2003

[Ives05] – Z. Ives, “Query Optimization Strategies”, University of Pennsylvania, 2005,
www.seas.upenn.edu/~zives/cis650/slides/6-query-opt.ppt

[PHH92] – H. Pirahesh, J. Hellerstein, W. Hasan, “Extensible/Rule Based Query Rewrite Optimization in Starburst”,
SIGMOD Conference, 1992, www.mcs.vuw.ac.nz/~db/publications/comp443Prest.ppt

[WikiHash] – Wikipedia, “Hash Function”, http://en.wikipedia.org/wiki/Hash_function