CN103309958B - The star-like Connection inquiring optimization method of OLAP under GPU and CPU mixed architecture - Google Patents

Abstract

The invention discloses the star-like Connection inquiring optimization method of the OLAP under a kind of GPU and CPU mixed architecture, comprise the steps: that first passing through bit join index filters the optimization star-like attended operation of OLAP, the connection bitmap that buffer memory high frequency accesses in GPU buffer memory；Secondly, off-balancesheet key set of properties is loaded in GPU buffer memory and carries out star-like connection filters the fact that by satisfied connection bitmap filter condition；Finally, by the GPU filtered bitmap generated, the full table scan of big for internal memory true table is converted to opsition dependent random access, thus improving the query processing performance of the star-like connection of OLAP.The present invention improves the storage efficiency of GPU buffer memory and the parallel processing efficiency of GPU, improves the OLAP query process performance of mixed processing applicator platform on the whole.

Description

OLAP star join query optimization method under GPU and CPU mixed architecture

technical field

The invention relates to a data warehouse query processing method, in particular to a method for optimizing complex multi-dimensional query processing by using a general-purpose GPU as a connection bitmap storage and processing engine under the mixed architecture of GPU and CPU, and belongs to the technical field of database management.

Background technique

At present, microprocessor technology is mainly divided into two development trends: one is multi-core general-purpose processor technology, and the other type is many-core coprocessor technology. The multi-core general-purpose processor is represented by Intel's multi-core processor technology, and its main features are a small number of processing cores and multi-level cache (cache). Many-core coprocessors are mainly represented by NVIDIA's general-purpose GPU (General Purpose Graphics Processing Unit, abbreviated as GPGPU) and Intel's Xeon Phi ^TM coprocessor. Judging from current and future development trends, many-core coprocessors have become the basic platform for high-performance computing.

Compared with multi-core CPUs, general-purpose GPUs have strong parallel computing capabilities but weaker data management capabilities. They are not suitable for managing complex data types and complex memory data structures, and are not suitable for processing complex control statements. They are more suitable for standard vectors, matrices, and arrays. Wait for the calculation. In addition, the cache capacity of the coprocessor is smaller than that of the memory. PCI-E cards are usually used as the processing device for server expansion. Data needs to be obtained from the memory under the control of the CPU, and the data transmission speed between the memory and the coprocessor It is much lower than the transmission speed between the memory and the processor, so the data processing time on the coprocessor needs to include two parts: the data transmission time from the memory to the coprocessor cache and the data processing time on the coprocessor.

In data warehouse applications, data is usually stored as a complex star schema or snowflake schema, generally consisting of a fact table and multiple dimension tables. Dimension tables store complex data types and need to process complex predicate expressions; fact tables are composed of dimension table foreign key attributes and measurement attributes, and measurement attributes need to be grouped according to the grouping attributes in the dimension table on the basis of connection with the dimension table Grouped aggregation calculations. The number of dimension tables is large and the amount of data is small (usually less than 5% of the total data volume), but the data types and data processing are complex; the number of fact tables is huge, and its complex multi-table join operation is the performance bottleneck of analysis and processing. At the same time, the parallel processing performance of analytical queries is affected by the complexity of grouping operations and the type of aggregation calculations. For example, aggregation calculations such as sum, count, and average are suitable for parallel processing, while aggregations such as median and percentile are difficult to process in parallel. Therefore, complex grouping and aggregation Computational tasks are not well suited for general-purpose GPU processing.

On the other hand, He Bingsheng et al. proposed the Co-Processing computing model in the paper "Relational query coprocessing on graphics processors" (published in "ACM Transactions on Database Systems" Volume 34, No. 4, December 2009), which distributed the query task load between GPUworker and CPUworker. , evaluate how relational operators are allocated on two processor nodes through the cost model of CPU and GPU. The paper proposes that simple calculations such as selection operations are suitable for CPU processing, and complex operations such as connection operations are suitable for GPU processing. GPUs are not suitable for branch prediction operations, so typical pipeline processing techniques in databases are difficult to implement on GPUs. The connection operation will generate a large amount of materialized data. In the OLAP (online analytical processing) application of the data warehouse, the star connection will generate complex multi-table connection operations. The parallel connection operation on the general-purpose GPU needs to be performed between each connection operator. For data partitioning operations, the cost of data preprocessing is relatively high. In the paper "Accelerating foreign-key joins using asymmetric memory channels" (published in Proceedings of International Conference on Very Large Data Bases 2011 (VLDB), 585-597), H.Pirk et al. regard GPU and CPU as a distributed database. In view of the high internal data access performance of GPU nodes, but The performance of the data channel between the GPU and the CPU is low. It is proposed to store the smaller dimension tables in the data warehouse in the general-purpose GPU. The foreign key connection attribute of the fact table completes the connection operation in the GPU through the foreign key index and returns the connection index. As intermediate data for subsequent operations in the CPU. However, when multiple GPUs are configured in the computer system, the full copy mechanism of the dimension table distribution will generate a large data redundancy cost and reduce the utilization rate of the limited GPU cache. In addition, dimension tables have diverse data structures, high predicate operation complexity, and small data volumes, which are more suitable for CPU processing.

