Uma Proposta de Algoritmo para a Fragmentação Virtual Adaptativa

A Fragmentação Virtual Adaptativa (AVP) é um algoritmo para processamento paralelo de consultas OLAP em clusters de computadores com memória distribuída. Nesta dissertação, são propostos dois algoritmos de processamento de consulta multicore que contribuem para a evolução da AVP: AVPMSimples e AVPMRandômica. A abordagem é inspirada na própria AVP, com a criação de subpartições virtuais – definidas por predicados de consultas – a serem processadas por cores individuais. Enquanto a AVPMSimples se apresenta como algoritmo ingênuo e adota tamanhos fixos para as subpartições, a AVPMRandômica é adaptativa, buscando de forma randômica por um tamanho de subpartição ótimo. Os algoritmos foram acrescentados à implementação padrão da AVP, o ParGRES, e foram testados em uma base de dados do benchmark TPC-H com aproximadamente 300 GBytes. Observou-se que a AVPMRandômica tende a se comportar como AVPMSimples, o que indica que esta é uma boa solução, mais simples do que a primeira e com mesmo desempenho. A utilização de múltiplos cores proporcionou aceleração no processamento de algumas consultas apenas. A razão pela qual os algoritmos propostos não aceleram nas outras consultas foi constatada como sendo a não aceleração da fase de planejamento das consultas, cujo tempo em geral domina a fase de execução para pequenas subpartições.