CN103927346B - Query connection method on basis of data volumes - Google Patents

Abstract

The invention discloses a query connection method based on data volume. In the real-time query of big data, this method deeply considers the characteristics of columnar file reading and other characteristics to estimate the cost to ensure the generation of the best connection sequence. It mainly includes: first constructing the metadata server; then completing the collection of statistical information; Secondly, by querying the metadata server to obtain the relevant statistical information of each table participating in the connection; then, according to the statistical information, the selection and data volume and other related parameters are estimated; finally, the optimal connection sequence is found by calculating the corresponding cost of each execution plan. This method can improve the accuracy of cost estimation, so as to ensure that the execution plan is optimal, and effectively improve the efficiency of the overall query.

Description

Query join method based on data volume

technical field

The invention relates to the technical field of big data real-time query optimization, in particular to a query connection method based on data volume.

Background technique

Big data real-time query is an important big data technology. Existing big data query systems include Google Dremel, Cloudera Impala, Berkeley Shark, Apache Drill, etc. Big data real-time query generally adopts a distributed computing architecture, which has higher scalability than relational database clusters due to weakened support for functions such as transactions. At the same time, because big data real-time query can well meet the needs of real-time query users, it has broad application space in the Internet, smart cities and other fields.

Multi-connection sequential query optimization is an important part of the database management system, and it is also of irreplaceable importance in the field of big data real-time query technology. By adopting a certain optimization method, it continuously traverses the search space of the execution plan to find the best connection sequence to generate the best execution plan, thereby improving the performance of the big data query system and meeting the real-time requirements of user queries.

Since cost estimation is a very important part in the multi-join sequential query optimization process, whether an effective query cost estimation method can be given is the key to the effective implementation of query optimization. The traditional cost estimation method is a method based on table cardinality, which can effectively solve the traditional cost estimation problem, so as to ensure that the best execution plan conforming to the cost model is found. However, in a distributed database system or data warehouse, there are data tables stored in a columnar file format. This format file is used to optimize the I/O performance when the underlying data is read and reduce the amount of data transmitted. The RCFile file is used as the For example, the file is a file format split horizontally by rows and then vertically by columns, which will read and transfer only the required columns of data. When the data tables stored in the columnar file format participate in the connection, when the traditional cost estimation method based on the cardinality of the table is used for estimation, the result may have serious deviations, which will cause the connection order optimization algorithm to find the execution that conforms to the cost model The plan is not optimal, that is, the connection order found is not optimal, which makes the entire query delay higher.

Contents of the invention

The technical problem to be solved by the present invention is how to ensure that the big data real-time query system improves the accuracy of its cost estimation when optimizing the multi-connection sequence, thereby improving the overall efficiency of the query. In order to solve the above-mentioned problems existing in traditional cost estimation based on table cardinality, the present invention proposes a multi-join query cost estimation method based on data volume, which considers that the part of the relationship in the query submitted by the user may be stored in a columnar file, and through in-depth Consider features such as columnar file reading, add finer-grained statistical information, and use the average length of each field to estimate the size of the intermediate result of the query connection, thereby effectively ensuring the accuracy of cost estimation.

A query connection method based on data volume, including:

Step 1. Submit a query request to the metadata server to obtain statistical information corresponding to each table participating in the connection;

Step 2, estimate the data volume of all tables in the current execution plan according to the obtained statistical information;

Step 3, repeat step 1 and step 2 until traversing the search space of the execution plan, find out the execution plan with the appropriate amount of data to minimize the query cost, and connect the tables according to the connection sequence in the execution plan.

The search space of the execution plan refers to the collection of table connection sequences obtained by all execution plans.

The present invention uses the amount of data as the query cost to determine the sequence of connections in the multi-connection query, thereby ensuring that the big data real-time query system improves the accuracy of cost estimation when optimizing the multi-connection sequence, thereby improving the overall efficiency of the query.

Among them, the metadata server is constructed by selecting a relational database and designing a column-level table schema, and creating a metadata database and table relationships in the corresponding relational database according to the designed table schema to obtain a metadata server.

In order to be able to provide the query system with statistical information at three granularities of table level, partition level, and column level, the design of the corresponding table schema needs to conform to the appropriate paradigm, and at the same time, under the premise of completing the cost estimation, the unnecessary storage overhead should be minimized .

The statistical information in the metadata server is the statistical information corresponding to each table, and the statistical information is obtained by counting the tables according to the designed table schema.

