Query Processing And Optimization Of Join Operation On Key-Value Database

With the rapid development of Internet technology, various types of applications emerge one after another. In the background of cloud-computing, data storage technology become to have some new features:supporting extremely large amounts of data, lower IO delay, high availability, lower operation and maintenance costs, etc. In the past few decades, traditional relational database has already occupied unshakable status in industry, but its drawback such as low expansibility, high cost, literacy slow, supporting capacity limit become more and more serious.In order to solve the problems above, NoSQL database arises at the historic moment. This kind of database is designed to support huge amounts of data storage,has high availability, can run on the cluster which is built with PC, and has lower cost and easy maintenance. Because it mainly uses the key-value data model, we also call this kind of database "key-value database", KVDB for short.In key-value database, there is no strong relationship among tuples such as the one in traditional database. This makes it difficult to support SQL query in key-value database, and the most complicated part of SQL is join operation. To solve this problem, this thesis present a new type of index on column value of ring architecture. Based on the index, we present a algorithm which supports join operation on large amount of data, and make the corresponding optimization. As another supplement, we also design the real-time join algorithm. The content of this thesis is summarizd as follows:1. Firstly, introduce the common data model, architecture, reading and writing strategy and other related knowledge in NoSQL2. We design column value index of ring architecture and give the corresponding algorithm. Base on the index structure, we present and optimize the pre-join algorithm.3. We design real-time-join algorithm. Meanwhile, for this real-time-join algorithm,we design double index to improve the performance of the algorithm.4. Finally, we make plenty of experiments to prove the exactness of the algorithms we present.