Index selection for database query

One or more computer processors match a query pattern to a received query; context information related to the received query; retrieve a set of query records including the same context information as the obtained context information from an index knowledge base, wherein each query record in the set of query records include context information related to a respective history query, the query pattern, an index type associated with the query pattern, and performance information relating to the query pattern and the index type; determine that a subset of the retrieved query records includes one or more query patterns equivalent to the matched query pattern; select a query pattern and an associated index type from the subset of query records based on associated performance information in the set of query records; and perform the received query by applying the selected query pattern and the associated index type.

BACKGROUND

The present invention relates generally to the field of database queries, and more particularly to index selection for database query.

A database is an organized collection of data, generally stored and accessed electronically from a computer system. A query against data in the database is quite frequent. After receiving a query, a query pattern is matched to the query by the database. The query is performed based on the query pattern and an index specified by the database.

SUMMARY

Embodiments of the present invention disclose a computer-implemented method, a computer program product, and a system. The computer-implemented method includes one or more computer processers matching a query pattern to a received query. The one or more computer processors obtain context information related to the received query. The one or more computer processors retrieve a set of query records including the same context information as the obtained context information from an index knowledge base, wherein each query record in the set of query records include context information related to a respective history query, the query pattern, an index type associated with the query pattern, and performance information relating to the query pattern and the index type. The one or more computer processors determine that a subset of the retrieved query records includes one or more query patterns equivalent to the matched query pattern. The one or more computer processors select a query pattern and an associated index type from the subset of query records based on associated performance information in the set of query records. The one or more computer processors perform the received query by applying the selected query pattern and the associated index type.

DETAILED DESCRIPTION

Implementation of embodiments of the invention may take a variety of forms, and exemplary implementation details are discussed subsequently with reference to the Figures.

Characteristics are as follows:

Service Models are as follows:

Deployment Models are as follows:

As shown inFIG.1, computer system/server12in cloud computing node10is shown in the form of a general-purpose computing device. The components of computer system/server12may include, but are not limited to, one or more computer processors or processing units (i.e., processor16), a system memory28, and a bus18that couples various system components including system memory28to processor16.

The present invention may contain various accessible data sources that may include personal storage devices, data, content, or information the user wishes not to be processed. Processing refers to any, automated or unautomated, operation or set of operations such as collection, recording, organization, structuring, storage, adaptation, alteration, retrieval, consultation, use, disclosure by transmission, dissemination, or otherwise making available, combination, restriction, erasure, or destruction performed on personal data. The present invention provides informed consent, with notice of the collection of personal data, allowing the user to opt in or opt out of processing personal data. Consent can take several forms. Opt-in consent can impose on the user to take an affirmative action before the personal data is processed. Alternatively, opt-out consent can impose on the user to take an affirmative action to prevent the processing of personal data before the data is processed. The present invention enables the authorized and secure processing of user information, such as tracking information, as well as personal data, such as personally identifying information or sensitive personal information. The present invention provides information regarding the personal data and the nature (e.g., type, scope, purpose, duration, etc.) of the processing. The present invention provides the user with copies of stored personal data. The present invention allows the correction or completion of incorrect or incomplete personal data. The present invention allows the immediate deletion of personal data.

FIG.3depicts a set of functional abstraction layers provided by cloud computing environment50(FIG.2). It should be understood in advance that the components, layers, and functions shown inFIG.3are intended to be illustrative only and embodiments of the invention are not limited thereto. As depicted, the following layers and corresponding functions are provided:

There are multiple indexes built in the database such as B-tree, Hash, GiST, GIN, and BRIN. Each index type uses a different algorithm that is suited to different types of queries. Generally, an index type is specified to map with a query pattern according to user preference or default system settings. In these situations, it is not always efficient to perform a query. Performance of a query unexpectedly deteriorates due to an improper index type. Since the performance of the query is quite sensitive to a specific user, it is desirable to optimize index type to adapt to different query types to guarantee the performance of the query.

The embodiments of the present disclosure propose an index type selection mechanism for database query. Instead of specifying a fixed index type, different index types are selected to perform different kind of queries based on performance analysis for history quires. In this way, index type selection is optimized to ensure performance of the query.

