LiveBin: Um Índice de Varredura Binned Localizado e Ciente de Versão

Avanços recentes no Índice de Varredura Binned demonstraram um potencial significativo para acelerar operadores de varredura em bancos de dados analíticos na memória principal. Essa capacidade decorre do paradigma Draft-Refine – uma abordagem em duas fases que primeiro gera resultados aproximados, depois os refina usando metadados auxiliares armazenados no índice. Apesar de alcançar um desempenho de varredura de ponta, os designs atuais ainda sofrem de duas grandes ineficiências: (1) Sobrecarga da fase de refinamento: Embora técnicas modernas melhorem a precisão do rascunho para reduzir iterações de refinamento, cada operação de refinamento incurre em custos substanciais de acesso aleatório à memória, e (2) Ineficiência de dados dinâmicos: Ao considerar MVCC, os operadores de varredura precisam determinar a versão visível dos registros para a transação atual. A sobrecarga da verificação de visibilidade é substancialmente maior do que o custo da avaliação de preditivos. Consequentemente, aproveitar um Índice de Varredura Binned para varreduras gera apenas melhorias marginais no tempo total de execução. Propomos o LiveBin, um Índice de Varredura Binned localizado e ciente de versão que aborda esses desafios por meio de duas técnicas-chave: (1) A localização particiona um índice completo em sub-índices logicamente independentes. Enquanto trabalhos anteriores se esforçam para reduzir a frequência de refinamento através de geração de rascunho mais complexa, o LiveBin emprega Localização para diminuir a sobrecarga de acesso aleatório à memória por refinamento. Isso efetivamente reduz a sobrecarga da fase de refinamento enquanto mantém uma geração de rascunho eficiente. (2) A indexação ciente de versão incorpora uma estrutura hierárquica de versionamento, que estende o paradigma Draft-Refine à verificação de visibilidade. Essa integração, consequentemente, minimiza a validação de visibilidade e a sobrecarga da travessia da cadeia de versão. Resultados experimentais demonstram que o LiveBin alcança desempenho de varredura de 2,2–2,6× mais rápido do que métodos de ponta sob orçamentos de memória idênticos. Além disso, integramos o LiveBin ao DuckDB, e o sistema melhorado alcançou aumentos de desempenho de 2,4–5,0× em comparação com o DuckDB original nas consultas TPC-H Q6 e SSB Q1.