But as far as the inventor knows, there is no research on using GPU cache as an index storage engine to accelerate the performance of OLAP query processing of memory big data.

Contents of the invention

The technical problem to be solved by the present invention is to provide an OLAP star join query optimization method under the mixed architecture of GPU and CPU. This method applies bitmap join index and star bitmap filtering technology to GPU and CPU hybrid architecture, effectively optimizing complex multi-dimensional query processing.

For realizing above-mentioned purpose of the invention, the present invention adopts following technical scheme:

A kind of OLAP star connection query optimization method under the mixed architecture of GPU and CPU, comprises the following steps:

Firstly, the OLAP star join operation is optimized by bitmap join index filtering, and the frequently accessed join bitmap is cached in the GPU cache; secondly, the foreign key attribute group of the fact table that satisfies the join bitmap filter condition is loaded into the GPU cache for star join operation. Finally, through the filter bitmap generated by the GPU, the full table scan of the large memory fact table is converted into random access by location, thereby improving the query processing performance of the OLAP star connection.

Preferably, the bitmap corresponding to the frequently accessed keyword in the bitmap connection index is used as a bitmap index member of the GPU, and its member bitmap is stored in the GPU cache.

Preferably, the foreign key attributes of the fact table are stored in the memory, and the foreign key attributes of the fact table satisfying the index conditions are extracted through the filter bitmap generated by the GPU bitmap index into the GPU cache.

Wherein preferably, when performing query processing, first look up whether there is a matching connection bitmap in the GPU according to the predicate in the query, if there is, perform the corresponding bitmap operation in the GPU, and load the dimension table predicate bitmap to the GPU in cache.

Wherein preferably, the foreign key of the fact table realizes star connection bitmap filtering through foreign key mapping in the GPU, and updates the filtering bitmap to determine the record position of the fact table that finally satisfies the star connection; the CPU passes through the filtering bit generated by the GPU The graph filters the fact table, converting a full table scan of a large fact table into random access by position.

Wherein preferably, the filter bitmap is a bitmap generated according to bit operations on the GPU cache connection bitmap corresponding to the query key, and is used to filter the fact table foreign key groups that need to be transferred from the memory to the GPU cache.

Preferably, in the OLAP star connection operation, the fact table foreign key is mapped to the corresponding position of the corresponding dimension table predicate bitmap through the mapping relationship between the fact table foreign key and the dimension table record position, thereby Transform the star connection into the filtering operation of the foreign key attribute of the fact table on the corresponding dimension table predicate bitmap.

Preferably, when the fact table foreign key attribute group performs star connection filtering, the filtering bitmap is updated according to the filtering result, and the fact table whose bit operation result of the star connection filtering is "0" is recorded in the corresponding filtering bitmap A "1" in the position is set to a "0".

Wherein preferably, the filter bitmap indicates the relative position of records in the fact table that satisfy the predicate operation for the current query, and the corresponding fact table records are connected with the dimension table to complete the subsequent grouping and aggregation operation.

Preferably, a% of the storage space in the GPU cache is used as the storage space quota of the bitmap connection index for caching the connection bitmap; 1-a% of the storage space is used as the fact table in the OLAP star connection operation Foreign key attribute cache and dimension table predicate bitmap; wherein, the value range of a is 20-60.

Compared with the prior art, the present invention optimizes the OLAP star connection query technology under the mixed architecture of GPU and CPU. Optimize storage and query processing between the general-purpose GPU cache and memory, use the general-purpose GPU as a connection bitmap storage and processing engine, and improve the data transmission efficiency between the foreign key attribute of the fact table and the general-purpose GPU cache through the bitmap index. Use dimension table predicates to filter the fact table foreign key star connection on the bitmap, update the filter bitmap, and realize random access by location in the memory through the filter bitmap, which significantly improves the access efficiency and query processing performance of large fact tables.

Description of drawings

Figure 1 is a schematic diagram of the data warehouse storage model under the hybrid architecture of GPU and CPU;

Fig. 2 is the OLAP query keyword bitmap operation synoptic diagram connecting on the bitmap in general-purpose GPU;

Fig. 3 is a schematic diagram of the memory access processing of the fact table foreign key attribute record based on the filtering bitmap;

Fig. 4 is a schematic diagram of the filtering operation of the fact table foreign key star dimension table bitmap based on the filtering bitmap in a general-purpose GPU;

FIG. 5 is a schematic diagram of CPU filtering bitmaps according to general-purpose GPUs, extracting fact table records to complete OLAP query processing.

detailed description

The present invention will be further described in detail below in conjunction with the accompanying drawings and specific embodiments.

