Database query tool

A memory stores a first log and a collection of queries. A processor accesses a second log that includes a first, second, third and fourth historical query, determines that the first and second historical queries belong to a first similarity group and the third and fourth historical queries belong to a second similarity group, and ranks the queries within groups based on static and dynamic features. The processor further determines the third historical query is frequently submitted and copies the highest ranked similar queries into the collection. The processor receives a first database query, stores it in both logs, determines it is not similar to queries stored in memory, further determines that it belongs to the first similarity group, copies the highest ranked similar queries to the first log, and returns a report containing the similar queries. The processor further receives and executes a second query selected from the report.

TECHNICAL FIELD

This disclosure relates generally to the access of data stored within databases.

BACKGROUND

Computer databases are commonly used by organizations to store large amounts of data. To access such data, users create and submit queries to the databases, where the queries are written in a standardized language, such as the Structured Query Language (SQL).

SUMMARY OF THE DISCLOSURE

Computer databases are commonly used by organizations to store large amounts of data. To access such data, users create and submit queries to the databases, where the queries are written in a standardized language, such as the Structured Query Language (SQL). Languages like SQL, however, are complex and difficult to learn. As a result, database users often are not experts in query construction, and tend to produce queries that are sub-optimal, when measured by the amount of resources needed by the computer to execute the queries. Furthermore, when multiple users access a database simultaneously, queries that may have been optimal when submitted by a user in isolation can become sub-optimal as a result of the current computer resource demands created by the other users.

This disclosure contemplates an unconventional database tool that addresses one or more of the above issues. The database tool uses historical queries previously submitted to the database to create groups of similar queries, where each query in a group is within a percentage of similarity to all the other queries within the same group. The percent similarity is calculated, for example, by splitting each query into a set of features, forming a pair of vectors using the features, and computing the cosine similarity between the two vectors. The database tool then stores groups of similar queries in similarity buckets, where each similarity bucket corresponds to a specific percent similarity range. Within each group, the database tool initially creates a ranked list of the most optimal queries, based on static features of the query and the database, such as the query features, cardinality, join conditions, etc. The database tool then periodically re-ranks the queries based on dynamic features, such as the network traffic, memory usage, and CPU usage.

When a user submits a query to the database, the database tool checks whether any historical queries are present that are similar within a given threshold to the newly submitted query, and then returns a report to the user containing either a ranked list of similar historical queries, or, if no similar historical queries are present, an estimate of the time required to run the user's proposed query. To decrease the amount of time required for the database tool to search for similar queries, the database tool stores in memory both those historical queries that are similar to a user's previously submitted queries, and those historical queries that are similar to queries that all users submit with high frequency. Then, when searching for the presence of similar historical queries, the database tool first compares the submitted query to those historical queries stored within the memory. Certain embodiments of the database tool are described below.

According to one embodiment, an apparatus includes a memory and a hardware processor communicatively coupled to the memory. The memory stores a first log and a collection of queries. The processor accesses a second log stored in a database. The second log includes a first historical query, a second historical query, a third historical query, and a fourth historical query. The processor further splits the first historical query into a first set of features, splits the second historical query into a second set of features, splits the third historical query into a third set of features, and splits the fourth historical query into a fourth set of features. The processor then forms a first vector comprising the first set of features, forms a second vector comprising the second set of features, forms a third vector comprising the third set of features, and forms a fourth vector comprising the fourth set of features. The processor then computes a first dot product of the first vector and the second vector, computes a first similarity index based on the first dot product, computes a second dot product of the third vector and the fourth vector, computes a second similarity index based on the second dot product, computes a third dot product of the first vector and the third vector, computes a third similarity index based on the third dot product, computes a fourth dot product of the first vector and the fourth vector, computes a fourth similarity index based on the fourth dot product, computes a fifth dot product of the second vector and the third vector, computes a fifth similarity index based on the fifth dot product, computes a sixth dot product of the second vector and the fourth vector, and computes a sixth similarity index based on the sixth dot product. The processor further determines that the first similarity index falls within a first range and that none of the third similarity index, the fourth similarity index, the fifth similarity index and the sixth similarity index fall within the first range. In response to determining that the first similarity index falls within the first range and that none of the third similarity index, the fourth similarity index, the fifth similarity index and the sixth similarity index fall within the first range, the processor stores the first historical query and the second historical query as a first similarity group in a first bucket corresponding to the first range, ranks the first historical query and the second historical query in the first similarity group at a first time based on a set of static system features, and re-ranks the first historical query and the second historical query in the first similarity group at a second time based on a set of dynamic system features. The processor further determines that the second similarity index falls within a second range, the second range lower than the first range, and that none of the third similarity index, the fourth similarity index, the fifth similarity index and the sixth similarity index fall within the second range. In response to determining that the second similarity index falls within the second range and that none of the third similarity index, the fourth similarity index, the fifth similarity index and the sixth similarity index fall within the second range, the processor stores the third historical query and the fourth historical query as a second similarity group in a second bucket corresponding to the second range, ranks the third historical query and the fourth historical query in the second similarity group at the first time based on the set of static system features, and re-ranks the third historical query and the fourth historical query in the second similarity group at the second time based on the set of dynamic system features. The processor further determines that a plurality of users submit the third historical query at a frequency greater than a set frequency. In response to determining that the plurality of users submit the third historical query at the frequency greater than the set frequency, the processor copies a set number of the highest ranked historical queries from the second similarity group into the collection of queries in a cache bucket corresponding to the second range. The processor further receives a first database query from a user. In response to receiving the first database query, the processor stores the first database query in the first log in a list corresponding to the user, stores the first database query in the second log, splits the first database query into a fifth set of features, and splits a list query stored in the first log in the list corresponding to the user into a sixth set of features. The processor then forms a fifth vector comprising the fifth set of features, forms a sixth vector comprising the sixth set of features, computes a seventh dot product of the fifth vector and the sixth vector, and computes a seventh similarity index based on the seventh dot product. The processor further determines that the seventh similarity index is not within a threshold. In response to determining that the seventh similarity index is not within the threshold, the processor splits a collection query stored in the collection of queries into a seventh set of features, forms a seventh vector comprising the seventh set of features, computes an eighth dot product of the fifth vector and the seventh vector, and computes an eighth similarity index based on the eighth dot product. The processor then determines that the eighth similarity index is not within the threshold. In response to determining that the eighth similarity index is not within the threshold, the processor determines that the first range is greater than the threshold. In response to determining that the first range is greater than the threshold, the processor calculates a ninth dot product of the fifth vector and the first vector, calculates a ninth similarity index based on the ninth dot product, calculates a tenth dot product of the fifth vector and the second vector, and calculates a tenth similarity index based on the tenth dot product. The processor then determines that the first similarity index, the ninth similarity index, and the tenth similarity index fall within the first range. In response to determining that the first similarity index, the ninth similarity index, and the tenth similarity index fall within the first range, the processor stores the database query in the first similarity group, copies the set number of the highest ranked historical queries from the first similarity group to the first log, and returns a report to the user containing a second set number of the highest ranked queries from the first similarity group. The processor further receives a second database query selected from the report by the user and executes the second database query.