The fine-grainedness of the statistical information is obtained from the fine-grainedness of the table schema. Since the table schema is a column-level schema, the statistical information includes column-level statistical information.

The relational database is: MYSQL database, Derby database or Oracle database.

According to the actual needs of enterprise users and systems, an appropriate relational database is selected as the metadata server of the big data real-time query system.

Statistics include: column name, lower bound of data value in column, upper bound of data value in column, number of empty column data in table, number of different values of column data in table, average length of field data in column, and The maximum length of the field data, total number of rows for the table or view.

The metadata server and the storage of statistical information in the metadata server are completed offline.

Since the construction of the metadata server and the collection of statistical information are completed offline, the return of statistical information during actual query does not require much runtime overhead, which greatly reduces the time delay of cost estimation.

In step 2, the data volume of each table is calculated according to the selectivity of the table, the average data volume of the field and the total number of rows of the table.

The degree of selectivity is based on statistical information such as the lower bound of the data value in the column, the upper bound of the data value in the column, and related conditions in the connection query, which are generally expressed by selectivity.

The method for estimating the selectivity is to perform corresponding calculations according to the query conditions and statistical information in the query, and obtain the proportion of the rows in the table that meet the query conditions in the object set to be queried.

The collection of objects is a collection of tables, views or intermediate results.

The formula for calculating the data volume size is as follows:

selectivity indicates the selectivity of the query, numsOfTableLine is the total number of rows in the table or view, avgColSize _i indicates the average amount of data in column i of the table to be returned, and j is the number of columns in the table.

Compared with the traditional estimation method based on table cardinality, it not only depends on the number of rows generated by the query intermediate results, but also takes the estimated data volume into consideration, thereby improving the accuracy of cost estimation.

Advantages of the present invention include:

In view of the problem of inaccurate estimation in the traditional cost method based on table cardinality, in-depth consideration of features such as columnar file reading and more fine-grained statistical information has effectively improved the accuracy of cost estimation.

The metadata server stores and maintains table-related statistical information, avoiding multiple analysis tasks, reducing runtime overhead, and improving the efficiency of cost estimation.

Description of drawings

Fig. 1 is an overall flow chart of the query connection method based on the amount of data in an embodiment of the method of the present invention;

FIG. 2 is a query processing architecture diagram adopted in the current embodiment of the present invention;

FIG. 3 is a flow chart of constructing a metadata server in the current embodiment of the present invention;

Fig. 4 is a flow chart of statistical information collection in the current embodiment of the present invention;

Fig. 5 is a flowchart of statistical information query in the current embodiment of the present invention;

Fig. 6 is a flow chart of data volume estimation in the current embodiment of the present invention;

Fig. 7 is a flowchart of connection sequence generation in the current embodiment of the present invention.

detailed description

The present invention proposes a query connection method based on data volume, and performs cost estimation on multi-connection queries when performing a query. The overall flow of the cost estimation method is shown in FIG. 1 . It first constructs the metadata server; then completes the collection of statistical information; secondly, obtains the relevant statistical information of each table participating in the connection by querying the metadata server; and then estimates the relevant parameters such as selectivity and data volume according to the statistical information ;Finally, use the estimation method based on the amount of data to calculate the corresponding cost of each execution plan to find the best connection sequence.

In order to more intuitively introduce the function of the method proposed in the present invention in query optimization, the architecture of query processing is shown in Figure 2, which illustrates the relationship between the cost estimation module based on data volume and the connection sequence generation module. Among them, in the connection sequence generation module, the relevant optimization method is used to search for the execution plan, and the cost estimation module based on data volume is mainly composed of two parts: the cost model and the MetaStore, to complete the cost estimation work. For the query submitted by the user, after parsing, the multi-connection sequential query optimization method will be used to complete the sequential optimization work. During the execution plan search process, it needs to call the relevant cost estimation module to estimate the cost, so as to ensure that it finds a query that meets the given requirements. Determines the optimal join order for the cost model.

The steps of the multi-connection query cost estimation method based on the amount of data proposed by the present invention include:

Before making a query connection, it is first necessary to build a metadata server and store statistical information in tables in the metadata server.

Relational database and design table schema, build metadata server.

In order to efficiently implement the cost estimation method based on the amount of data, it is first necessary to construct a metadata server. The process is shown in Figure 3, and the specific steps are as follows:

According to the actual needs of enterprise users and systems, select a suitable relational database (such as MYSQL database, Derby database) as the metadata server of the big data real-time query system;