According to relevant research, GPU and CPU are equivalent to a distributed system connected by PCI-E bus, in which GPU has a limited high-speed cache, which is suitable for high-speed parallel processing on simple data types, but it is necessary to further reduce the communication between CPU and GPU. Data transfer cost. The GPU cache capacity is small, but the data access performance is high, and it is suitable for storing indexes that can accelerate multi-table join operations. As mentioned earlier, many-core coprocessors have become the basic platform for high-performance computing. At present, many-core coprocessors are mainly represented by NVIDIA's general-purpose GPU and Intel's Xeon ^PhiTM coprocessor, among which With 2688 processing cores, 250GB/s memory bandwidth and 6GB memory; The Xeon ^PhiTM coprocessor 5110P has 60 cores (1.053GHz), 240 physical threads, 8GB memory and 320GB/sec bandwidth. In the following, a general-purpose GPU is taken as an example, but the technical content of the present invention is also applicable to Xeon ^PhiTM coprocessor.

In view of the technical characteristics of GPU and CPU, the present invention proposes an OLAP star connection query optimization method under the mixed architecture of GPU and CPU. This method uses the general-purpose GPU as an OLAP star-join (star-join) accelerator, uses the bitmap join index technology to accelerate the star-join operation, and utilizes the storage access performance of the high-performance cache of the general-purpose GPU and the powerful parallel processing performance of the general-purpose GPU to improve Query Processing Performance of OLAP Star Joins.

According to the characteristics of the general-purpose GPU's small cache but high bandwidth performance, the present invention first caches the connection bitmaps with high frequency access, and utilizes the powerful parallel processing capability of the general-purpose GPU to improve the operation performance of the bitmap, and accelerates the index through the bitmap index of the general-purpose GPU performance. With the support of the general-purpose GPU bitmap index, the general-purpose GPU is used as an OLAP star connection accelerator, and only the large fact table foreign key attribute groups that meet the connection bitmap filter conditions are loaded into the general-purpose GPU cache for parallel star connection filtering processing , using the powerful parallel processing capability of general-purpose GPU to accelerate star connection processing performance; finally, pass the smaller fact table filter bitmap generated by general-purpose GPU to the memory database to realize the filtering operation of large fact table and improve the table scan of OLAP Efficiency, improve the query processing performance of OLAP star join.

Among them, the main role of the general-purpose GPU in the present invention is to store and process the connection index, and filter the star connection of the foreign key of the fact table. The generated filter bitmap indicates the records that need to be finally connected in the OLAP query in the fact table, eliminates bandwidth consumption and unnecessary connection operation costs when accessing unnecessary fact table records, and improves the efficiency of memory access.

In addition, in order to implement the present invention, the in-memory database engine needs to support bitmap-based location access, that is, in the column-store in-memory database, random scanning by location can be realized through a standard bitmap access interface, so as to improve the efficiency of table scanning.

In the present invention, the OLAP star join query processing is divided into three execution stages: bitmap join index filtering, fact table foreign key star dimension table bitmap filtering and query processing based on fact table filtering bitmap. Improve index access performance through these three execution stages, reduce the amount of data access to memory by general-purpose GPUs, and convert a large number of record data scanning operations in memory into efficient random access by location, thereby reducing the cost of large fact table scanning in query processing and eliminating The join operation cost of these records optimizes the overall performance of complex multidimensional query processing. The following is a detailed description of this.

First, the present invention provides a data warehouse storage model under the mixed architecture of GPU and CPU. In the prior art, the storage and processing technologies such as data warehouse index, fact table and dimension table storage, and OLAP star connection operation are not systematically optimized under the unified GPU and CPU mixed architecture. Moreover, traditional connection technologies require data structures such as complex HASH tables on general-purpose GPUs, which increases the complexity of general-purpose GPU processing. In the prior art, when star join OLAP query is involved, the star join based on partitioning technology needs to materialize a large number of intermediate join results, which reduces the efficiency of GPU cache usage and the parallel processing efficiency of general-purpose GPUs. At the same time, the lack of index support also makes the fact table need to move a large amount of data between the memory and the general GPU cache when the general GPU connection is accelerated, which increases the data preprocessing cost of the general GPU. Aiming at the above-mentioned technical problems, the data warehouse storage model provided by the present invention optimizes the bitmap index mechanism between the GPU and the CPU on the one hand, and optimizes the storage and query processing mechanism of the fact table and the dimension table on the other hand. .

In the data warehouse storage model shown in Figure 1, the data objects in the data warehouse mainly include fact tables, dimension tables and bitmap join indexes. The dimension table is stored in memory, and the fact table is stored in memory or disk. Memory includes DRAM and flashmemory. It accesses the cache of the general-purpose GPU (that is, the video memory in Figure 1) through the PCI-E channel, and at the same time provides access to the CPU core through the memory channel.