According to another embodiment, a method includes accessing a second log stored in a database. The second log includes a first historical query, a second historical query, a third historical query, and a fourth historical query. The method also includes splitting the first historical query into a first set of features, splitting the second historical query into a second set of features, splitting the third historical query into a third set of features, and splitting the fourth historical query into a fourth set of features. The method further includes forming a first vector comprising the first set of features, forming a second vector comprising the second set of features, forming a third vector comprising the third set of features, and forming a fourth vector comprising the fourth set of features. The method further includes computing a first dot product of the first vector and the second vector, computing a first similarity index based on the first dot product, computing a second dot product of the third vector and the fourth vector, computing a second similarity index based on the second dot product, computing a third dot product of the first vector and the third vector, computing a third similarity index based on the third dot product, computing a fourth dot product of the first vector and the fourth vector, computing a fourth similarity index based on the fourth dot product, computing a fifth dot product of the second vector and the third vector, computing a fifth similarity index based on the fifth dot product, computing a sixth dot product of the second vector and the fourth vector, and computing a sixth similarity index based on the sixth dot product. The method further includes determining that the first similarity index falls within a first range and that none of the third similarity index, the fourth similarity index, the fifth similarity index and the sixth similarity index fall within the first range. In response to determining that the first similarity index falls within the first range and that none of the third similarity index, the fourth similarity index, the fifth similarity index and the sixth similarity index fall within the first range, the method includes storing the first historical query and the second historical query as a first similarity group in a first bucket corresponding to the first range, ranking the first historical query and the second historical query in the first similarity group at a first time based on a set of static system features, and re-ranking the first historical query and the second historical query in the first similarity group at a second time based on a set of dynamic system features. Additionally, the method includes determining that the second similarity index falls within a second range, the second range lower than the first range, and that none of the third similarity index, the fourth similarity index, the fifth similarity index and the sixth similarity index fall within the second range. In response to determining that the second similarity index falls within the second range and that none of the third similarity index, the fourth similarity index, the fifth similarity index and the sixth similarity index fall within the second range, the method includes storing the third historical query and the fourth historical query as a second similarity group in a second bucket corresponding to the second range, ranking the third historical query and the fourth historical query in the second similarity group at the first time based on the set of static system features, and re-ranking the third historical query and the fourth historical query in the second similarity group at the second time based on the set of dynamic system features. The method further includes determining that a plurality of users submit the third historical query at a frequency greater than a set frequency. In response to determining that the plurality of users submit the third historical query at the frequency greater than the set frequency, the method includes copying a set number of the highest ranked historical queries from the second similarity group into the collection of queries in a cache bucket corresponding to the second range. The method further includes receiving a first database query from a user. In response to receiving the first database query, the method includes storing the first database query in a first log in a list corresponding to the user, storing the first database query in the second log, splitting the first database query into a fifth set of features, and splitting a list query stored in the first log in the list corresponding to the user into a sixth set of features. The method further includes forming a fifth vector comprising the fifth set of features, forming a sixth vector comprising the sixth set of features, computing a seventh dot product of the fifth vector and the sixth vector, and computing a seventh similarity index based on the seventh dot product. The method further includes determining that the seventh similarity index is not within a threshold. In response to determining that the seventh similarity index is not within the threshold, the method includes splitting a collection query stored in a collection of queries into a seventh set of features, forming a seventh vector comprising the seventh set of features, computing an eighth dot product of the fifth vector and the seventh vector, and computing an eighth similarity index based on the eighth dot product. The method also includes determining that the eighth similarity index is not within the threshold. In response to determining that the eighth similarity index is not within the threshold, the method includes determining that the first range is greater than the threshold. In response to determining that the first range is greater than the threshold, the method includes computing a ninth dot product of the fifth vector and the first vector, computing a ninth similarity index based on the ninth dot product, computing a tenth dot product of the fifth vector and the second vector, and computing a tenth similarity index based on the tenth dot product. The method further includes determining that the first similarity index, the ninth similarity index, and the tenth similarity index fall within the first range. In response to determining that the first similarity index, the ninth similarity index, and the tenth similarity index fall within the first range, the method includes storing the database query in the first similarity group, copying the set number of the highest ranked historical queries from the first similarity group to the first log, and returning a report to the user containing a second set number of the highest ranked queries from the first similarity group. The method further includes receiving a second database query selected from the report by the user and executing the second database query.