FIG.4depicts database query system400which is an example database query system according to embodiments of the present disclosure is depicted. Database query system400includes client device401, network402, database system403and index knowledge base408. A user can interact with database system403through client device401. For example, client device401is a computer coupled to database system403via network402. The user can submit query409to database system403through network402. Database system403can respond to query409by generating search results410, which are transmitted through network402to client device401in a form that can be presented to the user. Database system403includes query pattern matching module404, context search model405, index type selector406and query performer407. In a nutshell, query pattern matching module404can match a query pattern to a received query such as query409. Context search model405can search context information related to a query in index knowledge base408. Index type selector406can select an index type for a received query such as query409from index knowledge base408. Query performer407can perform a query using the selected index type.

FIG.5is an example database query method according to embodiments of the present disclosure is depicted. The method500can be implemented by database query system400. The method500comprises steps502-512.

Query pattern matching module404, responsive to a query to a database, matches a query pattern to the received query (step502).

A query pattern provides one or more predefined rules for matching and interpreting a query. In some embodiments, several query patterns are defined manually. In some embodiments, query patterns are manually generated by testing various ways of splitting different types of queries and scoring candidate query patterns based on search results. A particular score can be required to select a query pattern from candidate query patterns. A query pattern can include, for example, a language identifier (e.g., English), a country or domain (e.g., the United States), stopwords, a connector, a confidence value, and a query splits filter strategy.

In particular, as used in one or more embodiments of the present disclosure, “{what}” is a placeholder for one or more query terms identifying a thing, while “{where}” is a placeholder for one or more query terms identifying a location. For example, a query pattern has a form {what} at {where} which describes a query jointed by the term of the connector “at”. Thus, the query pattern can be matched to a query of the form {what} at {where}, e.g., “Cafes at Fisherman's Wharf San Francisco”. When the query pattern is matched, the query can be split at the connector into corresponding {what} and {where} query components. For example, for a query of the form {what} at {where}, the pattern is split into query components corresponding to {what} and {where}. Each of these portions can be separately searched, for example, according to specialized indexes (e.g., a geocoding index). Thus, for the query “Cafes at Fisherman's Wharf San Francisco” is split into “Cafes” and “Fisherman's Wharf San Francisco”.

In an embodiment, query pattern matching module404annotates the query with particular labels that identify parts of the query. The labels are specified in accordance with the query pattern components, e.g., {prefix}, {suffix}, {query} and {connector}. Thus, the annotations are taken from the query pattern and matched to the corresponding query terms. For example, the query “Cafes at San Francisco square” can be annotated with the labels {what} {connector} {where} from the matching query pattern, where {what} is “Cafes”, {connector} is “at”, and {where} is “San Francisco”. Here, the {where} portion of the query “Cafes at Fisherman's Wharf San Francisco” is also indicated by geographical coordinates “lat=37.808517&lon=−122.411934&radius=100”. Therefore, a query can be explained with a plurality of query patterns. For the {where} part, the index type can be either attribute search or geospatial search etc.

Context search model405obtains context information related to the received query (step504). According to one or more embodiments, the context information related to the received query may include at least one of: the number of queries that have been processed during a predefined time period before the received query such as query409, index types corresponding to each of these queries, a source address of the received query, a query pattern matched to a previous query from the source address of the received query and search results of the previous query. Context search model405can obtain the context information related to the query from database system403.

Context search model405retrieves a set of query records including the same context information as the obtained context information from an index knowledge base (step506). Each of the set of query records include context information related to a respective history query, a query pattern, an index type associated with the query pattern, and performance information relating to the query pattern and the index type.

According to one or more embodiments, context search model405searches the context information in index knowledge base408. Index knowledge base408includes a plurality of query records created based on information related to history queries. The information related to each of the history queries includes a query string of each history query, context information related to each history query, a query pattern matched to a respective history query, an index type associated with the query pattern and performance information relating to the query pattern and its associated the index type. The history query is performed by applying the query pattern and the associated index type. The information related to history queries can be obtained from database system403. Similarly, context information related to each history query may include at least one of the number of queries that have been processed during a predefined time period before the received query, index types corresponding to each of the queries, a source address of the received query, a query pattern matched to a previous query from the source address of the received query, and search results of the previous query.

As noted above, query pattern matching module404can match a query pattern to each received query. Therefore, a query pattern matched to a respective history query can be obtained from query pattern matching module404. An index type performing each history query can be obtained from index type selector406. The performance information related to each history query such as a response time of the history query can be obtained from database system403. By way of example, Table 1 records information related to history queries obtained from database system403. Table 1 includes a plurality of entries, each of which corresponds to information related to a history query. By way of example, for history query A, query string A is a query string of history query A. Query pattern A is a matched query pattern of query string A. Context A is the context information related to history query A, index type A is selected to perform query A, and response time of query A is 1s.