Fact tables can be stored in memory or on disk. When using disk storage, the fact table can store a large amount of data, but the high-performance computing capability of multi-core CPU or general-purpose GPU is offset by the huge delay of disk I/O, which makes the processor idle and wastes powerful parallel computing resources. Therefore, in the present invention, the memory storage of large fact tables is preferably used as the application background. Fact tables are stored in columns, including foreign key columns and measure columns. Among them, the filter bitmap generated by the fact table foreign key attribute according to the general GPU connection bitmap is extracted to the general GPU cache for star-shaped bitmap filtering operation, so the fact table foreign key attribute can be stored in an independent column, It is also possible to store all foreign key attributes as supercolumns in the form of columngroups. The corresponding filtering bitmap is a bitmap generated according to bit operations on the general GPU cache connection bitmap corresponding to the query keyword, and is used to filter the fact table foreign key groups that need to be transferred from the memory to the general GPU cache, which can improve general GPU Cache storage efficiency and data transfer efficiency. The metric attributes are stored in columns in memory, and the column storage or hybrid storage model is determined according to the characteristics of the schema and the storage engine used.

The dimension table resides in memory and is used for dimension table predicate processing in user queries, and the generated dimension table predicate filter bitmap is transferred to the general-purpose GPU cache as a fact table filter bitmap. In this process, the memory database provides storage and complex predicate processing functions for dimension table storage. When the user issues a query request, firstly, the predicate operation on each dimension table in the query is converted into the predicate processing on the corresponding dimension table through query rewriting, and the corresponding dimension table predicate filter bitmap is generated. For example, the query

SELECT c_nation, sum(lo_revenue) asprofit

FROMcustomer,supplier,part,lineorder

WHERElo_custkey=c_custkey

ANDlo_suppkey=s_suppkey

ANDlo_partkey=p_partkey

ANDc_region='AMERICA'

ANDs_region='AMERICA'

AND(p_category='MFGR#41' OR p_category='MFGR#42')

GROUP BYc_nation ORDER BYc_nation;

It is rewritten as the following three queries. Each query will centrally process the predicate expression on the corresponding dimension table, and generate a bitmap vector according to the result of the predicate expression to identify the satisfaction of each dimension table record for the relevant predicate in the query:

SELECT CASE WHENS_region='AMERICA'1ELSE0

FROM Supplier;

SELECTCASEWHEN(p_category='MFGR#41' OR p_category='MFGR#42') 1ELSE0FROMPart;

SELECT CASE WHENC_region='AMERICA'1ELSE0

FROMcustomer;

The bitmap join index adopts memory storage or disk storage, and is used to create a bitmap for the member in the specified attribute column in the dimension table through pre-join operation, and identify the join position of the member in the fact table to which it is joined. In the present invention, the bitmap join index can be created for the low-potential set attribute column of the specified dimension table (or specify a single column or multiple columns) by using the bitmap join index technology in the standard database, or it can be created for Create bitmaps for some frequently accessed members in specified dimension attributes, use bitmaps of different dimension tables and different attribute column members as unified bitmap connection index objects, unify bitmap storage and access interfaces, and realize connection bits based on keywords Figure access. By default, each member of a column creates a join bitmap indicating where the particular column member is joined on the fact table. In one embodiment of the present invention, the part of the link bitmap with high access frequency in the bitmap link index is stored in the cache of the general-purpose GPU, as a high-speed link bitmap storage and bitmap index processing engine, providing a query keyword based on the The function of finding related bitmaps and performing bitmap operations in general-purpose GPUs. According to the keyword in the query, locate the corresponding connection bitmap in the cache of the general-purpose GPU and perform bit operations to generate a filter bitmap, extract the corresponding foreign key attribute group from the fact table in the memory to the cache of the general-purpose GPU, and perform staring. Type connection filtering operation.

The bitmap in the bitmap connection index (that is, the connection bitmap in Figure 1) is as long as the fact table, and its storage space can be calculated by the number of bitmaps × the number of records in the fact table/8 (byte). In the present invention, considering that the cache capacity of the general-purpose GPU is relatively small, all bitmap connection indexes are not cached, but the connection bitmaps corresponding to the predicate keywords of high-frequency access are cached in the general-purpose GPU cache, so as to improve general-purpose Storage efficiency of GPU cache. Specifically, the general-purpose GPU cache is used as a high-frequency access connection bitmap storage engine, and a% of the storage space in the general-purpose GPU cache is used as the storage space quota for the bitmap connection index to store the connection bitmap; 1-a % of storage space as fact table foreign key attribute cache in OLAP star join operations. Among them, the size of a% is specified by the user, and is used to weigh the index access performance and the star join processing performance. In an embodiment of the present invention, a ranges from 20 to 60, preferably 40.

Next, the OLAP star connection operation technology based on GPU and CPU hybrid architecture in the present invention is introduced.

