CN108197275A - A kind of distributed document row storage indexing means - Google Patents

Abstract

The invention discloses a distributed file column storage indexing method, which comprises the following steps: analyzing query statements to obtain query conditions; reading index copy columns according to the index fields in the query conditions, and the index copy columns are stored in the column storage The index fields are sorted in the engine's Stripe and then copied, including the column value and the row offset of the row where the column value is located; according to the index copy column, the Row Group that needs to be read is finally obtained. Through the present invention, the copied and sorted data can be used as a direct index for data reading, thereby reducing disk input and output costs, optimizing query performance, and can also be used as an indirect index to reduce data reading of other fields, further optimizing query efficiency, and can Realize the index on the finest storage granularity and improve the performance of fine-grained queries.

Description

A Distributed File Column Storage Index Method

technical field

The invention relates to the technical field of data query, in particular to a distributed data index and query method.

Background technique

In the era of big data, the distributed file system has become a standard file system for storing large-scale data in the online analysis and processing system in practical applications. Although the original design of the distributed file system is for sequential reading and writing of large files, in order to better support the query performance of the upper-level online analysis and processing system, some indexing schemes for distributed file systems have appeared in recent years. The finest granularity of schemas can be indexed down to the row level. Facing the challenge of PB (Petabyte) or even ZB (Zettabyte) level data in the era of big data, considering that compared with the traditional row storage engine, the column storage engine has better compression performance and fewer input and output operations. Most online analytical processing systems recommend using columnar storage as a storage method on a distributed file system. However, when the existing index schemes on the distributed file system are applied to the column storage engine, even the most fine-grained row-level index will degenerate into a coarse-grained index, which does not support fine-grained queries well. The existing column storage engine partially supports the most fine-grained clustered index in column storage, but the clustered index is implemented by sorting all data based on the index column, so there can only be one index field.

Contents of the invention

In view of the above problems, the present invention is proposed to provide a method for overcoming the above problems or at least partially solving the above problems.

The present invention provides a distributed file column storage index method, which includes the following steps:

Analyze the query statement to obtain the query condition;

Read the index copy column according to the index field in the query condition, and the index copy column is formed by copying after sorting the index field in the Stripe of the column storage engine, including the row offset of the column value and the row where the column value is located;

According to the index copy column, get the Row Group that needs to be read eventually.

Optionally, the index copy column does not replace the original data column.

Optionally, the index copy column is added behind the original data column,

Optionally, according to the query conditions, filter conditions, and query result fields, the final Row Group to be read can be obtained through different reading methods, including:

According to whether the query condition contains the index field, whether the filter condition contains other fields except the index field, and whether the query result field contains other fields except the field in the filter condition, the query is divided into three different reading methods .

Optionally, if the query condition contains index fields, the filter condition does not contain other fields except the index field, and the query result field does not contain other fields except the field in the filter condition, directly according to the index metadata information corresponding to the index field Select the index copy column Row Group that needs to be read.

Optionally, if the query condition contains index fields, and the filter condition does not contain other fields except the index field, but the query result field contains other fields besides the field in the filter condition, select the required read according to the index metadata information The index copy column Row Group, and read the index copy column data; parse out the row offset in the index copy column data, and parse the final Row Group that needs to be read.

Optionally, if the query condition includes index fields and filter conditions include other fields besides the index field, select the index copy column Row Group to be read according to the index metadata information, read the index copy column data; parse the index copy column Row offset in the data, and parse the selected Row Group that needs to be read under the conditions of the index field, and merge it with the Row Group under other fields to obtain the final Row Group that needs to be read.

Optionally, the method further includes: calculating the number of Row Groups that need to be read according to the index method according to any one of claims 1-7 according to the index metadata information, which is different from the number of Row Groups that need to be read without using the index method Compared with the number of Row Groups, if the former is greater than the latter, the indexing method described in any one of claims 1-7 is adaptively used, otherwise the indexing method described in any one of claims 1-7 is not used.

The technical solution provided in the embodiment of the present application has at least the following technical effects or advantages: when querying, the index copy column data can be directly read as a direct index to reduce disk input and output costs, optimize query performance, and can also be used as an indirect index to reduce other Field data reading to further optimize query efficiency.

