Algoritmos para Operações de
Agregação e para o operador
de Agrupamento GROUP BY
AULA 20
Profa. Sandra de Amo
GBC053 – BCC
Operações de Agregação
Select AVG(S.Idade)
From Sailors S
SID Idade
1
1
5
25
32
19
Agreg
25
Algoritmo Básico:
7 18
9 20

Scan da relação Sailors
11 21 referentes à operação de

Mantém em uma variável Agreg as informações
AVG sobre os valores do atributo Idade

Custo = custo de um scan da relação S
Avg(n) = (t_1+t_2+...+t_n)/n
Avg(n) = (Avg(n-1)*(n-1) + t_n)/n
Operações de Conjuntos
Select AVG(S.Idade)
From Sailors S
SID Idade
1
1
5
25
32
19
Agreg
28,5
Algoritmo Básico:
7 18
9 20

Scan da relação Sailors
11 21 referentes à operação de

Mantém em uma variável Agreg as informações
AVG sobre os valores do atributo Idade

Custo = custo de um scan da relação S
Operações de Conjuntos
Select AVG(S.Idade)
From Sailors S
SID Idade
1
1
5
25
32
19
Agreg
25,33
Algoritmo Básico:
7 18
9 20

Scan da relação Sailors
11 21 referentes à operação de

Mantém em uma variável Agreg as informações
AVG sobre os valores do atributo Idade

Custo = custo de um scan da relação S
Operações de Agregação





SUM
AVG
COUNT
MIN
MAX
Exercicio 1: Mostre que SUM, COUNT, MIN e MAX
são operações incrementais
Operações de agregação são operações incrementais :
Op(a1,...,an) = F(Op(a1,...,an-1) an, n)
Avg(a1,...,an) = F(Op(a1,...,an-1) an, n)
onde F(x,y,n) = (x*(n-1) + y)/n
Operador de Agrupamento: GROUP BY
SELECT S.Status, AVG(S.Idade)
FROM Sailors S
GROUP BY S.Status
Técnicas:
 Ordenação
 Hashing
Algoritmo para GROUP BY baseado
em ordenação
Etapa 1: Fase da ordenação
Ordena-se a relação pelo atributo do Group by
Etapa 2: Fase do agrupamento
Faz-se um scan da relação ordenada armazenando-se na variável Agreg o
resultado da operação de agregação para cada grupo
Custos:
Etapa 1 = 2M([LogB-1 M/B] + 1)
Etapa 2 = M
Custo total = 2M([LogB-1 M/B] + 1) + M
Exercicio 2: Projetar um algoritmo otimizado (baseado em ordenação)
para o GROUP BY e calcular seu custo
Algoritmo para GROUP BY baseado
em Hash



Fase do Particionamento

Particiona a relação R pelos atributos de agrupamento – do GROUP
BY

Desta maneira: elementos de um mesmo grupo só podem estar numa
mesma partição.

O particionamento é feito de modo que o número de partições seja
B-1 e cada partição caiba inteira na memória em B-1 páginas.

Para isso, é preciso que o tamanho do buffer (B) seja > M
onde M = número de páginas da relação R.
Fase do Agrupamento

Carrega partição inteira de R

Aplica algoritmo de ordenação interna pelos atributos do
agrupamento (Group By).

Varre a partição (ordenada) e calcula-se o resultado da função de
agregação sobre cada grupo
CUSTO = 2M + M = 3M
Fase do Particionamento
Relação R
Particionada
Relação R
Pt 1 Pt 2 Pt 3 Pt 4 Pt 5 Pt 6
Distribui usando hash h
sobre os atributos de
Página de R agrupamento (presentes
sa cláusula GROUP BY)
Disco
M páginas
Buffer tem capacidade para B páginas,
onde B – 1 = número de partições
Disco
M páginas
Fase do Agrupamento
Relação R’
Particionada
Relação R particionada
Partição n
Ordena pelos atributos
do Group By
Varre, calcula a operação
de agregação sobre cada grupo e
insere tupla (Val-Grupo,Val-Agreg)
no resultado
Disco
M páginas
Resultado
Buffer tem capacidade para B páginas,
onde B – 1 é suficiente para conter uma partição
inteira de R.
Disco
T páginas
Exemplo:
Seja R(A,B,C) M = 1000 páginas, B = 41
Consulta: SELECT R.A, Sum(B) FROM R GROUP BY R.A
1.
Fase do Particionamento:
1.
40 partições de 1000/40 = 25 páginas cada
2.
Custo = 1000 + 1000 = 2000
3.
Resultado no disco após a fase do particionamento: 1000 páginas,
particionadas em 40 partições, onde cada partição tem 25 páginas.
4.
Registros com mesmo valor de A estão em uma mesma partição
2.
Fase do Agrupamento
1.
Para i = 1, ..., 40
1.
Carrega-se partição i de 25 páginas
2.
Ordena-se internamente
3.
Calcula-se o output (o output tem número de páginas <= 25)
4.
Custo = 1000
3.
Custo total = 2000 + 1000 = 3000
GROUP BY usando um índice
SELECT R.A, Sum(R. B)
FROM R
GROUP BY R.A



CUSTO = N
onde N = número de páginas
do indice I
Suponha que tenhamos um índice denso
com chave (A,B)
Logo: o arquivo de índice contém todas
as informações necessárias para se fazer a
consulta.
Portanto: calcula-se a consulta, usando-se
as técnicas de ordenação ou Hash
(dependendo do tipo do índice)
Select I.A, Sum(I.B)
FROM I
GROUP BY I.A
Onde I = arquivo de índice
GROUP BY usando um índice
agrupado denso B-TREE
SELECT R.A, Sum(R. B)
FROM R
GROUP BY R.A





Suponha que tenhamos um índice do
tipo B-TREE (ou ISAM) com chave A,
Usa-se o indice para procurar as páginas
de dados referentes a cada valor do
atributo de agrupamento A
Para cada valor do atributo de
agrupamento, carrega-se estas páginas de
dados na memória (possivelmente vão
caber todas na memória)
Varre-se tais páginas na memória e
executa-se a operação de agregação.
Evita-se assim a fase de ordenação da
operação de agrupamento