In order to be able to provide the query system with statistical information at three granularities of table level, partition level, and column level, the design of the corresponding table schema needs to conform to the appropriate paradigm, and at the same time, under the premise of completing the cost estimation, the unnecessary storage overhead should be minimized ;

Create metadata and table relationships in the corresponding database server according to the designed table schema for use in subsequent steps.

According to the designed table schema, analyze the relationship in each table and store the corresponding statistical information in the metadata server to complete the collection of statistical information;

In order to optimize the connection order of the parsed query, the collection of statistical information needs to be completed after the metadata server is created. The process is shown in Figure 4, and the specific steps are as follows:

In order to reduce the overhead of cost estimation and statistical information acquisition during the connection sequence optimization process, first analyze the tables that are frequently connected and queried through corresponding analysis statements or tools;

Collect relevant statistical information on the analyzed table, and store the statistical information in the corresponding table of the metadata server. In order to better complete the cost estimation based on the amount of data, it is necessary to collect column levels including the average field length AVG_COL_LEN , which is given during the table schema design process. The statistical information includes: column name, the lower bound of the data value in the column, the upper bound of the data value in the column, the number of empty column data in the table, the number of different values of the column data in the table, the average data volume of the field data in the column, and The maximum amount of data for field data in a column, total number of rows for a table or view.

The creation of the metadata server (that is, the metadata database) and the collection of statistical information are completed offline, and then the query is performed.

Step 1, by submitting a query request to the metadata server to obtain the relevant statistical information of each table participating in the connection;

This step mainly completes the query and acquisition of relevant statistical information. The process is shown in Figure 5. The specific steps are as follows:

In order to obtain the corresponding statistical information of each table participating in the connection in the query, the query optimization module needs to submit a query request to the corresponding metadata server;

The statistical information corresponding to each table relationship is returned by the metadata server to complete the acquisition of statistical information, which is used for the calculation of relevant parameters in the next stage.

Since the construction of the metadata server and the collection of statistical information are completed offline, this step does not require much runtime overhead, which greatly reduces the time delay of cost estimation.

Step 2, estimate the data volume of all tables in the current execution plan according to the obtained statistical information.

The execution plan refers to queries performed in different table join sequences.

Before estimating the corresponding cost of the execution plan, it is necessary to complete the estimation of relevant parameters. The calculation process of relevant parameters including the degree of selectivity and data volume is shown in Figure 6. The specific steps are as follows:

Based on the relevant statistical information obtained in the previous step, first calculate the selectivity of each table participating in the connection, step 2-1, perform corresponding calculations according to the query conditions and statistical information in the connection query, and obtain the rows that meet the conditions in the desired query The proportion of objects in the collection.

For any two query conditions contained in the query, the corresponding calculation formulas are different for different relationships satisfied:

The formula for calculating selectivity _(AandB) when the query satisfies both query condition A and query condition B is:

