MetisIDX: Indexação de dados preditiva

Abstract

Exploratory data analysis characterized by OLAP query workloads over large databases are now commonplace on both academia and industry. In these scenarios, data production velocity and unknown and drifting access patterns make the choice of access methods a challenging task. In this context, adaptive indexing techniques propose the use of partial indexes that are incrementally built in response to the actual query sequence and as a byproduct of query processing to optimize the access only to the key ranges of interest. This work presents a further development to this principle by leveraging the recent query history to predict the next key ranges and index them in advance, so the queries arriving in the near future find data in its final representation and placed higher in the storage hierarchy, since data must be loaded into main memory in order to be indexed. Adaptive Merging is used as base architecture for the data structures and merge operations are executed in parallel with query execution instead of being the same operation. An extreme learning machine is used to perform key range forecasting and undergo continuous training by the indexing thread. The experiments show approximately one third gain in query response times after 1000 queries. The result is lower overall response times and the fact that the select operator does not incur the costs of indexing.