The above description is only an overview of the technical solution of the present invention. In order to better understand the technical means of the present invention, it can be implemented according to the contents of the description, and in order to make the above and other purposes, features and advantages of the present invention more obvious and understandable , the specific embodiments of the present invention are enumerated below.

Description of drawings

Various other advantages and benefits will become apparent to those of ordinary skill in the art upon reading the following detailed description of the preferred embodiment. The drawings are only for the purpose of illustrating a preferred embodiment and are not to be considered as limiting the invention. Also throughout the drawings, the same reference numerals are used to designate the same parts. In the attached picture:

Fig. 1 shows the flowchart of the distributed file column storage index method according to the present invention;

Fig. 2 shows the data structure diagram of the index copy column proposed according to the present invention;

Fig. 3 shows a query flowchart of the indexing method proposed according to the present invention.

Detailed ways

Exemplary embodiments of the present disclosure will be described in more detail below with reference to the accompanying drawings. Although exemplary embodiments of the present disclosure are shown in the drawings, it should be understood that the present disclosure may be embodied in various forms and should not be limited by the embodiments set forth herein. Rather, these embodiments are provided for more thorough understanding of the present disclosure and to fully convey the scope of the present disclosure to those skilled in the art.

In one aspect of the present invention, the index scheme is a clustered index based on data replication. Data replication is to copy and sort the columns on the basis of retaining the original columns to form index copy columns, and the index copy columns are the columns sorted by the index columns value and the row offset of the row where the column value was originally located. When querying, the index copy column data can be directly read as a direct index to reduce disk input and output costs and optimize query performance, and can also be used as an indirect index to reduce data reading of other fields and further optimize query efficiency. The invention has better compatibility with existing distributed file systems, column storage engines and online analysis and processing systems.

The feature of sorting in this solution is that instead of globally sorting the entire column of data, the index fields are sorted and then copied in the column storage engine Stripe. This design avoids distributed clusters during index construction and query compared to global sorting. It can realize the index on the finest storage granularity and improve the performance of fine-grained query.

The implementation scheme of the index mainly includes the specific design of the index metadata and the design of the index query process, and the implementation scheme of the present invention is:

When the index metadata information of the present invention is used for querying index fields, the addressing of index copy columns can be realized according to the metadata information, and data filtering at Row Group level in the index copy columns can be realized. Specifically, the metadata information includes the column address offset of the index copy column, the data statistics information of each Row Group of the index copy column, and the row offset address of each Row Group.

As shown in Figure 1, the present invention proposes a distributed file column storage index method, the method includes the following steps:

S1. Analyzing the query statement to obtain the query condition;

S2. Read the index copy column according to the index field in the query condition, and the index copy column is to sort the index field in the Stripe of the column storage engine and copy the composition, including the row offset of the column value and the row where the column value is located;

S3. According to the index copy column, obtain the Row Group that needs to be read eventually.

The feature of the above method is that the copied sorted data can be used as a direct index to directly read data to reduce disk input and output costs and optimize query performance, and can also be used as an indirect index to reduce data reading of other fields and further optimize query efficiency.

Fig. 2 is the principle diagram of the index scheme of the present invention and the data structure diagram of the index copy column in the index scheme. When this index scheme is applied to the column storage engine on the distributed file system, as shown in Fig. On the basis of retaining the original data, the index field column 2 data in Stripe is sorted and copied to form the index copy column 2'. The index copy column structure is shown in Figure 2, and the column values and column values are sorted by the index columns The row offset of the previous row. In the process of generating the index copy column, the metadata information is generated according to the index metadata structure of the index of the present invention, and the metadata information includes the column address offset of the index copy column, the data statistics information of each Row Group of the index copy column, and the row offset of each Row Group address.

Stripe refers to the column storage of the distributed file system that divides the data block data into several Stripes by row, and uses Stripe as the unit to divide the column set storage unit. Row Group refers to dividing each column of data in Stripe into multiple Row Groups according to the number of rows. Row Group refers to the most fine-grained division granularity on the column storage of the distributed file system. This index scheme implements the most fine-grained index scheme on the column storage of the distributed file system. Stripe refers to the division granularity of the upper layer of the finest storage granularity. .

