Automated database indexing using model-free reinforcement learning

• Ano de defesa: 2020
• Autor(a) principal: Licks, Gabriel Paludo
• Orientador(a): Meneguzzi, Felipe Rech
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Pontifícia Universidade Católica do Rio Grande do Sul
• Programa de Pós-Graduação: Programa de Pós-Graduação em Ciência da Computação
• Departamento: Escola Politécnica
• País: Brasil
• Palavras-chave em Português: Inteligência artificial; Aprendizado por reforço; Bancos de dados; Indexação automática
• Palavras-chave em Inglês: Artificial intelligence; Reinforcement learning; Databases; Automated indexing
• Área do conhecimento CNPq: CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO
• Link de acesso: http://tede2.pucrs.br/tede2/handle/tede/9260

Configuring databases for efficient querying is a complex task, often carried out by a database administrator. To reduce the response time of queries, especially complex ones, index structures are created to facilitate the search for data. However, solving the problem of building indexes that truly optimize database access requires a substantial amount of database and domain knowledge, the lack of which often results in wasted space and memory for irrelevant indexes, possibly jeopardizing database performance for querying and certainly degrading performance for updating. In this research, we develop the an architecture to solve the problem of automatically indexing a database by using reinforcement learning to optimize queries by indexing data throughout the lifetime of a database. We train our reinforcement learning agent and evaluate its performance in experiments using TPC-H, a standard, and scalable database benchmark. In our experimental evaluation, our architecture shows superior performance compared to related work on reinforcement learning and genetic algorithms, maintaining near-optimal index configurations and efficiently scaling to large databases.