According to a further embodiment, a system includes a storage element and a processing element communicatively coupled to the storage element. The storage element is operable to store a first log and a collection of queries. The processing element is operable to access a second log stored in a database. The second log includes a first historical query, a second historical query, a third historical query, and a fourth historical query. The processing element is further operable to split the first historical query into a first set of features, split the second historical query into a second set of features, split the third historical query into a third set of features, and split the fourth historical query into a fourth set of features. The processing element is further operable to form a first vector comprising the first set of features, form a second vector comprising the second set of features, form a third vector comprising the third set of features, and form a fourth vector comprising the fourth set of features. The processing element is additionally operable to compute a first dot product of the first vector and the second vector, compute a first similarity index based on the first dot product, compute a second dot product of the third vector and the fourth vector, compute a second similarity index based on the second dot product, compute a third dot product of the first vector and the third vector, compute a third similarity index based on the third dot product, compute a fourth dot product of the first vector and the fourth vector, compute a fourth similarity index based on the fourth dot product, compute a fifth dot product of the second vector and the third vector, compute a fifth similarity index based on the fifth dot product, compute a sixth dot product of the second vector and the fourth vector, and compute a sixth similarity index based on the sixth dot product. The processing element is further operable to determine that the first similarity index falls within a first range and that none of the third similarity index, the fourth similarity index, the fifth similarity index and the sixth similarity index fall within the first range. In response to determining that the first similarity index falls within the first range and that none of the third similarity index, the fourth similarity index, the fifth similarity index and the sixth similarity index fall within the first range, the processing element is operable to store the first historical query and the second historical query as a first similarity group in a first bucket corresponding to the first range and rank the first historical query and the second historical query in the first similarity group at a first time based on a set of static system features. The set of static system features includes query features, cardinality, join conditions, and filter conditions. The processing element is further operable to re-rank the first historical query and the second historical query in the first similarity group at a second time based on a set of dynamic system features. The set of dynamic system features includes network traffic, memory usage, and CPU usage. The processing element is further operable to determine that the second similarity index falls within a second range, the second range lower than the first range, and that none of the third similarity index, the fourth similarity index, the fifth similarity index and the sixth similarity index fall within the second range. In response to determining that the second similarity index falls within the second range and that none of the third similarity index, the fourth similarity index, the fifth similarity index and the sixth similarity index fall within the second range, the processing element is operable to store the third historical query and the fourth historical query as a second similarity group in a second bucket corresponding to the second range, rank the third historical query and the fourth historical query in the second similarity group at the first time based on the set of static system features, and re-rank the third historical query and the fourth historical query in the second similarity group at the second time based on the set of dynamic system features. The processing element is further operable to determine that a plurality of users submit the third historical query at a frequency greater than a set frequency. In response to determining that the plurality of users submit the third historical query at the frequency greater than the set frequency, the processing element is operable to copy a set number of the highest ranked historical queries from the second similarity group into the collection of queries in a cache bucket corresponding to the second range. The processing element is further operable to receive a first database query from a user. In response to receiving the first database query, the processing element is operable to store the first database query in the first log in a list corresponding to the user, store the first database query in the second log, split the first database query into a fifth set of features, and split a list query stored in the first log in the list corresponding to the user into a sixth set of features. The processing element is also operable to form a fifth vector comprising the fifth set of features, form a sixth vector comprising the sixth set of features, compute a seventh dot product of the fifth vector and the sixth vector, and compute a seventh similarity index based on the seventh dot product. The processing element is further operable to determine that the seventh similarity index is not within a threshold. In response to determining that the seventh similarity index is not within the threshold, the processing element is operable to split a collection query stored in the collection of queries into a seventh set of features, form a seventh vector comprising the seventh set of features, compute an eighth dot product of the fifth vector and the seventh vector, and compute an eighth similarity index based on the eighth dot product. The processing element is further operable to determine that the eighth similarity index is not within the threshold. In response to determining that the eighth similarity index is not within the threshold, the processing element is operable to determine that the first range is greater than the threshold. In response to determining that the first range is greater than the threshold, the processing element is operable to calculate a ninth dot product of the fifth vector and the first vector, calculate a ninth similarity index based on the ninth dot product, calculate a tenth dot product of the fifth vector and the second vector, and calculate a tenth similarity index based on the tenth dot product. The processing element is further operable to determine that the first similarity index, the ninth similarity index, and the tenth similarity index fall within the first range. In response to determining that the first similarity index, the ninth similarity index, and the tenth similarity index fall within the first range, the processing element is operable to store the database query in the first similarity group, copy the set number of the highest ranked historical queries from the first similarity group to the first log, and return a report to the user containing a second set number of the highest ranked queries from the first similarity group. The processing element is further operable to receive a second database query selected from the report by the user and execute the second database query.