In the present invention, a typical OLAP star join query task is decomposed into three execution phases: (1) according to the predicate keyword in the query, whether the corresponding link bitmap is stored in the cache of the general-purpose GPU, if there is Several matching connection bitmaps complete the corresponding bitmap calculation according to the query predicate expression, and generate a filter bitmap through the parallel processing of the general-purpose GPU; (2) in the filter bitmap, extract according to the position where the value of the bitmap is 1 The corresponding fact table foreign key column group subset, and the dimension table predicate filter bitmap is loaded to the general GPU cache, and the fact table foreign key value is mapped to the offset position corresponding to the dimension table predicate filter bitmap, and filtered according to the dimension table predicate Whether the corresponding position of the bitmap is 1 is used for foreign key connection filtering, and the star connection filtering of fact table records on multiple dimension tables is realized. Set the bitmap position in the filter bitmap with a bitmap value of 1 and the corresponding fact table foreign key star connection filter result to 0, and update the filter bitmap; (3) Pass the final filter bitmap generated by the general-purpose GPU to After returning to the CPU and filtering the fact table through the filtering bitmap, the OLAP query processing is completed.

In the above-mentioned OLAP star join query processing process, the OLAP star join operation is firstly optimized through the bitmap join index, and the bitmap corresponding to the frequently accessed keywords in the traditional bitmap join index is used as a general GPU bitmap index member, and its The member bitmap is stored in the general-purpose GPU cache to ensure that the smaller general-purpose GPU cache can store index data that is most conducive to OLAP star connection optimization. Since the foreign key attributes of the fact table are stored in the memory, we first extract the foreign key attributes of the fact table that meet the index conditions into the general GPU cache through the filtered bitmap generated by the general GPU bitmap index, so as to improve the data transfer between the memory and the general GPU. Transfer efficiency and cache storage efficiency for general-purpose GPUs. In addition, the full table scan on the fact table is the performance bottleneck factor of the OLAP star connection operation. The present invention reduces the data volume of the fact table scan in the OLAP query through two-stage filtering, and converts the large fact table into memory through the filter bitmap generated by the general-purpose GPU. The full table scan is converted into a partial scan operation based on random access by location, which improves the storage access efficiency of the fact table.

When executing the query processing of OLAP star connection, the high-frequency access connection bitmap is stored by the general-purpose GPU. When query processing is executed, firstly, according to the predicate in the query, it is checked whether there is a matching connection bitmap in the general-purpose GPU. If it exists, first perform the corresponding bitmap operation in the general-purpose GPU, and improve the performance of the bitmap operation through the powerful parallel processing capability of the general-purpose GPU; In the GPU cache, it can improve the utilization rate of the general GPU cache, reduce the processing complexity of complex predicates on the dimension table, and simplify the design of the database system; thirdly, the foreign key of the fact table realizes the star connection bitmap through foreign key mapping in the general GPU Filter and update the filter bitmap to determine the position of the fact table record that finally meets the star connection. The CPU filters the fact table through the filter bitmap generated by the general-purpose GPU, thereby converting the full table scan of a large fact table into high-efficiency random access by location, improving memory bandwidth performance, and optimizing the query processing performance of OLAP star joins.

Fig. 2 is a schematic diagram of an OLAP query keyword bitmap operation on a connection bitmap in a general-purpose GPU. The traditional bitmap join index is to create a bitmap identifying the join relationship of the fact table for each column member on the specified dimension table column or columns, so the bitmap join index usually selects columns with low potential sets to reduce the cost of the bitmap index storage overhead. In the first stage of the OLAP star join query, the bitmap join index can adopt the conventional method, but the bitmap join index is stored in a large-capacity disk, and we pass the bitmap corresponding to the predicate keyword frequently accessed in the query through the memory Load it into the general-purpose GPU cache to improve the space utilization of the small-capacity general-purpose GPU cache, and use the high parallel processing capability of the general-purpose GPU to process the bit operations on the big fact table connection bitmap to improve the bitmap index processing performance. For example in Figure 2, the connection bitmap corresponding to the predicates c_region='AMERICA', c_region='AMERICA' and p_category='MFGR#41' in the query is stored in the general GPU cache, but p_category='MFGR#42' corresponds to The connection bitmap of is not cached, so the connection bitmap of the predicate keyword corresponding to OR is incomplete and does not participate in the calculation of the connection bitmap. The general-purpose GPU executes the connection bitmap corresponding to c_region='AMERICA' and c_region='AMERICA' Parallel AND operation, and generate a connection filter bitmap.

Fig. 3 is a schematic diagram of the memory access of the foreign key column of the fact table based on the filtered bitmap. In the second stage of the OLAP star join query, the join bitmap operation in the general-purpose GPU produces a filter bitmap with a lower selection rate, and then the general-purpose GPU selects the foreign key attribute of the fact table according to the position where the filter bitmap value is 1 Extract the corresponding foreign key attribute group to the general-purpose GPU to complete the star connection operation. The OLAP star connection operation in the present invention does not parallelize the traditional connection operation in the general-purpose GPU, but maps the fact table foreign key to the corresponding dimension table through the mapping relationship between the fact table foreign key and the dimension table record position At the position corresponding to the predicate filter bitmap, the star connection is converted into a filter operation on the corresponding dimension table predicate filter bitmap for the foreign key attribute of the fact table. This operation can be converted into a direct access operation by subscripting on the array, which is suitable for parallel processing of general-purpose GPUs and can have better parallel processing performance.