When executing the query, the query is divided into three categories, according to whether the query condition contains this index field, whether the filter condition contains other fields except this index field, and whether the query result field contains other fields except the field in the filter condition. parameters are divided. The first type of query refers to the query that includes this index field in the query condition, does not contain other fields except this index field in the filter condition, and does not contain other fields in the query result field except the field in the filter condition. The second type of query refers to queries that include this index field in the query condition, do not include other fields except this index field in the filter condition, but include other fields in the query result field besides the field in the filter condition. The third type of query refers to queries that include this index field in the query condition, and include other fields in the filter condition except this index field.

Below in conjunction with accompanying drawing 3, describe the specific embodiment of the invention in detail:

Fig. 3 describes the query process of the indexing scheme of the present invention. For each query, use this index to select the Row Group that needs to be read as shown in Figure 3, ignore the data that does not need to be read, reduce the disk input and output overhead, and improve query performance. And the number of Row Groups that need to be read after using this index and the number of Row Groups that need to be read can be calculated according to the index metadata information when querying. If the former is smaller than the latter, it means that using this index can reduce the number of Row Groups that need to be read. If the number of RowGroups is large, the index will be used adaptively, otherwise, the index can be selected not to be used, so as to realize the adaptive query strategy on the index scheme and improve query performance.

After the query statement is parsed, the query condition is obtained, based on three parameters: whether the query condition contains this index field, whether the filter condition contains other fields except this index field, and whether the query result field contains other fields except the field in the filter condition. , which divides queries into three types of queries. Each query type uses the index scheme of the present invention to obtain the Row Group to be read in a different process. The first type of query refers to the query that includes this index field in the query condition, does not contain other fields except this index field in the filter condition, and does not contain other fields in the query result field except the field in the filter condition. If this index is created for column 2 of tb1, such queries as: select count(*) from tb1where column 2>1and column 2<5. This type of query can directly select the index copy column RowGroup to be read according to the metadata information of the index and read the data, which reduces the disk input and output overhead and improves query performance. The second type of query refers to the query that includes this index field in the query condition and does not contain other fields except this index field in the filter condition, but the query result field contains other fields besides the field in the filter condition. Such queries include: select column 1, column 2 from tb1 where column 2>1 and column 2<5. This type of query not only needs to select the index copy column RowGroup to be read according to the index metadata information, read the index copy column data, but also use the index copy column data as index information for reading other fields, that is, parse out the index copy column The row offset in the data can be parsed into the Row Group that needs to be read in the end. The third type of query refers to the query that includes this index field in the query condition and other fields in the filter condition except this index field. This type of query is such as: select column 1, column 2 from tb1where column 2>1and column 2<5and column 3 =5. This type of query not only needs to select the index copy column Row Group to be read according to the index metadata information, read the index copy column data, but also use the index copy column data as index information for reading other fields, that is, parse out the index copy The row offset in the column data, and parse out the Row Group that needs to be read selected under the conditions of this index field, and merge it with the Row Group selected by other conditions to obtain the final Row Group that needs to be read, reducing disk input Output overhead to improve query performance. And the number of RowGroups that need to be read after using this index and the number of Row Groups that need to be read when this index is not used can be calculated according to the index metadata information during query. If the former is smaller than the latter, it means that using this index can reduce For the number of Row Groups that need to be read, this index is adaptively selected to be used; otherwise, this index is not used to implement an adaptive query strategy on this index scheme and improve query performance.

The technical solutions provided in the embodiments of the present application have at least the following technical effects or advantages:

The copied sorted data can be used as a direct index to directly read data to reduce disk input and output overhead and optimize query performance, and can also be used as an indirect index to reduce data reading of other fields and further optimize query efficiency.

The present invention does not perform global sorting on the entire column of data, but sorts the index fields in the column storage engine Stripe and then replicates them. Compared with global sorting, this design avoids the network overhead on the distributed cluster during index construction and query. And it can realize the index on the finest storage granularity and improve the performance of fine-grained query.

The present invention can adaptively select whether to use this index scheme for each query in combination with query characteristics and data distribution conditions during index query, which can effectively avoid queries that are not applicable to this index and improve query efficiency.

The methods and displays presented herein are not inherently related to any particular computer, virtual system, or other device. Various generic systems can also be used with the teachings based on this. The structure required to construct such a system is apparent from the above description. Furthermore, the present invention is not specific to any particular programming language. It should be understood that various programming languages can be used to implement the content of the present invention described herein, and the above description of specific languages is for disclosing the best mode of the present invention.