According to embodiments, index knowledge base408is built up based on information related to history queries. Index knowledge base408includes a plurality of query records. Each of the query records includes context information related to a history query and a data pair related to the history query and performance information related to the data pair. The data pair related to the history query is comprised of a query pattern and an index type related to the history query. According to embodiments, context information related to history queries and data pairs related to the history queries and performance information related to the data pairs can be obtained from the information related to the history queries to create a plurality of query records. A performance related to each data pair includes the performance of a history query when the history query is performed using a query pattern and an index type included in each data pair. The performance of a history query may be, for example, but is not limited to, response time of the query, CPU utilization for performing the query, memory utilization for performing the query and network utilization for performing the query, etc.

By way of example, Table 2 shows a part of query records in index knowledge base408built on information related to history queries in Table 1. Context A, the data pair (query pattern A, index type A), and the performance (1s) in the 1stentry in Table 1 are extracted to create the 1stquery record in Table 2. Context B, the data pair (query pattern B, index type B), and the performance (2s) in the 2ndentry in Table 1 are extracted to create the fourth query record in Table 2. Context C, the data pair (query pattern C, index type C), and the performance (1s) in the 3rdentry in Table 1 are extracted to create the seventh entry in Table 2.

According to one or more embodiments, an identification (TD) is assigned to each query pattern. Equivalent query patterns share a same TD which signifies that an ID can uniquely identify equivalent query patterns. For example, in Table 2, ID1 can be used to uniquely identify equivalent query patterns A, A-1. ID 2 can be used to uniquely identify equivalent query patterns B, B-1, B-2. ID 3 can be used to uniquely identify equivalent query patterns C, C-1, C-2.

According to one embodiment, a performance ranking is added to each query record in index knowledge base408, which is provided based on performances related to data pairs having equivalent query patterns. For example, data pairs (query pattern B, index type A), (query pattern B-1, index type B), and (query pattern B-2, index type A) have equivalent query patterns B, B-1, B-2. The performances related to the data pairs (query pattern B, index type A), (query pattern B-1, index type B) and (query pattern B-2, index type A) are 2s, 1s and 3s, respectively. Therefore, the performances for the data pairs (query pattern B-1, index type B), (query pattern B, index type A), and (query pattern B-2, index type A) are respectively ranked first, second and third. It means that, of the three data pairs, the performances related to data pair (query pattern B-1, index type B) is the best and the performances related to data pair (query pattern B-2, index type A) is the worst.