By filtering the bitmap foreign key attribute extraction operation of the fact table, the amount of data transfer between the memory and the general GPU cache of the foreign key attribute of the fact table is greatly reduced, and the bandwidth efficiency and the parallel processing efficiency of the general GPU are improved. When extracting the fact table foreign key column group according to the filter bitmap, you can logically aggregate the position where the filter bitmap value is 1 in the fact table foreign key attribute group into a data block, and attach a bitmap to each fact table foreign key column group The position corresponding to the bitmap value of 1 in , identifies the bitmap position corresponding to the foreign key column group of the fact table. The extracted data blocks aggregated by the foreign key column groups of the fact table are transferred to the general-purpose GPU cache, and are prepared for the filtering process of the dimension table predicate filtering bitmap.

Figure 4 shows the bitmap filtering operation of the fact table foreign key star dimension table based on the filtering bitmap in a general-purpose GPU. According to the concept of multi-dimensional storage model in data warehouse, dimension table records can be mapped into an ordered sequence, such as 1, 2, 3, .... Dimension table predicate filter bitmap is a bitmap with the same length as the dimension table, which respectively records the status of whether the query predicate expression in the current dimension table is satisfied, and the connection filter bitmap extracts from the fact table that satisfy the result of the bitmap index operation. The fact table foreign key is grouped into the general GPU cache, and the fact table foreign key is sequentially mapped to the corresponding position of the dimension table predicate filtering bitmap to complete the star connection filtering. When the fact table foreign key attribute group performs star connection filtering, the filter bitmap is updated according to the filtering result, and the fact table whose bit operation result of star connection filtering is "0" is recorded in "1" in the corresponding filter bitmap position Set to "0". If the foreign key attribute of the fact table does not satisfy the star bitmap filter, as shown in the second record (5, 1, 4, 2) in Figure 4, set the "1" at the corresponding position "4" in the bitmap to " 0", update the filter bitmap.

In the third stage of the OLAP star join query, the CPU extracts the records of the fact table according to the general-purpose GPU filter bitmap, and completes the OLAP query processing. As shown in Figure 5, the general-purpose GPU completes the bitmap operation on the bitmap connection index, generates a filter bitmap, and then extracts the foreign key attribute group of the fact table to the cache of the general-purpose GPU according to the filter bitmap, and filters through the dimension table predicate The bitmap completes the star connection filtering operation, updates the filtering bitmap, and determines the record position in the fact table that satisfies the star connection filtering condition. After the join bitmap filter and the fact table star filter secondary filter operation, the filter bitmap indicates the relative position of the record in the fact table that satisfies the predicate operation for the current query, and the corresponding fact table record needs to be substantially connected with the dimension table operation to complete subsequent grouping aggregation operations. In the join operation, the partly joined dimension tables can be pruned according to the access condition of the join bitmap, so as to reduce the join nodes in the query tree. Finally, the filter position generated in the general-purpose GPU is transferred back to the memory as an additional filter condition for the fact table in the memory database, converting the full table scan of the large fact table into random access by bitmap position, thereby improving the access efficiency of the fact table And the efficiency of OLAP query processing.

The filtered bitmap generated by the general-purpose GPU needs to be transferred from the general-purpose GPU cache to the memory to complete the subsequent OLAP processing. When the filtering bitmap is very sparse (the position of 0 is enough), the bitmap compression storage method can be used to reduce the amount of data transmitted by the bitmap. In one embodiment of the present invention, the bitmap space is compressed by using continuous m-digit values to store the offset position of the bitmap value "1", for example, the bitmap "01000010" is stored as (2, 7). The number of digits of m is determined by the record length N of the fact table, that is, m is the smallest basic numerical type greater than lnN, such as when lnN is less than 16, a shortint (16-bit) type value can be used to store the offset value of the "1" position in the bitmap . The threshold for bitmap compression technology is bitmap filtering selectivity η<1/m, when the compression condition is met, the filtered bitmap is stored as ηN consecutive m-digit value sequences.

In one embodiment of the present invention, the filter bitmap generated by the index is used to filter the connection records on the fact table, and the query Q originally input by the user is optimized to query Q' according to the index bitmap. In the query Q', if the predicate keyword exists in the connection bitmap, and the corresponding dimension table attribute does not appear in the grouping attribute, such as s_region='AMERICAN'AND in the SQL example (p_mfgr='MFGR#1'ORp_mfgr='MFGR #2') If the predicate keyword has a connection bitmap, the filter bitmap generated by the index implies the connection relationship between the fact table and the dimension table supplier and part. In the query Q', the connection between lineorder, supplier table and part table can be connected The operation is pruned, and the number of table connections is reduced to two on the basis of reducing the cost of scanning the fact table. The optimized query Q' is as follows:

Original query Q:

