Design And Implementation Of High-performance Bitmap Indexing Algorithm For Multi-core CPU

Bitmap indexing is a common database indexing technology.Compared with traditional indexes such as Hash and B~+-tree,bitmap indexing has higher query performance.Therefore,it has been widely used in querying large data sets like scientific data sets.However,the current bitmap indexing has two major problems.(1)Application Parallelization.The gradual failure of Moore’s law leads to the development of programs in the direction of parallelization.That is,the same data structure is simultaneously accessed by multiple CPU cores in parallel,which requires indexing to support parallel read and write operations.(2)Real-time Data Update.When an operation updates data,its submission should be correctly saved and perceived by other operations.NBUB ensures the consistency and correctness of the database before and after data update,which requires that the changes to the index must be timely and correctly recorded.Two major problems seriously hinder the wide application of bitmap indexing technology at present.Therefore,this thesis first parallelizes the existing bitmap indexing algorithms and runs them on multi-core systems.When analyzing the problems of these parallelized algorithms,we propose a Non-blocking Updatable Bitmap indexing(NBUB).Compared with the state-of-the-art algorithms,NBUB is non-blocking.That is,when a read/write operation is in progress,the newly arrived read/write operations are not blocked.In sharp contrast,with the previously parallelized algorithm,the newly arrived read/write operation have to wait for the previous operation to complete.In this thesis,the following techniques are used to achieve the parallel control and obtain good performance.(1)Multi-version Concurrency Control.MVCC is a technology that provides multiple versions of data structure used in the system,while global timestamps is used to mark the order of those versions.The multi-version technology separates read and write operations.When different read/write operations arrive,it only needs to find the corresponding version of the operation without being affected by other operations in progress.(2)Transaction.NBUB algorithm guarantees the ACID properties of database transaction.In the process of multi-version submission,two-phase locking is used by the algorithm to solve the conflict between operations.NBUB also provides conflict detection mechanism to solve the write skew problem,which provides a snapshot isolation level.In the application part,this thesis integrates NBUB into DBx1000 database.At the same time,this thesis also applies NBUB to scientific data analysis.The experiment shows that the throughput of NBUB algorithm is 1.7 times better than Up Bit,4.2 times better than In-place and 5 times better than UCB.