Certain embodiments provide one or more technical advantages. For example, an embodiment will identify a sub-optimal user query and provide the user with a choice of similar queries the user could execute instead and thereby avoid wasting valuable computer resources. As another example, an embodiment monitors system resource usage and prioritizes similar historical queries according to resource availability, such that, for example, when memory usage in the system is high and a user submits a query that requires a large amount of memory to execute, the embodiment will suggest similar historical queries that require lower amounts of memory. As a further example, an embodiment reduces the time required by the database tool to search for historical queries similar to a newly submitted user query, by storing both the user's historical queries and frequently submitted historical queries in memory, along with highly ranked similar historical queries. Certain embodiments may include none, some, or all of the above technical advantages. One or more other technical advantages may be readily apparent to one skilled in the art from the figures, descriptions, and claims included herein.

DETAILED DESCRIPTION

Computer databases are commonly used by organizations to store large amounts of data. To access such data, users create and submit queries to the databases, where the queries are written in a standardized language, such as the Structured Query Language (SQL). Languages like SQL, however, are complex and difficult to learn. As a result, database users often are not experts in query construction, and tend to produce queries that are sub-optimal, when measured by the amount of resources needed by the computer to execute the queries. Furthermore, when multiple users access a database simultaneously, queries that may have been optimal when submitted by a user in isolation can become sub-optimal as a result of the current computer resource demands created by the other users.

This disclosure contemplates an unconventional database tool that addresses one or more of the above issues. The database tool uses historical queries previously submitted to the database to create groups of similar queries, where each query in a group is within a percentage of similarity to all the other queries within the same group. The percent similarity is calculated, for example, by splitting each query into a set of features, forming a pair of vectors using the features, and computing the cosine similarity between the two vectors. The database tool then stores groups of similar queries in similarity buckets, where each similarity bucket corresponds to a set percent similarity range. Within each group, the database tool initially creates a ranked list of the most optimal queries, based on static features of the query and the database, such as the query features, cardinality, join conditions, etc. The database tool then periodically re-ranks the queries based on dynamic features, such as the network traffic, memory usage, and CPU usage. When a user submits a query to the database, the database tool checks whether any historical queries are present that are similar within a given threshold, and then returns a report to the user containing either a ranked list of similar historical queries, or, if no similar historical queries are present, an estimate of the time required to run the user's proposed query. To decrease the amount of time required for the database tool to search for similar queries, the database tool stores in memory both those historical queries that are similar to a user's previously submitted queries, and those historical queries that are similar to queries that all users submit with high frequency. Then, when searching for the presence of similar historical queries, the database tool first compares the submitted query to those historical queries stored within the memory. By suggesting optimized similar historical queries when a user submits a sub-optimal query, the database tool is able to prevent the computer resource wastage that would otherwise occur. The database tool will be described in more detail usingFIGS. 1 through 3.

FIG. 1illustrates an example system100. As seen inFIG. 1, system100includes one or more devices110, a network115, a database120, and a database query tool125. Generally, database query tool125operates to provide similar, more optimal queries (as measured by the amount of resources needed by database query tool125to execute the queries) to a user105, when the user105submits a sub-optimal query150to database120. In this manner, certain embodiments of database query tool125prevent the waste of valuable system resources.

The similar, more optimal queries suggested by database query tool125are chosen from historical queries previously submitted to database120and stored by database query tool125in second log165. To efficiently determine if any historical queries similar to sub-optimal queries150submitted by users105exist, database query tool125places the historical queries stored in second log165into groups of similar historical queries, which it then stores in similarity buckets175, using bucketing calculation170. To provide users105with the most optimal similar historical queries, database query tool125ranks the historical queries stored in each similarity group according to both static and dynamic system features, as discussed in further detail below, in the discussion ofFIG. 2B. Additionally, database tool125stores the historical queries a user105submits to database120, along with similar, more optimal historical queries, in a list in first log140stored in memory135. Database tool125also stores the historical queries users150submit to database120at greatest frequency, along with similar, more optimal historical queries, in a collection of queries145stored in memory135. Then, to determine whether any similar historical queries exist, database query tool125first determines whether sub-optimal query150is similar to any historical queries stored in memory135, and if not, database query tool125then determines if the sub-optimal query150belongs to any similarity groups stored in similarity buckets175. Because database query tool125is able to perform this process without having to compare sub-optimal query150to each and every historical query stored in second log165, the process is more computationally efficient than simply searching second log165for similar, more optimal queries.