SELECT d_year, c_nation, SUM(lo_revenue-lo_supplycost) ASprofit

FROM date, customer, supplier, part, line order

WHERElo_custkey=c_custkey

ANDlo_suppkey=s_suppkey

ANDlo_partkey=p_partkey

ANDlo_orderdate=d_datekey

ANDc_region='AMERICAN'

ANDs_region='AMERICAN'

AND(p_mfgr='MFGR#1' ORp_mfgr='MFGR#2')

GROUP BY d_year, c_nation

ORDER BY d_year, c_nation

Optimized query Q':

SELECT d_year, c_nation, SUM(lo_revenue-lo_supplycost) ASprofit

FROM date, customer, line order

WHERElo_custkey=c_custkey

ANDlo_orderdate=d_datekey

ANDc_region='AMERICAN'

GROUP BY d_year, c_nation

ORDER BY d_year, c_nation

In order to verify the actual effect of the OLAP star connection query optimization method provided by the present invention, the inventor uses a common desktop as an experimental platform, configured as IntelCorei3-2350MCPU2.30GHz, 8GB memory, 64-bit Windows7 operating system, and configures a GeForce610M Graphics card, CUDA computing capability 2.1, 1GB video memory, GPUClock main frequency 1.48Ghz, 48 CUDAcores, 1024 threads per block, the data bandwidth between GPU video memory and memory is about 2GB/s.

The inventor simulated the big data memory storage scene, the dimension table and the fact table are stored in the memory, the GPU memory only stores the selected TOPK keyword bitmap connection index, and uses the powerful parallel processing capability of the GPU to accelerate the calculation of the index bitmap, and only Load the fewer foreign keys of the fact table after index filtering to the GPU for star connection processing, transfer the group aggregation calculation with high parallel write conflicts to the CPU processing, and take advantage of different processors.

In the specific test, the inventor chooses SSB (StarSchemaBenchmark) as the test standard, the data set size is 4GB (SF=4, 24,000,000 rows), and the predicate keyword used in the query is used as the system index keyword, which is established in the preprocessing stage Link the bitmap and store it in the GPU memory, and use the GPU as an independent GPU index processing engine. The inventor chooses the most representative Q4 query group as the test query. The Q4 query is the connection between the fact table and the four dimension tables, and contains a large number of predicate expressions, which can better reflect the results generated by the keyword bitmap join index. Optimization of bit operation cost between multiple bitmaps.

On the CPU/GPU hybrid platform, OLAP star join query processing is divided into the following processes:

◆Index creation BitFilter

◆BitFilter transmission: GPU→CPU

◆Fact table foreign key group transfer: CPU→GPU

◆Star connection and generate grouping vector

◆Packet vector transmission: GPU→CPU

◆Fact table metric attribute aggregate operation

Among them, the processing process of the CPU platform includes three processes: index creation BitFilter, star connection and generation of grouping vectors, and fact table measurement attribute aggregation operation; CPU/GPU hybrid Co-OLAP includes all processing processes. In experiments, the amount of data transfer between CPU and GPU in queries has been minimized through GPU indexing mechanism and star join optimization.

Table 1 Query execution cost analysis

Table 1 shows the cost analysis results of query execution. From the statistics of CPU query processing and CPU/GPU cooperative processing in Table 1, it can be seen that bitmap operations and star connection operations, which are expensive in CPU processing, achieve extremely high performance in GPU. The bitmap calculation completed by the multi-core CPU in tens of thousands of microseconds can be completed within a short time. Even processing large data and ultra-long bitmaps can achieve extremely high processing performance. The star connection operation is optimized for GPU processing characteristics, and the complex connection operation is simplified to a bit-by-bit direct access operation on the array, which is suitable for the parallel processing mode of the GPU. Therefore, the multi-table star connection also has a huge impact. performance gain.

Compared with the prior art, the present invention has the following technical characteristics:

1. Use the general-purpose GPU cache as a storage engine for high-frequency access to the connection bitmap, and use a smaller GPU cache to store a smaller connection bitmap. When the query keyword hits the connection bitmap, the general-purpose GPU can provide high-performance Parallel bitmap access and bit operation processing performance between multiple bitmaps, improving the operation performance of connected bitmaps (in the CPU, the calculation cost of bit operations between large bitmaps is relatively high);

2. High-frequency and low-selection bitmaps are stored in the general-purpose GPU cache. When multiple bitmap indexes are hit in the query, the filter bitmap generated has a low selection rate and can filter out most of the records in the fact table. You only need to set the related foreign key of the fact table according to the position where the filter bitmap takes a value of 1 The column data is extracted to the general-purpose GPU cache for star connection processing, which can greatly reduce the amount of data transmission between the memory and the general-purpose GPU, and improve data access performance;

