On Optimization Of Join Query Algorithms For Massive Data

The join query is one of the most significant operations in on-line analytical processing(OLAP), and it is also an important way for decision-makers to get information from big data. And multi-join is the main bottleneck in join queries. With the advent of big data era, traditional join algorithms cannot meet the requirements of multi-join queries tothe enterprise management, and also restricted decision-making of the enterprise management.Graphic processing unit(GPU)computing is being developed in recent years.It has been widely applied in computational chemistry, sparse matrix and the physical model. With thehigh parallel computingability of GPU and the join algorithms of column-oriented database, this thesis presents a series of join query algorithms. And we speed up themulti-join of OLAP. The main researches are as follows:(1) According to the star schema ofanalysis-oriented data warehouseand the characteristics of multi-join, we design a partition model suitable for the large-scale data.And with the coalesced accesses of GPU,we proposedthe interval difference compression algorithm.This algorithm gets 2 times speedup to traditionalalgorithm;(2) According to the interval difference compression data and the traditional difference compression data, we proposed two selecting join algorithms based on interval compression and traditional compression. We speed up the selecting join algorithms with GPU.(3) According to the OLAP standard test(SSB),the selecting join algorithms based on GPU gets about 10 times speedup with algorithm based on CPU and also get 2-4 times speedup with invisible join based on GPU.