In the description provided herein, numerous specific details are set forth. However, it is understood that embodiments of the invention may be practiced without these specific details. In some instances, well-known methods, structures and techniques have not been shown in detail in order not to obscure the understanding of this description.

Similarly, it should be appreciated that in the foregoing description of exemplary embodiments of the invention, in order to streamline this disclosure and to facilitate an understanding of one or more of the various inventive aspects, various features of the invention are sometimes grouped together in a single embodiment, figure, or its description. This method of disclosure, however, is not to be interpreted as reflecting an intention that the claimed invention requires more features than are expressly recited in each claim. Rather, as the following claims reflect, inventive aspects lie in less than all features of a single foregoing disclosed embodiment. Thus, the claims following the Detailed Description are hereby expressly incorporated into this Detailed Description, with each claim standing on its own as a separate embodiment of this invention.

Furthermore, those skilled in the art will understand that although some embodiments herein include some features included in other embodiments but not others, combinations of features from different embodiments are meant to be within the scope of the invention. And form different embodiments. For example, in the following claims, any of the claimed embodiments may be used in any combination.

The various component embodiments of the present invention may be implemented in hardware, or in software modules running on one or more processors, or in a combination thereof. Those skilled in the art should understand that a microprocessor or a digital signal processor (DSP) can be used in practice to implement some or all functions of some or all components in the gateway, proxy server, and system according to the embodiments of the present invention. The present invention can also be implemented as an apparatus or an apparatus program (for example, a computer program and a computer program product) for performing a part or all of the methods described herein. Such a program for realizing the present invention may be stored on a computer-readable medium, or may be in the form of one or more signals. Such a signal may be downloaded from an Internet site, or provided on a carrier signal, or provided in any other form.

It should be noted that the above-mentioned embodiments illustrate rather than limit the invention, and that those skilled in the art will be able to design alternative embodiments without departing from the scope of the appended claims. In the claims, any reference signs placed between parentheses shall not be construed as limiting the claim. The word "comprising" does not exclude the presence of elements or steps not listed in a claim.

Claims (8)

1. a kind of distributed document row storage indexing means, which is characterized in that this method includes the following steps：Parse query statement Obtain querying condition；

Index field in querying condition reads index copy row, and the index copy row are in row storage engines It replicates and forms after being ranked up in Stripe to index field, the line displacement being expert at including train value and train value；

According to index copy row, acquisition finally needs the Row Group read.

2. according to the method described in claim 1, the index copy row do not replace original data row.

3. according to the method described in claim 2, the index copy row addition is behind original data row.

4. according to the method described in claim 1, different readings is passed through according to querying condition, filter condition, query result field Mode is taken to obtain the Row Group for finally needing to read, is specifically included：

According to whether comprising index field, in filter condition except index field in addition to whether including other fields in querying condition, look into Whether ask in result field except field in filter condition in addition to comprising three parameters of other fields, by inquiry be divided into three kinds it is different Reading manner.

5. method according to claim 2, if included in querying condition in index field, filter condition in addition to index field Not comprising other fields, and other fields are not included in query result field in addition to field in filter condition, directly according to index The corresponding index metadata information selection of field needs the index copy row Row Group read.

6. method according to claim 2, if included in querying condition in index field, filter condition in addition to index field Not comprising other fields, but other fields are also included in query result field in addition to field in filter condition, according to this index member Data information selection needs the index copy row Row Group read, and reads index copy column data；Parse index copy Line displacement in column data, and parsing finally needs the Row Group read.

7. method according to claim 2, if removing index field outsourcing in querying condition in packet index field, filter condition Containing other fields, the index copy row Row Group read are needed according to the selection of index metadata information, read index copy row Data；Line displacement in parsing index copy column data, and parse the Row that the needs chosen under the conditions of the index field are read Group, and merged with the Row Group under other fields, acquisition finally needs the Row Group read.

8. according to claim 1-5 any one of them methods, it is further characterized in that, this method further includes：According to the first number of index It is believed that breath calculates the Row Group numbers read according to claim 1-7 any one of them indexing means needs, the Row Group numbers are compared with the Row Group numbers read without using indexing means needs, if the former is less than the latter, from It adapts to, using claim 1-7 any one of them indexing means, otherwise index without using claim 1-7 any one of them Method.