3. The foreign key records of the fact table in the general-purpose GPU are filtered twice through the dimension table predicate filtering bitmap. By mapping the fact table foreign key value to the corresponding position of the dimension table predicate filtering bitmap generated by the CPU, the foreign The join operation of the key and the dimension table is converted into the filtering operation of the foreign key of the fact table on the dimension table predicate filter bitmap, and the star connection is converted into the filtering operation of the foreign key attribute of the fact table on multiple dimension table bitmaps, on a general-purpose GPU The star join operation can be completed through sequential bitmap filtering between the fact table foreign key of the array structure and the dimension table predicate filtering bitmap, without materializing the result of each fact table foreign key connection;

4. The bitmap index is the first level of filtering, the fact table foreign key star connection filtering is the second level of filtering, and the two levels of filtering operations share a filtering bitmap. The second-level filtering updates the bitmap value based on the first-level filtering. After the general-purpose GPU completes bitmap index and fact table foreign key filtering, the generated filtered bitmap is passed to the memory, and the CPU extracts it from the fact table according to the bitmap. The corresponding records are processed by OLAP query, which reduces the scanning cost of large fact tables and effectively improves the query processing performance of OLAP when dealing with large data.

In summary, the present invention applies bitmap connection index and star bitmap filtering technology to GPU and CPU hybrid architecture, improves the storage efficiency of general-purpose GPU cache and the parallel processing efficiency of general-purpose GPU, and improves the hybrid processor as a whole. OLAP query processing performance of the platform. The present invention is not only suitable for the application of the internal memory database adopting the mixed architecture of GPU and CPU, but also suitable for the analysis and processing application in the general database.

The above is a detailed description of the OLAP star join query optimization method provided by the present invention under the mixed architecture of GPU and CPU. For those skilled in the art, any obvious changes made to it without departing from the essence and spirit of the present invention will constitute an infringement of the patent right of the present invention and will bear corresponding legal responsibilities.

Claims (9)

1. an OLAP star join query optimization method under a GPU and CPU mixed architecture, is characterized in that comprising the steps: Optimize OLAP star connection operations through bitmap connection index filtering, and cache frequently accessed connection bitmaps in the GPU cache; Load the foreign key attribute group of the fact table that satisfies the filter condition of the connection bitmap into the GPU cache for star connection filtering; Through the filter bitmap generated by the GPU, the full table scan of the large memory fact table is converted into random access by location, thereby improving the query processing performance of the OLAP star connection; When performing query processing, firstly, according to the predicate in the query, it is checked whether there is a matching connection bitmap in the GPU, and if it exists, the corresponding bitmap operation is performed in the GPU, and the dimension table predicate bitmap is loaded into the GPU cache. 2. OLAP star connection query optimization method as claimed in claim 1, is characterized in that: The bitmaps corresponding to the frequently accessed keywords in the bitmap connection index are used as the bitmap index members of the GPU, and the member bitmaps are stored in the GPU cache. 3. OLAP star connection query optimization method as claimed in claim 1, is characterized in that: Store the foreign key attributes of the fact table in memory, and extract the foreign key attributes of the fact table that meet the index conditions into the GPU cache through the filter bitmap generated by the GPU bitmap index. 4. OLAP star connection query optimization method as claimed in claim 1, is characterized in that: The foreign key of the fact table implements star connection bitmap filtering through foreign key mapping in the GPU, and updates the filtering bitmap to determine the record position of the fact table that finally meets the star connection; the CPU performs filtering on the fact table through the filtering bitmap generated by the GPU. Filtering, which converts full table scans of large fact tables into random access by position. 5. the OLAP star join query optimization method as claimed in claim 1, 3 or 4, is characterized in that: The filter bitmap is a bitmap generated according to bit operations on the GPU cache connection bitmap corresponding to the query keyword, and is used to filter the foreign key group of the fact table that needs to be transferred from the memory to the GPU cache. 6. OLAP star connection query optimization method as claimed in claim 5, is characterized in that: The filtering bitmap indicates the relative position of the records satisfying the predicate operation for the current query in the fact table, and the corresponding fact table records are connected with the dimension table to complete subsequent grouping and aggregation operations. 7. OLAP star connection query optimization method as claimed in claim 1, is characterized in that: In the OLAP star join operation, the foreign key of the fact table is mapped to the position corresponding to the predicate bitmap of the dimension table through the mapping relationship between the foreign key of the fact table and the record position of the dimension table, and the star join is converted into The filtering operation of the foreign key attributes of the fact table on the corresponding dimension table predicate bitmap in turn. 8. OLAP star connection query optimization method as claimed in claim 7, is characterized in that: When the fact table foreign key attribute group performs star connection filtering, the filter bitmap is updated according to the filtering result, and the fact table whose bit operation result of star connection filtering is "0" is recorded in "1" in the corresponding filter bitmap position Set to "0". 9. The OLAP star join query optimization method as described in any one of claims 1 to 3, characterized in that: A% of the storage space in the GPU cache is used as the storage space quota of the bitmap connection index for caching the connection bitmap; 1-a% of the storage space is used as the foreign key attribute cache of the fact table in the OLAP star connection operation; Wherein, the value range of a is 20-60.