Uma implementação em C# da operação Junção Sort-Merge usando Ordenação Externa (External Merge Sort) para processamento de grandes volumes de dados com restrições rigorosas de memória.
- Visão Geral
- Características
- Arquitetura
- Instalação
- Como Usar
- Esquema de Dados
- Detalhes do Algoritmo
- Gerenciamento de Memória
- Métricas de Performance
- Exemplos
- Estrutura do Projeto
- Contribuindo
MicroMerge implementa a operação Junção Sort-Merge da álgebra relacional, especificamente projetada para processar grandes conjuntos de dados que não cabem inteiramente na memória. A implementação usa Ordenação Externa (External Merge Sort) para manipular dados de forma eficiente mantendo restrições rigorosas de memória.
- APENAS 4 PÁGINAS (40 registros) NA MEMÓRIA A QUALQUER MOMENTO
- NUNCA excede este limite, independente do tamanho dos dados de entrada
- Processamento page-by-page para garantir conformidade com a restrição
- Restrição de Memória: Usa APENAS 4 páginas (40 registros) na memória simultaneamente
- Ordenação Externa: Processa datasets maiores que a memória disponível
- I/O Eficiente: Leitura e escrita otimizada baseada em páginas
- Merge Multi-Pass: Automaticamente processa grandes quantidades de runs ordenados
- 🔄 Junção Sort-Merge: Operação de inner join eficiente entre duas tabelas
- 💾 Ordenação Externa: Processa grandes datasets com limitação rigorosa de memória
- 📊 Rastreamento de Performance: Estatísticas detalhadas de I/O e uso de memória
- 🔍 Suporte Multi-Tabelas: Funciona com datasets de vinhos, uvas e países
- 📁 Exportação CSV: Resultados podem ser exportados para formato CSV
- ⚡ Performance Otimizada: Otimização automática do tamanho das tabelas (tabela maior torna-se operando esquerdo)
- Operator: Classe principal que orquestra a operação de junção sort-merge
- Tables: Estruturas de dados representando tabelas de vinhos, uvas e países
- Records: Classes de registro tipadas para cada tipo de tabela
- External Merge Sort: Algoritmo de ordenação eficiente em memória
- Page Management: Sistema de páginas de tamanho fixo (10 registros por página)
Tabelas de Entrada (Esquerda, Direita)
↓
Ordenação Externa (External Merge Sort)
↓
Criação de Runs Ordenados
↓
Merge Multi-Way
↓
Junção Sort-Merge
↓
Tabela Resultado + Métricas
MEMÓRIA TOTAL: APENAS 4 PÁGINAS (40 registros)
├── Fase de Ordenação: 4 páginas para acumulação e ordenação
├── Fase de Merge: 3 páginas de entrada + 1 página de saída
└── Fase de Junção: 2 páginas de entrada + 1 página de marca + 1 página de saída
⚠️ NUNCA excede 4 páginas independente do tamanho dos dados!
- .NET 9.0 SDK
- Sistema Operacional: Windows, macOS, ou Linux
-
Clone o repositório:
git clone <repository-url> cd SubMerge/MicroMerge
-
Restaure as dependências:
dotnet restore
-
Compile o projeto:
dotnet build
Execute a aplicação com configuração padrão:
dotnet run --project MicroMergeA aplicação pode ser configurada modificando o arquivo Program.cs para usar diferentes operações de junção:
// Diferentes combinações de junção (descomente a operação desejada):
// Vinho ⋈ País (por país de produção)
using var op = new Operator(wineTable, countryTable, "pais_producao_id", "pais_id");
// Vinho ⋈ Uva (por tipo de uva)
using var op = new Operator(wineTable, grapeTable, "uva_id", "uva_id");
// Uva ⋈ País (por país de origem) - Padrão
using var op = new Operator(countryTable, grapeTable, "pais_id", "pais_origem_id");A aplicação irá:
- Exibir estatísticas da operação
- Criar um arquivo CSV de resultado no diretório
output/ - Mostrar uso de memória e contagem de operações de I/O
Exemplo de saída:
Operação concluída com sucesso!
Result:
Número de páginas geradas: 8
Número de registros gerados: 73
Número de IO's: 82
Nome da tabela gerada: grapes_countries_joined_sorted_pais_origem_id
| Coluna | Tipo | Descrição |
|---|---|---|
vinho_id |
int | Chave Primária |
rotulo |
string | Rótulo do vinho |
ano_producao |
int | Ano de produção |
uva_id |
int | Chave Estrangeira → Uva |
pais_producao_id |
int | Chave Estrangeira → País |
| Coluna | Tipo | Descrição |
|---|---|---|
uva_id |
int | Chave Primária |
nome |
string | Nome da uva |
tipo |
string | Tipo da uva |
ano_colheita |
int | Ano de colheita |
pais_origem_id |
int | Chave Estrangeira → País |
| Coluna | Tipo | Descrição |
|---|---|---|
pais_id |
int | Chave Primária |
nome |
string | Nome do país |
sigla |
string | Código do país |
País (Country)
├── pais_id (PK)
├── nome
└── sigla
Uva (Grape)
├── uva_id (PK)
├── nome
├── tipo
├── ano_colheita
└── pais_origem_id (FK → País.pais_id)
Vinho (Wine)
├── vinho_id (PK)
├── rotulo
├── ano_producao
├── uva_id (FK → Uva.uva_id)
└── pais_producao_id (FK → País.pais_id)
A implementação usa uma ordenação externa de 2 fases com restrição rigorosa de memória:
- Lê dados em chunks que cabem na memória (APENAS 4 páginas = 40 registros)
- Ordena cada chunk na memória
- Escreve runs ordenados em arquivos temporários
- NUNCA excede 4 páginas na memória
- Faz merge dos runs ordenados usando abordagem tournament tree
- Mantém APENAS 1 página por run de entrada + 1 página de saída na memória
- Processa qualquer quantidade de runs através de merge multi-pass
- GARANTE que nunca mais de 4 páginas estão na memória simultaneamente
- Preparação: Ambas as tabelas são ordenadas externamente pelas colunas de junção
- Processo de Merge: Traversal simultânea das tabelas ordenadas
- Tratamento de Duplicatas: Produto cartesiano adequado para valores de junção duplicados
- Gerenciamento de Memória: Usa sistema de buffer de 4 páginas
┌─────────────────────────────────────────────────┐
│ RESTRIÇÃO ABSOLUTA: MÁXIMO 4 PÁGINAS (40 registros) │
├─────────────────────────────────────────────────┤
│ ✓ Fase de Ordenação: 4 páginas máximo │
│ ✓ Fase de Merge: 3 entrada + 1 saída │
│ ✓ Fase de Junção: 2 entrada + 1 marca + 1 saída│
│ ✓ NUNCA excede independente do tamanho dos dados│
└─────────────────────────────────────────────────┘
O sistema mantém restrições rigorosas de memória:
| Operação | Uso de Buffer | Descrição |
|---|---|---|
| Ordenação | 4 páginas máx | Acumular, ordenar, escrever runs |
| Merging | 3 entrada + 1 saída | Buffer de merge multi-way |
| Junção | 2 entrada + 1 marca + 1 saída | Buffer de junção sort-merge |
- Tamanho da Página: 10 registros por página
- Limite de Memória: Máximo 4 páginas (40 registros) na memória
- Unidade de I/O: Todas as operações de disco trabalham com páginas completas
⚠️ GARANTIAS IMPLEMENTADAS:
1. RunIterator: 1 página por iterador
2. CreateSortedRuns: Máximo 4 páginas para acumulação
3. MergeRuns: Máximo 3 páginas de entrada + 1 saída
4. SortMergeJoin: 2 entrada + 1 marca + 1 saída
5. Multi-pass: Quando necessário, divide automaticamente
RESULTADO: NUNCA excede 4 páginas independente do tamanho dos dados!
A aplicação rastreia e reporta:
- Páginas Criadas: Número de páginas escritas no disco
- Registros Gerados: Total de registros no resultado
- Operações de I/O: Contagem de operações de leitura/escrita no disco
- Uso de Memória: Permanece dentro da restrição de 4 páginas
- Ordenação de Tabelas: Tabela maior automaticamente torna-se operando esquerdo
- Minimização de Runs: Criação eficiente de runs reduz passes de merge
- Gerenciamento de Buffer: Estratégia ótima de substituição de páginas
Encontrar todas as uvas com seus países de origem:
var countryTable = new CountryTable("./Data/pais.csv");
var grapeTable = new GrapeTable("./Data/uva.csv");
using var op = new Operator(countryTable, grapeTable, "pais_id", "pais_origem_id");
var result = op.Execute();
op.WriteToCsv("./output");Resultado: Arquivo CSV com informações de uvas unidos com detalhes dos países.
Encontrar todos os vinhos com suas informações de uvas:
var wineTable = new WineTable("./Data/vinho.csv");
var grapeTable = new GrapeTable("./Data/uva.csv");
using var op = new Operator(wineTable, grapeTable, "uva_id", "uva_id");
var result = op.Execute();var result = op.Execute();
Console.WriteLine($"Operações de I/O: {result.NumberOfIOOperations}");
Console.WriteLine($"Eficiência de Memória: {result.NumberOfCreatedRecords / result.NumberOfIOOperations:F2} registros/I/O");
Console.WriteLine($"Páginas na memória: MÁXIMO 4 páginas (garantido)");MicroMerge/
├── Program.cs # Ponto de entrada da aplicação
├── MicroMerge.csproj # Configuração do projeto
├── Data/ # Arquivos CSV de entrada
│ ├── pais.csv # Dados dos países
│ ├── uva.csv # Dados das uvas
│ └── vinho.csv # Dados dos vinhos
├── Models/ # Modelos de dados
│ ├── Page.cs # Estrutura de página
│ ├── PageId.cs # Identificador de página
│ └── Record/ # Tipos de registro
│ ├── Record.cs # Classe base de registro
│ ├── CountryRecord.cs # Registro de país
│ ├── GrapeRecord.cs # Registro de uva
│ └── WineRecord.cs # Registro de vinho
├── Tables/ # Implementações de tabela
│ ├── Table.cs # Classe base de tabela
│ ├── SortedTable.cs # Tabela ordenada com I/O de disco
│ ├── CountryTable.cs # Carregador da tabela de países
│ ├── GrapeTable.cs # Carregador da tabela de uvas
│ └── WineTable.cs # Carregador da tabela de vinhos
├── Operator/ # Operação de junção
│ └── Operator.cs # Implementação da junção sort-merge
└── output/ # Resultados gerados
└── *.csv # Resultados das junções
-
Execute com diferentes operações de junção:
# Edite Program.cs para descomentar a junção desejada dotnet run --project MicroMerge -
Verifique os arquivos de saída:
ls -la output/ cat output/grapes_countries_joined_sorted_pais_origem_id.csv
-
Teste de performance:
- Monitore a contagem de operações de I/O
- Verifique conformidade com restrição de memória
- Confira correção da junção
- Correção: Compare resultados da junção com resultados esperados
- Conformidade de Memória: Certifique-se de nunca exceder limite de 4 páginas
- Eficiência de I/O: Monitore contagem de operações de disco
Este projeto faz parte de uma tarefa acadêmica para o curso de Sistemas de Banco de Dados (SGBD).
- Conceitos de Sistema de Banco de Dados (Silberschatz, Galvin, Gagne)
- Algoritmos de Ordenação Externa
- Padrões de Implementação de Junção Sort-Merge
Autores: Curso de Sistemas de Banco de Dados - UFC
Data: Junho 2025
Versão: 1.0.0