If database tool125determines that similar, more optimal historical queries exist, it returns a report160to user105containing a ranked list of one or more of the similar, more optimal queries. In certain embodiments, if database tool125determines that similar, more optimal historical queries do not exist, database tool125returns a report160to user105containing user105's original query, a statement that database query tool125could not find any similar, more optimal historical queries, and an estimate of the time required to execute query150. User105then submits a new query180to database120, chosen from report160, and database query tool125performs query180.

Devices110are used by users105to submit database queries to database120. For example, users105can use devices110to communicate a query or a list of queries150directed at database120to database tool125. Database tool125then determines whether query150is sub-optimal, and, if so, whether any similar, more optimal historical queries exist, either stored in memory135or in similarity buckets175. Devices110, can also receive a report160generated by database query tool125containing a ranked list of similar, more optimal historical queries. In certain embodiments, devices110can additionally receive a report160generated by database query tool125containing user105's original query, a statement that database query tool125could not find any similar, more optimal historical queries, and an estimate of the time required to execute query150. Devices110are further able to submit a second query180chosen from report160to database query tool125, which database query tool125then executes in database120. Devices110may also receive the results of the database queries submitted by database query tool125to database120. In certain embodiments, devices110may communicate with database tool125through network115via a web interface.

Devices110include any appropriate device for communicating with components of system100over network115. For example, devices110may be a telephone, a mobile phone, a computer, a laptop, a tablet, an automated assistant, and/or a cash register. This disclosure contemplates device110being any appropriate device for sending and receiving communications over network115. As an example, and not by way of limitation, device110may be a computer, a laptop, a wireless or cellular telephone, an electronic notebook, a personal digital assistant, a tablet, or any other device capable of receiving, processing, storing, and/or communicating information with other components of system100. Device110may also include a user interface, such as a display, a microphone, keypad, or other appropriate terminal equipment usable by user105. In some embodiments, an application executed by device110may perform the functions described herein.

Network115facilitates communication between and amongst the various components of system100. This disclosure contemplates network115being any suitable network operable to facilitate communication between the components of system100. Network115may include any interconnecting system capable of transmitting audio, video, signals, data, messages, or any combination of the preceding. Network115may include all or a portion of a public switched telephone network (PSTN), a public or private data network, a local area network (LAN), a metropolitan area network (MAN), a wide area network (WAN), a local, regional, or global communication or computer network, such as the Internet, a wireline or wireless network, an enterprise intranet, or any other suitable communication link, including combinations thereof, operable to facilitate communication between the components.

Database120stores an organization's data to which users105direct queries150and180. Additionally, database120stores historical queries previously submitted to database120, both as a list in second log165, and as groups of similar historical queries stored in similarity buckets175. Each individual similarity bucket in the group of similarity buckets175holds groups of historical queries, formed such that each historical query in a group is similar to every other historical query in the group within a particular range of similarity that is unique to the specific similarity bucket stored in the group of similarity buckets175. Here, the similarity between two historical queries can range from zero, when the historical queries are completely dissimilar, to one, when the historical queries are identical. This disclosure contemplates database120storing any number of buckets in the group of similarity buckets175. For example, database120could store three similarity buckets in the group of similarity buckets175, such that the first similarity bucket corresponds to a similarity range of 0.8 to 1.0, the second similarity bucket corresponds to a similarity range of 0.6 to 0.8, and the third similarity bucket corresponds to a similarity range of 0.4 to 0.6.

As seen inFIG. 1, database query tool125includes a processor130and a memory135. This disclosure contemplates processor130and memory135being configured to perform any of the functions of database query tool125described herein. Generally, database query tool125performs bucketing calculation170, where it calculates the similarity between pairs of historical queries stored in second log165, places historical queries into similarity groups such that each historical query in a similarity group is similar to every other historical query in the similarity group within a specific similarity range, stores similarity groups in similarity buckets175according to the specific similarity ranges, and ranks the historical queries within each similarity group based on the resources required to execute the queries.

Additionally, database query tool125stores a user105's historical queries, along with similar, more optimal historical queries, in a list corresponding to the user in a first log140in memory135. Database query tool125also stores the historical queries most frequently submitted to database120, along with similar, more optimal historical queries, in a collection of queries145stored in memory135. Then, when database query tool125receives a sub-optimal query150from user105, it performs similarity calculation155to determine whether any similar, more optimal historical queries exist. In performing similarity calculation155, database query tool125first determines whether any similar, more optimal historical queries exist in memory135, before searching for similar, more optimal historical queries in the similarity buckets175. Thus, certain embodiments of database query tool125reduce traffic to database120by searching memory135for similar, more optimal historical queries, rather than searching similarity buckets175stored on database120.

Processor130is any electronic circuitry, including, but not limited to microprocessors, application specific integrated circuits (ASIC), application specific instruction set processor (ASIP), and/or state machines, that communicatively couples to memory140and controls the operation of database tool125. Processor130may be 8-bit, 16-bit, 32-bit, 64-bit or of any other suitable architecture. Processor130may include an arithmetic logic unit (ALU) for performing arithmetic and logic operations, processor registers that supply operands to the ALU and store the results of ALU operations, and a control unit that fetches instructions from memory and executes them by directing the coordinated operations of the ALU, registers and other components. Processor130may include other hardware and software that operates to control and process information. Processor130executes software stored on memory to perform any of the functions described herein. Processor130controls the operation and administration of database query tool125by processing information received from network115, device(s)110, and memory135. Processor130may be a programmable logic device, a microcontroller, a microprocessor, any suitable processing device, or any suitable combination of the preceding. Processor130is not limited to a single processing device and may encompass multiple processing devices.

