of 41/41
INF70 – Gerenciamento de Banco de Dados 2 Ordenação Externa Ilmério Reis da Silva [email protected] www.facom.ufu.br/~ilmerio/gbd2 UFU/FACOM/BCC

SISTEMAS DE BANCO DE DADOS - SBD - facom.ufu.brilmerio/gbd2/gbd2_s5_sorting.pdf · • Two-way Merge Sort • External Merge Sort • Arvore-B+ e Sort. UFU/FACOM/BCC GBD2 Página:3

  • View
    218

  • Download
    0

Embed Size (px)

Text of SISTEMAS DE BANCO DE DADOS - SBD - facom.ufu.brilmerio/gbd2/gbd2_s5_sorting.pdf · • Two-way...

  • INF70 Gerenciamento de Banco de Dados 2Ordenao Externa

    Ilmrio Reis da [email protected]/~ilmerio/gbd2UFU/FACOM/BCC

    mailto:[email protected]

  • UFU/FACOM/BCC

    Roteiro

    Fundamentos

    Two-way Merge Sort

    External Merge Sort

    Arvore-B+ e Sort

  • UFU/FACOM/BCC GBD2 Pgina:3

    Fundamentos

    Fundamentos

  • UFU/FACOM/BCC GBD2 Pgina:4

    Contexto

  • UFU/FACOM/BCC GBD2 Pgina:5

    Sorting parte do executor de consultas

    Estudamos arquivos, buffers e ndices Vamos estudar execuo de consultas Antes de estudar os vrios operadores da lgebra relacional Antes de estudar como esses operadores so combinados em

    um plano de consulta Um operador bsico de grande importncia :

    EXTERNAL SORT

  • UFU/FACOM/BCC GBD2 Pgina:6

    Aplicaes do operador SORT Uso explcito: SELECT a, b, c FROM r ORDER BY a, b Bulk-Loading (construo bootom-up de de rvore B+) Eliminao de duplicatas SELECT DISTINCT a, b, c FROM r Melhorias no desempenho de alguns operadores, por

    exemplo, juno

  • UFU/FACOM/BCC GBD2 Pgina:7

    Definio Arquivo Ordenado

    Um arquivo de registros est ordenado (sorted) com respeito a uma chave de ordenao (sort key) e uma ordem , se para todo par de registros r1, r2 com r1 precedendo r2 no arquivo, ento suas chaves correspondentes esto na ordem

    r1 precede r2 r1.k r2.k

  • UFU/FACOM/BCC GBD2 Pgina:8

    Abordagem para o Problema O Problema:

    o arquivo no cabe na memria

    Abordagem Ordenar um arquivo de tamanho arbitrrio considerando

    trs pginas disponveis no buffer (Two-way Merge Sort) Refinar o algoritmo com um uso mais efetivo do buffer

    (External Merge Sort) Melhorias (Replacement Sort)

  • UFU/FACOM/BCC GBD2 Pgina:9

    Two-Way Merge Sort

    Two-Way Merge Sort

  • UFU/FACOM/BCC

    Two-way Merge Sort

    5,7 10,6 8,9 7,3 5,7

    Buffer Pool

    Pginas de Input

    Pgina de Output

    4,21,3

  • UFU/FACOM/BCC

    1,3 4,2 5,7 10,6 8,9 7,3 5,7

    Buffer Pool

    Ordena

    1,3

    Uma pgina paraConstruir o output

    Pginas de Input

    / 7*2 I/OProduz 7 subarquivos ordenados

    1,3 2,4 5,7 6,10 8,9 3,7 5,7

    Etapa 0 Ordena registros em cada pgina

  • UFU/FACOM/BCC

    1,2

    3,4

    5,6

    7,10

    3,7

    8,9

    5,7

    7 x 2 I/OProduz 4 subarquivos ordenados

    1,3 2,4 5,7 6,10 8,9 3,7 5,7

    Etapa 1 Merge de pares de pginas

  • UFU/FACOM/BCC

    1,2

    3,4

    5,6 3,7

    8,9

    5,7

    7 x 2 I/O

    1,2

    3,4

    5,6

    7,10

    3,5

    7,7

    8,9

    7,10

    Produz 2 subarquivos ordenados

    Etapa 2 Ordena pares de subarquivos ordenados

  • UFU/FACOM/BCC

    7 x 2 I/O

    1,2

    3,4

    5,6

    7,10

    3,5

    7,7

    8,9

    1,2

    3,34,55,6

    7,7

    7,89,10

    Produz 1 arquivo ordenado

    Etapa 3 Ordena par de subarquivos ordenados

  • UFU/FACOM/BCC

    Seja N o nmero de pginas do arquivo Considere que N = 2s

    Etapa 0 : 2s subarquivos ordenados Etapa 1 : 2s-1 subarquivos ordenados Etapa 2 : 2s-2 subarquivos ordenados ... Etapa s : 1 arquivo ordenado Total de etapas = s+1 = log2N + 1

    Genericamente

    Anlise nmero de etapas

  • UFU/FACOM/BCC

    Nmero de etapas = log2N + 1

    Nmero de I/O por etapa = 2N

    Total de I/O = 2N(func_teto(log2N) + 1)

    O(N log N)

    Anlise Custo em IOs

  • UFU/FACOM/BCC

    External Merge Sort

    External Merge Sort

  • UFU/FACOM/BCC

    External Merge Sort

    Buffer com B pginas Etapa 0 :

    B pginas so carregadas no buffer, ao invs de uma a uma. B pginas so ordenadas e so criados N/B arquivos

    ordenados. Etapas i=1,2,...

    B-1 pginas so utilizadas no buffer 1 pgina usada para construir o output.

  • UFU/FACOM/BCC

    Esquema de utilizao do buffer no External Merge Sort Etapas 1, 2, ...

    DISCO

    ...

    Input 1

    Input 2

    Input B-1

    output

    B pginas no Buffer

    DISCO

    ...

    Pginas do arquivodesordenado

    Pginas do arquivoordenado

  • UFU/FACOM/BCC

    1,3 5,2 5,7 10,6 4,6 3,6 4,71,3

    1,3

    5,2

    10,6

    B = 4

    5,7

    1,2

    3,5

    5,6

    7,10

    3,4

    4,6

    6,7

    Etapa 0 External Merge Sort

  • UFU/FACOM/BCC

    1,2 3,5

    1,2

    3,3

    4,4

    5,5

    6,6

    6,7

    7,10

    1,2

    3,5

    5,6

    7,10

    3,4

    4,6

    6,7

    Etapa 1 External Merge Sort

  • UFU/FACOM/BCC

    Nmero de arquivos produzidos na etapa 0 = N/B = N1

    Nmero de etapas = logB-1N1 + 1 Nmero de I/O por etapa = 2N

    Total de I/O = 2N(logB-1N1 + 1) ou

    Anlise Custo External Merge Sort

  • UFU/FACOM/BCC

    Exemplo

    B = 5 N = 108 pginas Etapa 0 : 108/5 = 22 arquivos,

    21 de 5 pginas e 1 de 3 pginas Etapa 1 : 22/4 = 6 arquivos

    5 de 20 pginas e 1 de 8 pginas Etapa 2 : 6/4 = 2 arquivos

    1 de 80 pginas e 1 de 28 pginas Etapa 3 : 1 arquivo ordenado de 108 pg Total de I/O = 2*108*4 = 864 2*108(log422 + 1) = 864

  • UFU/FACOM/BCC

    Comparao de Custos : n de etapas

    4581015301000.000.000

    44791426100.000.000

    3468122310.000.000

    335710201.000.000

    3356917100.000

    224571310.000

    22345101.000

    112347100

    B=257B=129B=17B=9B=5B=3N

    Numero de I/O = etapas * 2N

  • UFU/FACOM/BCC

    Comparao com Two-way

  • UFU/FACOM/BCC GBD2 Pgina:26

    Melhorias : minimizando o nmero de subarquivos do passo 0

    Replacement Sort Seja B o nmero de pginas do bufferpool Reserve uma para entrada(Inp) e outra para sada(Out) B-2 pginas formaro o current-set (CSet) A cada rodada grava-se um current-run(CRun)

  • UFU/FACOM/BCC GBD2 Pgina:27

    Loop de uma rodada do Replacement Sort

  • UFU/FACOM/BCC GBD2 Pgina:28

    Replacement Sort - Consideraes finais

    Registros de tamanho varivel dificultam o processo. Seleo da menor chave do CSet pode usar uma estrutura de

    dados, por exemplo, um max Heap (rvore onde todo filho tem chave menor ou igual ao pai)

    Em mdia o tamanho do subarquivo de cada rodada igual a 2B

    Exemplo: B = 6, 1 reg/pg. Logo temos 4 reg no Cset

    700

  • UFU/FACOM/BCC GBD2 Pgina:29

    Outras melhorias no Sort Externo

    Diminuindo do Custo Mdio de Cada IO IO baseado em blocos de vrias pginas pode melhorar o

    tempo mdio de cada IO (diminui o nmero de seeks), mas pode aumentar nmero de passos

    Double Buffering pode ser usado para paralelizar trabalho da CPU enquanto aguarda requisio de IO

  • UFU/FACOM/BCC GBD2 Pgina:30

    Sort Externo com IO baseado em Blocos

    unidade de leitura e gravao = bloco com b pginas diminui nmero de seeks, portanto o custo mdio do IO b pginas para Out merge de no mximo (Bb)/b = B/b -1 o sort merge externo com b pginas de output e merge de

    (Bb)/b subarquivos por passo Exemplo:B = 10

    SE b = 1, merge de nove subarquivos por passo SE b = 2, merge de 4 subarquivos por passo

    aumenta-se o nmero de pasos, portanto o nmero de IOs melhoria depende de b, tamanho do arquivo, caractersticas

    de desempenho do disco.

  • UFU/FACOM/BCC GBD2 Pgina:31

    Anlise Sort Externo com IO baseado em Blocos

    Anlise incluindo Replacement Sort no Passo 0 Passo 0: produz N2 = N/(2B) subarquivos Passos 1, 2, ...: merge F = B/b -1 subarquivos por vez NroPassos = 1+ logFN2, sendo que originalmente seria

    NroPassoMerge Sort Original = 1 + logB-1 N/B

  • UFU/FACOM/BCC GBD2 Pgina:32

    Exemplo Sort Externo com IO baseado em Blocos

    Exemplo: N = 1.000.000, B = 5000, b = 32, N2 = piso(1.000.000/ (25.000)) = 100 F = piso(5.000/32) 1 = 155 NroPassos = 1 + teto(log155 100) = 2

    Consideraes finais Necessita maior rea de bloco para manter nmero de

    passos semelhante ao algoritmo original cada passo R/W do arquivo, porm com menor custo de

    I/O.

  • UFU/FACOM/BCC GBD2 Pgina:33

    Double Buffering

    considerando que a CPU bem mais rpida que o IO mantem CPU ocupada enquanto aguarda requisio de IO para isso faz prefetch de pginas shadow, uma para cada

    pgina de input, alm de pgina shadow para output (figura)

  • UFU/FACOM/BCC GBD2 Pgina:34

    rvore B+ como alternativa ordenao

    rvore B+ como alternativa ordenao

  • UFU/FACOM/BCC GBD2 Pgina:35

    rvore B+ como alternativa ordenao

    se existe ndice baseado em rvore B+, considere utiliz-la em substituio ordenao externa

    Idia: recuperar registros percorrendo as folhas Consideraes:

    Se a rvore B+ agrupada trata-se de uma boa idia Seno perigoso e pode ser uma idia muito ruim

  • UFU/FACOM/BCC GBD2 Pgina:36

    rvore B+ Agrupada como alternativa ordenao

  • UFU/FACOM/BCC GBD2 Pgina:37

    rvore B+ No Agrupada como alternativa ordenao

    Custo (alternativa 2) Raiz at a folha mais esquerda Percorre sequencial set e para cada entrada

    Busca pgina do data set (um IO por registro => pode ser pssimo)

  • UFU/FACOM/BCC GBD2 Pgina:38

    Comparao rvore B+ No Agrupada x ordenao

  • UFU/FACOM/BCC GBD2 Pgina:39

    Consideraes finais sobre classificao externa

    importante no processamento de consultas External Merge Sort a soluo mais usada para minimizar

    custo de IO Passo 0: subarquivos ordenados de tamanho B (ou 2B

    com replacement sort) Passos seguinte: merge de subarquivos com nmero

    dependente de B e do tamanhos dos blocosMaiores blocos minimizam custo de cada IOMenores blocos minimizam nmero de passos

    rvore B+ agrupada uma boa alternativa, mas a no agrupada pode ser muito ruim.

  • UFU/FACOM/BCC GBD2 Pgina:40

    Exerccios Ordenao Externa

    EXERCCIOS CAP 13 LIVRO-TEXTO

  • UFU/FACOM/BCC GBD2 Pgina:41

    FIM - Ordenao Externa

    FIM - Ordenao Externa*

    * material baseado no livro-texto e pginas pblicas da internet

    Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41