The Parallelization Research Of Query Technology On GPU

As a very important technology in database management field, database technology iswidely used in a lot of industries. In here, query technology is the core component. Currently,the query technology field exist two main research directions. One is to find the fast indexupdate algorithm.The other is to design an efficient query algorithm which fits the query task.For this reason, how to leverage the emerging parallel hardware such as GPUs to improve theupdate efficiency of index structure and the query performance of large-scale data set hasdrawn more and more attentions. In the update process of index structure, insertion anddeletion are two basic operations and both are opposite. At the same time, with the widelyapplication of the Internet and recommendation service, XML query and top-k query havegradually become two research hotspots. So, On the basis of summary and analysis of relatedwork, the main content of this paper as follows:Summarizes the existing build and insertion method of index structure and the querymethod of large-scale data set. According to the research work of this paper, the GPUgeneral computing technology and its mainstream development tool--CUDA are describedin detail. On this basis, the parallel primitives which used in this paper have been furtherintroduction and analysis;For the concurrent insertion of current linear hash table need to lock, a lock-free batchrecords insertion algorithm--GSInsert4LHT and its data structure are proposed in thispaper which combined with the significant advantage in GPU sorting. By using thestrategy in which one thread is responsible for one record insertion, this algorithm cangreatly enhance the insertion performance of linear hash table. Under the condition ofdifferent parameter settings, the performance of this algorithm is improved by10.26~13.54times compared with four threads batch algorithm.On this basis,how to usethis algorithm to improve the judgement efficiency of resource operation authority of“Wetoband” system is proposed in detail.For improving the build and insertion performance of B+tree, a space allocation strategyis introduced firstly. On this basis, a batch build and insertion algorithm--CUBPT isfurther proposed. The experimental results show that the build performance of CUBPT is improved by21.76~25.1times compared with4threads algorithm. Furthermore, In theprocess of batch keys insertion, the performance of CUBPT is improved by9.49~19.2times compared with four threads PALM; this is because the workload of CUBPT is verybalanced.Because of the performance advantages, how to use this algorithm to improvethe query efficiency of resources in “Wetoband” system is described in detail.In here, the parallel XPathquery method on GPU architecture has been researched. Firstly,the deficiencies of two parallel XPath query methods M2and GPU-Twig in storage andthread use ratio is analyzed. On this basis, the Zhang coding structure of the nodes instream labels storage mechanism have been expanded and an large-scale XPath querymethod GXQ based on relation array is further proposed. In the stage of building relationarray, GXQ firstly calculate the first and second node indexes which associated with eachrelation node. And on this basis, quickly build the relation array. In the stage of parallelquery, GXQ mark the results of each execution step, so the cost of storage allocation anddeleting duplicate nodes is greatly reduced. The experimental results show that withoutconsidering the building time of relation matrix, the performance speedup of GXQ is alsoup to16.1times compared with four threads M2method.According to the deficiencies ofcurrent parallel top-k query methods in storage utilizationand generality, a fast top-k query algorithm on GPU architecture CNRA is proposed whichbased on the combination of NRA and LARA algorithm. Different with the traditionalalgorithms which process a data level of the ordered lists in one time, CNRA processSTRIDE data levels in one time both in growth and shrinkage stage, So the upper boundand lower bound updating time of aggregation scores and the comparing time of top-kcandidate objects are greatly reduced. The experimental results show that the performanceof CNRA is greatly improved. But when the value of STRIDE is larger, the performanceof this algorithm has declined. This is related to the updating score lower bound strategyused in this algorithm.