Memory135also stores a first log140containing a list for each user105of the historical queries the user105has previously submitted to database120, as well as any similar, more optimal historical queries. Database query tool125stores such historical queries in memory135under the assumption that users105often submit queries150that are similar to queries they have previously submitted. Additionally, memory135contains a collection of queries145, which contains all or a portion of any similarity groups from similarity buckets175containing historical queries that users105submit to database120most frequently. Database query tool125stores such historical queries in memory135based on the assumption that if all users105submit a historical query with great frequency, it is more likely that any given user105will submit this same query at some time in the future. As a result, certain embodiments of system100reduce the amount of time required by database query tool125to search for similar, more optimal historical queries, by storing those historical queries similar to queries user105is most likely to submit, in memory135.

In certain embodiments, system100reduces the waste of valuable system resources that may occur when a user105submits a sub-optimal query150to database120. Instead of executing the sub-optimal query150, database query tool125suggests more optimal historical queries that are nonetheless similar to the sub-optimal query150, which user105can submit to database120. In this manner, certain embodiments of database query tool125reduce the time required for a user105, who may not be an expert in query construction, to query database120, by taking advantage of historical queries that have proven efficient.

FIGS. 2A and 2Billustrate, in greater detail, the processes involved in bucketing calculation170. Bucketing calculation170includes the processes of creating groups of similar historical queries, storing these groups in similarity buckets175, and ranking the historical queries within these groups according to the amount of resources required by system100to execute the queries.

For simplicity, this example illustrates the bucketing calculation for historical queries205A through205D (among others) that were previously submitted by users105to database query tool125and are currently stored in second log165. However, this disclosure contemplates any number of historical queries stored in second log165. To determine if historical queries205A through205D are similar to one another, database query tool125calculates a similarity index between each pair of queries, where the similarity index ranges from zero to one. A similarity index of zero corresponds to a pair of queries that are completely dissimilar, while a similarity index of one corresponds to a pair of queries that are identical.

FIG. 2Aillustrates the process by which database query tool125calculates the similarity indices. Database query tool125first splits the historical queries205A through205D into features210A through210L (among others) and forms vectors215A through215D using these features. For example, vector215A is composed of features210A,210B, and210C (among others), where database query tool125formed features210A,210B, and210C from query one205A. Database tool125then calculates the dot products220A through220F between pairs of vectors215A through215D and uses the results to determine the similarity indices between pairs of queries205A through205D. In this example, the dot product220A between vector one215A and vector two215B leads to a similarity index of 0.95, the dot product220B between vector one215A and vector three215C leads to a similarity index of 0.92, the dot product220C between vector one215A and vector n215D leads to a similarity index of 0.55, the dot product220D between vector two215B and vector three215C leads to a similarity index of 0.96, the dot product220E between vector two215B and vector n215D leads to a similarity index of 0.61, and the dot product220F between vector three215C and vector n215D leads to a similarity index of 0.63.

FIG. 2Billustrates the process of grouping similar historical queries into similarity groups and storing the similarity groups in similarity buckets175. In this example, the similarity buckets175consist of five buckets225A through225E, covering a total similarity index range from 0.5 to 1.0. This disclosure, however, contemplates any number of similarity buckets, covering any similarity index range within the range 0.0 to 1.0. The first similarity bucket225A corresponds to similarity range 0.9 to 1.0. Accordingly, first similarity bucket225A will hold groups of similar historical queries for which the similarity indices calculated between every pair of historical queries within the group falls within the range 0.9 to 1.0. Similarly, the second similarity bucket225B will hold groups of similar historical queries for which the similarity indices calculated between every pair of historical queries within the group falls within the range 0.8 to 0.9, the third similarity bucket225C will hold groups of similar historical queries for which the similarity indices calculated between every pair of historical queries within the group falls within the range 0.7 to 0.8, the fourth similarity bucket225D will hold groups of similar historical queries for which the similarity indices calculated between every pair of historical queries within the group falls within the range 0.6 to 0.7, and the fifth similarity bucket225E will hold groups of similar historical queries for which the similarity indices calculated between every pair of historical queries within the group falls within the range 0.5 to 0.6.

As mentioned above, in the discussion ofFIG. 2A, the similarity index between query one205A and query two205B is 0.95, the similarity index between query one205A and query three205C is 0.92, and the similarity index between query two205B and query three205C is 0.96. Therefore, the similarity index calculated for every pair of queries in the group of query one205A, query two205B, and query three205C falls within the range of 0.9 to 1.0. As a result, query one205A, query two205B, and query three205C form a first similarity group230A that database query tool125ranks according to a set of static system features and stores in first similarity bucket225A Similarly, query two205B and query n205D form a second similarity group230B that database query tool125ranks according to the set of static system features and stores in fourth similarity bucket225D; query three205C and query n205D form a third similarity group230C that database query tool125ranks according to the set of static system features and stores in fourth similarity bucket225D; and query on205A and query n205D form a fourth similarity group230D that database query tool125ranks according to the set of static features and stores in fifth similarity bucket225E.