selectivity (A and B ₎ = selectivity _(A) × selectivity _(B) (1)

Among them, selectivity _(A) represents the selectivity of a single query condition A, and selectivity _(B) represents the selectivity of a single query condition B;

The formula for calculating the selectivity _(AorB) when the query satisfies query condition A or query condition B is:

Selevtivity _(AorB) = P(A)+P(B)-selectivity _(AandB) (2)

P(A) represents the occurrence probability of query condition A, and P(B) represents the occurrence probability of query condition B;

The formula for calculating the selectivity _(notA) when the query meets the exclusion query condition A:

selectivity _(ntoA) =1-selectivity _(A) (3)

The satisfied relationship between any two query conditions A and B is: satisfy at the same time, satisfy A or satisfy B, and the query condition may not include A. When there are multiple query conditions and multiple relationships between the query conditions, the query conditions can be combined in pairs according to the above formulas, and calculated according to the relationship satisfied by each combination to obtain the final selectivity.

Step 2-2, calculate the amount of data in each table according to the selectivity obtained in step 2-1, the calculation formula is as follows:

selectivity indicates the selectivity calculated in step 2-1, numsOfTableLine is the total number of rows in the table or view, avgColSize _i indicates the average data volume of the column i in the table to be returned, and j is the number of columns in the table.

Input the amount of data in each table calculated by formula (4) into the cost model to estimate the cost of multi-join query, so as to obtain the cost of different execution plans. Compared with the traditional estimation method based on table cardinality, it not only depends on the number of rows generated by the query intermediate results, but also takes the estimated data volume into consideration, thereby improving the accuracy of cost estimation.

Step 3, repeat step 1 and step 2, until the search space of the execution plan is traversed, and the table connection order with the smallest amount of data is found for connection.

In order to be able to find the best connection sequence, the cost estimation method based on the amount of data proposed by the present invention needs to be used in the search process of the execution plan. The process flow is shown in Figure 7, and the specific steps are as follows:

According to the connection order optimization method adopted, the spatial search of the execution plan is performed (that is, repeating steps 1 and 2), which optimizes the performance of the execution plan search by considering the characteristics of the real-time query system and adding corresponding pruning techniques, reducing query latency performed by the algorithm itself;

Obtain the estimated value of the data volume of the corresponding execution plan through step 2, find out the execution plan that satisfies the given cost model, and store it;

According to the optimal execution plan found in the above steps, the optimal connection sequence is generated, and the accuracy of the cost estimation is effectively improved due to the adoption of the cost estimation method proposed by the present invention.

Claims (5)

1. A query connection method based on data volume, characterized in that, comprising: Step 1. Submit a query request to the metadata server to obtain statistical information corresponding to each table participating in the connection; Step 2, estimate the data volume of all tables in the current query execution plan according to the obtained statistical information; Step 3, repeat step 1 and step 2 until traversing the search space of the query execution plan, find out the execution plan with the appropriate amount of data to minimize the query cost, and connect the tables according to the connection sequence in the execution plan; In step 1, the method of constructing the metadata server is to select a relational database and design a column-level table schema, create a metadata database and table relationships in the corresponding relational database according to the designed table schema, and build a metadata server; In step 2, the data volume of each table is calculated based on the corresponding selectivity of the table, the average field data volume and the total number of rows in the table; the selection method is calculated according to the query conditions and statistical information in the query , to get the proportion of rows in the table that meet the query conditions in the object set to be queried; the calculation formula for the data size of each table is as follows: $\mathrm{<span\; class="notranslate">\; the\; s</span>}\mathrm{<span\; class="notranslate">\; i</span>}\mathrm{<span\; class="notranslate">\; z</span>}\mathrm{<span\; class="notranslate">\; e</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}\mathrm{<span\; class="notranslate">\; e</span>}\mathrm{<span\; class="notranslate">\; l</span>}\mathrm{<span\; class="notranslate">\; e</span>}\mathrm{<span\; class="notranslate">\; c</span>}\mathrm{<span\; class="notranslate">\; t</span>}\mathrm{<span\; class="notranslate">\; i</span>}\mathrm{<span\; class="notranslate">\; v</span>}\mathrm{<span\; class="notranslate">\; i</span>}\mathrm{<span\; class="notranslate">\; t</span>}\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; no</span>}\mathrm{<span\; class="notranslate">\; u</span>}\mathrm{<span\; class="notranslate">\; m</span>}\mathrm{<span\; class="notranslate">\; o</span>}\mathrm{<span\; class="notranslate">\; f</span>}\mathrm{<span\; class="notranslate">\; T</span>}\mathrm{<span\; class="notranslate">\; a</span>}\mathrm{<span\; class="notranslate">\; b</span>}\mathrm{<span\; class="notranslate">\; l</span>}\mathrm{<span\; class="notranslate">\; e</span>}\mathrm{<span\; class="notranslate">\; L</span>}\mathrm{<span\; class="notranslate">\; i</span>}\mathrm{<span\; class="notranslate">\; no</span>}\mathrm{<span\; class="notranslate">\; e</span>}<span\; class="notranslate">\; \&times;</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; avgColSize</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}$ selectivity indicates the selectivity of the query, numsOfTableLine is the total number of rows in the table or view, avgColSize _i indicates the average amount of data in column i of the table to be returned, and j is the number of columns in the table. 2. The query connection method based on data volume as claimed in claim 1, wherein the statistical information stored in the metadata server is the statistical information corresponding to each table, and the statistical information is performed on the table according to the designed table mode Statistics are obtained. 3. The query connection method based on data volume according to claim 1, wherein the relational database is: MYSQL database, Derby database or Oracle database. 4. The query connection method based on data volume as claimed in claim 1, wherein the statistical information includes: the column name, the lower bound of the data value in the column, the upper bound of the data value in the column, and the number of empty column data in the table , the number of distinct values of column data in a table, the average and maximum data size of field data in a column, and the total number of rows in a table or view. 5 . The query connection method based on data volume according to claim 1 , wherein the metadata server and the storage of statistical information in the metadata server are both completed in an offline state. 6 .