Query prediction

Patent metadata

Field	Value
Publication number	US-9734205-B2
Application number	US-201313865916-A
Country	US
Kind code	B2
Filing date	Apr 18, 2013
Priority date	Apr 18, 2013
Publication date	Aug 15, 2017
Grant date	Aug 15, 2017

Abstract

Disclosed here are methods, systems, paradigms and structures for predicting queries, creating tables to store data for the predicted queries, and selecting a particular table to obtain the data from in response to a query. The methods include determining various combinations of a finite set of columns users may query on, based on (i) a list of columns users are interested in obtaining data for, and (ii) cardinality information of a column or combinations of columns in the list of columns. The methods further includes creating various tables based on the determined combinations of the columns using a meta query language. A query is responded to by selecting a table that has least number of rows, among the tables that satisfy query parameters. The methods include selecting a table that has a longest sequence of columns matching with a portion of the query parameters.

First claim

What is claimed is:

1. A method, comprising:
receiving, at a computer system in a computer network, information regarding multiple data attributes associated with an application;
analyzing, by the computer system, the data attributes to determine cardinality information of the data attributes;
predicting, by the computer system and based at least in part on a set of queries received at the computer system, a set of the data attributes to be requested in the future;
generating, by the computer system and based at least in part on the cardinality information and the set of the data attributes, multiple tables, wherein different tables have different subsets of the data attributes as columns of the tables, wherein the multiple tables include a first table and a second table, wherein the first table and the second table both contain at least some common columns;
receiving, at the computer system and from an entity, a query having a plurality of query parameters;
selecting, by the computer system, one of the multiple tables in a storage system to obtain query results from, wherein selecting the one of the multiple tables includes:
analyzing the multiple tables to determine a prefix of each of the multiple tables, and
selecting a specified table of the multiple tables that has a longest common prefix with the query parameters, the longest common prefix being one of the determined prefixes containing a longest sequence of a plurality of leading columns that matches with a portion of the query parameters; and

obtaining, in response to the query, the query results from the specified table.

2. The method of claim 1 further comprising:
sending the query results to the entity that issued the query.

3. The method of claim 1 , wherein the query parameters include at least one of (a) names of columns, (b) filter criteria, or (c) aggregation criteria.

4. The method of claim 3 , wherein selecting the one of the tables with the longest common prefix includes selecting the particular table in which the longest sequence of the columns matches with columns of filter criteria.

5. The method of claim 1 , wherein generating the tables includes:
receiving the set of the data attributes as a user selection of a first list of columns, wherein the first list of columns is a subset of a finite set of columns on which potential user queries can be executed,
determining the cardinality information of the first list of columns,
expressing at least the first list of columns and the cardinality information of the first list of columns as a meta query language,
determining different subsets of the finite set of columns using the meta query language, and
generating the tables with the determined different subsets of the finite set of columns.

6. The method of claim 5 , wherein determining cardinality information of the first list of columns includes determining cardinality information of at least one of (a) individual columns in the first list of columns, or (b) a particular column in combination with another column from the first list of columns.

7. The method of claim 5 , wherein each of the tables has a determined subset of the columns in a decreasing order of the cardinality of the columns.

8. The method of claim 5 , wherein determining different subsets of the finite set of columns includes:
determining, by the computer system, a second list of columns of the finite set of columns for which at least one of (i) user queries is received frequently, or (ii) data is increasing in volume.

9. The method of claim 1 , wherein selecting one of the tables includes selecting the particular table which has least number of total rows to be read by the query to obtain the query results based on the query parameters.

10. A non-transitory computer-readable storage device storing computer-readable instructions, comprising:
instructions for receiving, by a computer system in a computer network, a user selection of a list of columns, wherein the list of columns is a subset of a finite set of columns;
instructions for analyzing, by the computer system, the list of columns to determine cardinality information of the list of columns, wherein the analyzing includes expressing at least the list of columns and the cardinality information of the list of columns as a meta query language;
instructions for predicting, by the computer system and based at least in part on a set of queries received at the computer system, a set of the columns to be requested in the future;
instructions for determining, by the computer system and based at least in part on the cardinality information and the set of the columns, different subsets of the set of columns using the meta query language;
instructions for generating, by the computer system, multiple tables in a storage system, each of the multiple tables having one of the different subsets of the set of columns;
instructions for receiving, from an entity in the computer network, a query having a plurality of query parameters; and
instructions for selecting, by the computer system and in response to receiving a query, one of the multiple tables to obtain query results from, wherein selecting the one of the multiple tables includes:
analyzing the multiple tables to determine a prefix of each of the multiple tables, and
selecting a specified table of the multiple tables that has a longest common prefix with query parameters, the longest common prefix being one of the determined prefixes containing a longest sequence of a plurality of leading columns that matches with the query parameters; and

instructions for obtaining, in response to the query, the query results from the selected table.

11. The non-transitory computer-readable storage device of claim 10 further comprising:
instructions for sending the query results to the entity that issued the query.

12. The non-transitory computer-readable storage device of claim 10 , wherein the instructions for selecting the one of the tables with the longest common prefix includes instructions for selecting the particular table in which the longest sequence of the columns matches with columns of filter criteria in the query parameters.

13. The non-transitory computer-readable storage device of claim 10 , wherein the selected particular table has least number of total rows to obtain the query results from.

14. The non-transitory computer-readable storage device of claim 10 further comprising:
instructions for retrieving statistical information from the storage system, the statistical information including information pertaining to management of the tables;
instructions for determining, at predefined time intervals, criteria for adapting the tables based on the statistical information; and
instructions for adapting, at predefined intervals, the tables, the adapting including at least one of (a) creating one or more new tables, (b) altering one or more existing tables, or (c) deleting one or more existing tables.

15. An apparatus, comprising:
a processor;
a table management criteria unit configured to:
receive information regarding multiple data attributes associated with an application,
analyze the data attributes to determine cardinality information of the data attributes, and
predict, based at least in part on a set of queries received at the computer system, a set of the data attributes to be requested in the future;

a table management unit configured to generate, based at least in part on the cardinality information and the set of the data attributes, multiple tables, wherein different tables have different subsets of the data attributes as columns

Assignees

• Facebook Inc

Inventors

• Rash Samuel
• Williamson Timothy
• Traverso Martin

Classifications

• G06F16/24553 Primary

  of query operations · CPC title

• G06F16/221

  Column-oriented storage; Management thereof · CPC title

• G06F17/30483 Primary

  Physics · mapped topic

• G06F17/30315

  Physics · mapped topic