In particular embodiments, the set of static features used by database query tool125to rank the historical queries stored in similarity groups includes the query features210A through210L (among others), cardinality, join conditions, and filter conditions. These static features relate to both the form of query150and the structure of the data stored in database120. The effect that these static features will have on the amount of system resources required by database120to execute query150will remain constant in time, unaffected by network traffic, memory usage, or CPU usage.

In particular embodiments, the process of forming similarity groups, ranking the historical queries within each similarity group according to the set of static system features, and storing the similarity groups in similarity buckets175occurs once each day. For example, this process may occur once during the night when users105are less likely to submit queries150and180to database120, and database query tool125would otherwise be idle. As a result, database query tool125is able to conserve system resources by reducing the demand on processor130during the day when processor130is performing similarity calculations155.

Once database query tool125has placed the historical queries205A through205D into similarity groups, ranked the historical queries within each similarity group according to the set of static system features, and stored the similarity groups in similarity buckets175, database query tool125further re-ranks the historical queries within each similarity group according to a set of dynamic system features. For example, database query tool125re-ranks first similarity group230A stored in first similarity bucket225A into first similarity group230E stored in first similarity bucket225F. Database query tool125similarly re-ranks second similarity group230B stored in fourth similarity bucket225D into second similarity group230F stored in fourth similarity bucket2251, re-ranks third similarity group230C stored in fourth similarity bucket225D into third similarity group230G stored in fourth similarity bucket2251, and re-ranks fourth similarity group230D stored in fifth similarity bucket225E into fourth similarity group230H stored in fifth similarity bucket225J.

In certain embodiments the set of dynamic system features includes network traffic, memory usage, and CPU usage. Database query tool125performs this re-ranking because when multiple users105access a database120simultaneously, historical queries that may have been optimal when submitted by a user105in isolation can become sub-optimal as a result of the current system resource demands created by other users105. By re-ranking the historical queries within each similarity group based on dynamic system features, database query tool125is able to prioritize historical queries according to resource availability, such that, for example, when memory usage in database query tool125is high and a user105submits a query150that requires a large amount of memory to execute, database query tool125will suggest similar historical queries that require lower amounts of memory.

In particular embodiments, database query tool125performs this re-ranking multiple times throughout the day at a set re-ranking frequency. Performing the re-ranking at multiple times throughout the days helps to ensure that the historical queries within each similarity group are ranked according to the current resources of database tool125.

In certain embodiments, the processes of ranking and re-ranking the historical queries stored in similarity groups is performed by a machine learning algorithm. For example, in particular embodiments, database query tool125attaches a weight to each of the static and dynamic features used to rank and re-rank the queries and uses machine learning to determine the optimal values for these weights.

FIG. 2Balso illustrates the process by which database query tool125populates the collection of queries145stored in memory135. In this example, database query tool125determines that users105submit query two205B to database120with a frequency greater than a set frequency f. As a result, database query tool125copies similarity groups230E and230F, both containing query two205B, into the collection of queries145. Since query two205B is submitted to database120frequently by users105, there is a reasonable likelihood that any given user105will submit a query150to database120that is similar to query two205B. By storing the highest ranked queries within similarity groups230E and230F in memory135, database query tool125ensures that if a user150does submit a query150to database120that is similar to query two, database query tool125can access similar historical queries in memory135without accessing the similarity buckets175stored in database120, thereby reducing the time required to return suggested similar, more optimal historical queries to user105. While this example illustrates database query tool125copying the entire similarity groups230E and230F into the collection of queries145, certain embodiments of system100contemplate database query tool125copying only a set number of the highest ranked queries within each similarity group230E and230F into the collection of queries145. This may be desirable, for example, to reduce the total amount of data memory135stores.

By storing groups of similar historical queries in similarity buckets175, bucketing calculation170, illustrated inFIGS. 2A and 2B, provides an efficient means for determining whether a sub-optimal query150is similar, within a given threshold, to any historical queries stored in second log165; to determine whether a sub-optimal query150is similar to any such historical queries, database query tool125merely determines whether the sub-optimal query150belongs to any similarity groups stored in similarity buckets175, corresponding to similarity ranges above the given threshold. Because database query tool125is able to perform this process without having to compare sub-optimal query150to each and every historical query stored in second log165, the process is more computationally efficient than simply searching second log165for similar, more optimal queries. Additionally, by ranking the historical queries within each similarity group according to dynamic features as well as static features, database query tool125is able to provide users105with optimal historical queries, tailored to the current resource demands of the system.

FIGS. 3A and 3Billustrate the process by which database query tool125determines whether any similar, more optimal historical queries exist when user105submits a sub-optimal query150to database120. Here, a historical query is considered similar to query150if the similarity index between the historical query and query150is within a set threshold.

In certain embodiments, the set threshold is adjustable by user105. This may be desirable, for example, for a user105who is unsure about the query150that the user105is submitting to database120. In such situations, user105may want to increase the range of similarity indices covered by the set threshold to improve the chances that database query tool125will returns suggestions of similar, more optimal historical queries.