Although the performance related to a data pair in Table 1 and Table 2 is response time of a respective history query, it is only for purposes of illustration but is not intended to limit the embodiments disclosed. According to one or more embodiments, response time of a history query may combine with at least one of other performance measurements of the history query including CPU utilization for performing the history query, memory utilization for performing the history query and network utilization for performing the history query etc. The performance ranking store can be calculated as below:
LGAN=Et1,t2˜Pdata[log(1−D(G(z,Bt1,+(1−Bt2)))]  (1)
with respect to equation (1), where Sirepresents a performance related to a data pair, w1represents a weight assigned to the performance related to the data pair, N represents the number of performances related to a data pair, 1≤i≤N and Σ1Nwi=1.

Those of ordinary skill in the art may understand that, the query records in Table 2 are only for purposes of illustration but is not intended to limit the embodiments disclosed. There are many solutions to record the query records in index knowledge base408, for example, the query records are created in a form of a file such as XML file or other data structures. Index knowledge base408can be updated every period of time (e.g., one month).

According to some embodiments, data pairs obtained from the information related to history queries can be further expended to create more query records to enrich index knowledge base408.

In step508, the present invention determines a subset of the retrieved query records includes one or more query patterns equivalent to the matched query pattern. According to some embodiments, index type selector406obtains IDs of respective query patterns in the retrieved query records from database system403. Index type selector406can further obtain an ID of the matched query pattern of the received query from database system403. Index type selector406can determine whether each of the IDs of respective query patterns in the retrieved query records is the same as that of the matched query pattern of the received query. As cited above, equivalent query patterns can be identified by an ID. In the scenario where a plurality of query patterns share a same ID number, this signifies that the plurality of query patterns are equivalent patterns. Index type selector406can make a comparison between each of the IDs of query patterns in the retrieved query records and that of the matched query pattern of the received query. In response to a determination that at least one ID is the same as that of the matched query pattern of the received query, index type selector406can determine a subset of the retrieved query records that include one or more query patterns equivalent to the matched query pattern.

The present invention selects a query pattern and its associated index type from the subset of query records based on performance information in the set of query records (step510). By way of example, it is assumed that context information related to the received query is context A and the query pattern of the received query is query pattern A-1 with ID1. Using context A as key words, the three query records including data pairs (query pattern A, index type A), (query pattern A, index type B), and (query pattern A-1, index type A) can be retrieved from index knowledge base408. By comparing ID1 and each ID of query patterns of the three data pairs, it is found that the query patterns of the three data pairs are equivalent with the query pattern of the received query. According to the three query records, the performance related to the data pair (query pattern A, index type A) is ranked the first therefore, query pattern A and index type A are selected from the three query records.

Query performer407performs the received query by applying the selected query pattern and its associated index type (step512). According to one embodiment, the selected query pattern and its associated index type includes the matched query pattern to the received query and a first index type. Query pattern performer407can perform the query by applying the matched query pattern and the first index type. According to one embodiment, the selected query pattern and its associated index includes a second query pattern equivalent to the matched query pattern and a second index type. Query performer407can perform the received query by applying the second query pattern and the second index type.

According to the present disclosure, instead of performing the query pattern and an index type specified by database system403, query performer407can perform the query using a query pattern and an index type in the selected data pair. Because the data pair is selected according to its performance information related to the data pair, the performance of the query can be guaranteed.

FIG.6depicts an example query records creation method according to embodiments of the present disclosure is depicted. According to embodiments of the present disclosure, the query records in index knowledge base408are divided into a plurality of groups. Each of the plurality of groups can be created by method600. Method600comprises steps602to608which can be implemented by database system403.

Database system403obtains context information related to a history query, a data pair related to the history query, and performance information related to the data pair (step602).

Database system403creates a query record including the context information related to the history query, the data pair related to the history query, and performance information related to the data pair (step604).

Database system403, responsive to a determination that a query pattern of the data pair related to the history query has at least one equivalent query pattern corresponding to at least one index type, creates at least one query record including the context information related to the history query and at least one data pair comprised of the at least one equivalent query pattern and the corresponding at least one index type and performance information related to the at least one data pair (step606).

As noted above, a query can be explained with a plurality of query patterns (i.e., equivalent query patterns of the query). Each of the equivalent query patterns can be supported by at least one index type. By way of example, in Table 2, query pattern A is a matched query pattern of query A. Query pattern A can be converted into query pattern A-1. Therefore, query pattern A and query pattern A-1 are equivalent query patterns. Query pattern A-1 can be supported by index type A. By designing a test instance meeting context A, a performance test of query A can be conducted using query pattern A-1 and index type A. As result, performance of query A such as response time can be obtained by executing the test instance on database system403. In this way, a new query record including context A, the data pair (query pattern A-1, index type A) and performance related to the data pair can be created. The new query record corresponds to the 3rdentry in Table 2.

Database system403, responsive to a determination that a query pattern of the data pair related to the history query corresponds to at least one index type other than an index type in the data pair related to the history query, creates at least one query record including the context information related to the history query, at least one data pair comprised of the query pattern and at least one index type, and performance information related to the at least one data pair (step608).

As known, a query pattern can be supported by at least one index type. Different index type can provide different performance for a query. By way of example, for query A in Table 1, besides index type A, index type B can support query pattern A. Designing a test instance in accordance with context A, performance test of query A can be conducted using query pattern A and index type B. Therefore, performance of query A, such as response time, can be obtained by executing the test instance on database system403. In this way, a new query record including context A, the data pair (query pattern A, index type B) and performance related to the data pair can be created. A new entry including the data pair (query pattern A, index type B) corresponding to context A and performance of the data pair can be generated and added to Table 2. The new query record corresponds to the 2nd entry in Table 2.

Therefore, based on the information related to history queries, more data pairs are expanded, and more query records are created in index knowledge base408. The performance related to these expanded data pairs can be acquired through executing designed test instances to meet specific context information.

According to some embodiments, index knowledge base408is stored in a storage separated from database system403. The information related to history queries can be stored either in database system403or in index knowledge base408. By way of example, after obtaining the context information of query409, a set of query records including the same context information as the obtained context information in step504can be retrieved from query records in index knowledge base408by context search model405.

It should be noted that the database query method according to embodiments of this disclosure could be implemented by computer system/server12ofFIG.1.