Fault-Tolerant Query Execution over Distributed Bitmap Indices

Advances in storage software and filesystems have proliferated a vast array of easy-to-use distributed storage services, removing the barrier for a growing number of organizations to geo-distribute large data sets. While leaving data in their distributed environments is convenient for data collection, various types of processing (that might use multiple data sources) are precluded due to the prohibitive costs of data movement. Users are therefore burdened with finding creative ways of performing data analysis, often requiring expert knowledge in multiple domains. This paper reports on the design and implementation of a query engine that enables high-level queries over distributed data sets. Our system generates bitmap indices at multiple geo-distributed data sources in order to approximate large amounts of raw data values. The bitmaps are replicated for fault-tolerance and performance. Upon accepting a high-level (SQL-like) query, our system generates a query plan, resolves dependencies, and schedules for its execution over the distributed system. The system has been tested rigorously, and experimental results show that most overheads (i.e., query planning, node spawning, etc.) are negligible. Our testing also shows that our system is capable of delivering query results in the face of node failures, with no observable impact on query execution for up to 20% of the system failing. The system also provides a framework that is easily extendible for future research on the interplay between distributed systems and bitmap indices.