In step305, database query tool125receives query150from user105. Database query tool125then, in step310, stores this query in a list corresponding to user105in a first log140stored in memory135. Next, in step315, database query tool125determines whether any similar, more optimal historical queries are present in user105's list stored in first log140. This process is similar to the process of determining similarity groups, described above forFIG. 2A. Database query tool125first splits user105's query150into a set of features, and then forms a vector (database query vector) using these features. Database query tool125similarly forms vectors for the historical queries stored in first log140in the list corresponding to user105(list vectors). Database query tool125then computes dot products between the database query vector and the list vectors and uses these dot products to compute similarity indices. Historical queries stored in user105's list are determined by database query tool125to be similar to query150if the similarity indices calculated between the historical queries and query150fall within the set threshold.

If database query tool125determines that no similar historical queries are stored in user105's list in first log140, in step325database query tool125next determines whether any similar historical queries are present in the collection of queries145. Database query tool125first searches similarity bucket235A, stored in the collection of queries145, which corresponds to the highest similarity index range. If database query tool125determines that query150does not belong to any of the similarity groups230E stored in first similarity bucket235A, it proceeds to search second similarity bucket235B, corresponding to the second highest similarity index range, provided that this similarity index range is greater than the set threshold. For example, in the example shown inFIG. 2B, if the set threshold is 0.8, database query tool125will search both the first similarity bucket235A and the second similarity bucket235B. On the other hand, if the set threshold is 0.9, database query tool125will only search the first similarity bucket235A. If the set threshold is less than 0.8 and database query tool125determined that query150does not belong to any similarity groups stored in similarity buckets235A and235B, database query tool125will continue to search similarity buckets235C through235E until: (1) database query tool125determines that query150belongs to a similarity group stored in one of the similarity buckets; or (2) database query tool reaches a similarity bucket corresponding to a similarity index range outside the set threshold; or (3) database query tool125searches all similarity buckets235C through235E and determines that query150does not belong to any of the similarity groups stored within the collection of queries145. This example assumes that the collection of queries145consists of five similarity buckets235A through235E. However, this disclosure contemplates the collecting of queries145containing any number of similarity buckets.

If database query tool125determines that query150does not belong to any similarity groups stored in the collection of queries145, in step340database query tool125next determines whether any similar historical queries are present in similarity buckets175. This process is similar to the process described above for step325. Database query tool125first searches first similarity bucket225F, stored in similarity buckets175, which corresponds to the highest similarity index range. If database query tool125determines that query150does not belong to any of the similarity groups230E stored in first similarity bucket225F, it proceeds to search second similarity bucket225G, corresponding to the second highest similarity index range, provided that this similarity index range is greater than the set threshold. For example, in the example shown inFIG. 2B, if the set threshold is 0.8, database query tool125will search both the first similarity bucket225F and the second similarity bucket225G. On the other hand, if the set threshold is 0.9, database query tool125will only search the first similarity bucket225F. If the set threshold is less than 0.8 and database query tool125determines that query150does not belong to any similarity groups stored in similarity buckets225F and225G, database query tool125will continue to search similarity buckets225H through225J until: (1) database query tool125determines that query150belongs to a similarity group stored in one of the similarity buckets225H through225J; or (2) database query tool reaches a similarity bucket corresponding to a similarity index range outside the set threshold; or (3) database query tool125searches all similarity buckets225H through225J and determines that query150does not belong to any of the similarity groups stored within similarity buckets175. This example assumes that similarity buckets175contains five similarity buckets235A through235E. However, this disclosure contemplates similarity buckets175containing any number of similarity buckets.

In particular embodiments, if database query tool125determines that query150does not belong to any similarity groups stored in the collection of queries145, in step355database query tool125returns a report160to user105containing the database query150submitted by user105, a statement that the database query tool could not provide any suggested queries, and an estimate of the time required to run query150.

In particular embodiments, if database query tool125determines that user105's list in first log140contains similar, more optimal historical queries, database query tool125returns a report160to user105containing a ranked list of a set number of the similar list queries, in step320.

In particular embodiments, if database query tool125determines that query150belongs to a similarity group stored in the collection of queries145, database query tool125first copies a set number of the highest ranked similar queries from the similarity group into user105's list in first log140, in step330. Then, in step335, database query tool125returns a report160to user105containing a ranked list of the historical queries stored in the similarity group.

If database query tool125determines that query150belongs to a similarity group stored in similarity buckets175, database query tool125first copies a set number of the highest ranked similar queries from the similarity group into user105's list in first log140, in step345. Then, in step350, database query tool125returns a report160to user105containing a ranked list of a set number of the historical queries stored in the similarity group.

Finally, in step360, database query tool125receives a second query180from user105, selected from report160, and in step365database query tool125executes the second query180in database120.

Modifications, additions, or omissions may be made to method300depicted inFIGS. 3A and 3B. Method300may include more, fewer, or other steps. For example, steps may be performed in parallel or in any suitable order. While discussed as database query tool125(or components thereof) performing the steps, any suitable component of system100, such as device(s)110for example, may perform one or more steps of the method.

Although the present disclosure includes several embodiments, a myriad of changes, variations, alterations, transformations, and modifications may be suggested to one skilled in the art, and it is intended that the present disclosure encompass such changes, variations, alterations, transformations, and modifications as falling within the scope of the appended claims.