O custo de uma operação de junção de mérito é normalmente dividido no custo de classificação e o custo da fusão. O fator dominante é geralmente a classificação. Vamos quebrá -lo:

1. Custo de classificação:

* algoritmo : Normalmente, os bancos de dados usam uma classificação de mesclagem externa. Isso ocorre porque as relações unidas geralmente são muito grandes para se encaixar na memória.
* Custo de E/S (fator dominante):
* A classificação de mesclagem externa envolve vários passes através dos dados.
* Número de passes: O número de passes depende do tamanho das relações e da quantidade de memória disponível (o "buffer"). Digamos que temos:
* `B` =número de blocos (páginas) na relação.
* `M` =número de blocos de memória disponíveis (tamanho do buffer).
* O número de passes é aproximadamente `log_m (b)` ou um pouco mais do que isso, se você quiser ser extremamente preciso.
* E/O Custo por Pass: Cada passe lê e escreve toda a relação, por isso custa operações de E/S 2B (B para leitura e B para escrever).
* Total E/S Custo para classificação: `2b * número de passes =2b * log_m (b)`. Com mais detalhes, o custo de classificação para cada relação `r` e` s` é:
* Classificar (r) =2 * `b (r)` * log * Classificação (s) =2 * `b (s)` * log m (`B (s)`) (onde `b (s)` é o número de blocos para as relações s)

* CPU Custo: Embora a classificação seja principalmente ligada à E/S, há um custo de CPU associado à comparação de tuplas, fusão de execuções classificadas, etc. Esse custo geralmente é menor que o custo de E/S e é frequentemente ignorado em modelos de custo simplificados.

2. Custo de fusão:

* I/S Custo: Depois que as relações são classificadas, a fase de fusão requer a leitura de cada bloco de ambas as relações classificadas uma vez.
* `B (r) + b (s)` (onde `b (r)` e `b (s)` são o número de blocos para as relações r e s, respectivamente)
* CPU Custo: O custo da CPU da comparação de tuplas durante a fase de mesclagem é relativamente pequeno em comparação com os custos de classificação e E/S.

Custo total:

O custo total da junção de mérito é aproximadamente a soma dos custos de classificação e o custo de fusão:

custo ≈ 2 * b (r) * log m (B (R)) + 2 * B (S) * LOG M (B (s)) + b (r) + b (s)

Custo simplificado (aproximação comum):

Se o custo de classificação dominar (que geralmente é o caso), uma aproximação simplificada é:

custo ≈ 2 * b (r) * log m (B (R)) + 2 * B (S) * LOG M (B (s))

Considerações importantes:

* Memória (M): A quantidade de memória disponível afeta significativamente o número de passes necessários para a classificação. Mais memória significa menos passes e menor custo.
* dados pré-classificados: Se qualquer uma das relações já estiver * classificada na chave de junção, você poderá pular a etapa de classificação para essa relação. Isso reduz dramaticamente o custo. O custo se torna o custo de classificar apenas a relação não classificada mais o custo de fusão.
* duplicados: Se as teclas de junção contiverem duplicatas, a fase de mesclagem poderá ser mais complexa, exigindo potencialmente E/S adicionais. A fórmula assume que o manuseio duplicado é incorporado em cada leitura de um bloco.
* Tamanho do bloco: O tamanho do bloco (tamanho da página) afeta o número de blocos em uma relação.
* Modelo de custo: A fórmula exata usada para estimativa de custos varia entre os sistemas de banco de dados. Alguns podem incluir o custo da CPU mais explicitamente, os tempos de busca de disco etc. Este é um modelo simplificado para entender os custos relativos.
* Hash Join vs. Sort-Merge Junção: Em muitos casos, a junção de hash é mais eficiente do que a junção de classificação, especialmente quando uma das relações se encaixa inteiramente na memória. No entanto, a junção do tipo Merge pode ser mais eficiente quando os dados já são classificados ou quando os dados não particionam uniformemente.
* Abordagens híbridas : Alguns bancos de dados usam abordagens híbridas que combinam aspectos de junção de hash e junção de mérito.
* desempenho real: Estes são custos teóricos. O desempenho real pode ser afetado por fatores como desempenho de E/S de disco, velocidade da CPU, simultaneidade e ajuste do banco de dados.

Exemplo:

Digamos:

* `B (r) =1000` blocos
* `B (s) =500` blocos
* `M =100 'blocos de memória

Então:

* LOG 100 (1000) ≈ 1,5
* LOG 100 (500) ≈ 1,35

Custo estimado ≈ 2 * 1000 * 1,5 + 2 * 500 * 1,35 + 1000 + 500
≈ 3000 + 1350 + 1500
≈ 5850 Operações de E/S.

Isso é apenas uma estimativa, e o custo real em um sistema de banco de dados real pode ser diferente. A comparação relativa é que o custo de classificação é maior que o custo de fusão.

Em resumo, o custo da junção de tipo é dominado pelo custo de E/S de classificar as relações. O número de passes necessários para a classificação depende do tamanho das relações e da quantidade de memória disponível. Reduzir o tamanho das relações (por exemplo, através da filtragem ou projeção) ou aumentar a memória disponível pode melhorar significativamente o desempenho.