Utilization Of Bloom Filter For Database Query Optimization

Abstract

In modern days, NoSQL database system is slowly replacing the traditional relationalbased database system. One of the NoSQL database type that is widely used is a document store databases type as it mimics the design of traditional relational database system, while provides more flexibility on the scheme. Some traditional database query optimization methods can be utilized in a documentstore databases, but the flexibility of the scheme, and lack of a strict consistent structuremakes some query optimizations to be impossible to perform. Bloom filter is a probabilistic data structure that is capable to determine the member- ship of an element in a set. Bloom filter always produce true negative, but may producea false positive. This qualitative study is
conducted in order to determine the viability of bloom filter for an optimization method to reduce the time taken to process a query in a NoSQLdocument store databases. The results from this study determine that the implementation of bloom filter with the scheme described in this experiment is only applicable to create a slightly better performance of a query in only some specific cases. Meanwhile in the majority of other cases the bloom filter either does not create a significant performance different, or hinders theperformance of the query.
Keywords: NoSQL, Bloom Filter, Query Optimization