Improving Query Execution Performance in Big Data using Cuckoo Filter

Performance is a critical concern when reading and writing billions of records stored in a Big Data warehouse. To improve performance, Big Data systems utilize the Eventual Consistency model as well as a probabilistic data structure called Bloom Filter. In recent times, cost minimization and privacy concerns have led Big Data systems to regularly delete data besides reading and writing. Bloom Filter has an important limitation of not supporting deletion of elements from within it. This limitation along with constraints of the Eventual Consistency model prevents the system to delete data from disk immediately upon an execution of a DELETE command. Rather data is actually deleted during a compaction process, which is executed very infrequently due to it being resource-intensive. During the time between data deletion and compaction (typically a few days), lookup queries fetch records from disk that includes the deleted rows, then detect and remove the deleted records from the returning result set. This leads to poor query execution performance. In this paper, we propose a scheme to improve performance of lookup queries after data deletion by replacing Bloom Filter with a better probabilistic data structure called Cuckoo Filter that supports deletion of elements from within it. We evaluate our proposed scheme using a popular Big Data database (Cassandra) that uses both the Eventual Consistency model and Bloom Filter, and show that performance of lookup queries executed after data deletion can improve for up to 100%. We also show that our scheme does not degrade performance of other data manipulation queries as a side effect.