Method and system for optimizing queries in a multi-tenant database environment

• US 8,655,867 B2
• Filed: 01/26/2011
• Issued: 02/18/2014
• Est. Priority Date: 05/13/2010
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Collins, Jesse, Bathija, Jaikumar
• Primary Examiner(s): Mofiz, Apu
• Assistant Examiner(s): NGUYEN, THU N
• Application Number:
  US13/014,115
• Publication Number:
  US 20110282864A1
• Time in Patent Office: 1,119 Days
• Field of Search: None
• US Class Current: 707/719
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation

Abstract

In accordance with embodiments, there are provided mechanisms and methods for query optimization in a database system. These mechanisms and methods for query optimization in a database system can enable embodiments to optimize OR expression filters referencing different logical tables. The ability of embodiments to optimize OR expression filters referencing different logical tables can enable optimization that is dynamic and specific to the particular tenant for whom the query is run and improve the performance and efficiency of the database system in response to query requests.

Claims

1. A machine-implemented method comprising:

a computer system including one or more computers, which includes at least a processor system having at least one processor, receiving a user query;

the processor system parsing the user query and automatically generating a set of parallel subqueries that in combination are equivalent to the user query in results that are expected to be returned, where the parsing of the user query determines one or more OR clauses to be within the user query;

the computer system forming a query that is applied to multiple database tables, if a cost of the user query is expected to be more than the query formed, the forming of the query being by at least forming a clause that combines the set of parallel subqueries into a query equivalent to the user query;

the method also including at least

generating, by the computer system, prequeries the prequeries being a series of queries that are run to determine an estimate of a cost of each of the parallel subqueries;

optimizing, by the computer system, individual subqueries of the parallel subqueries with a query optimizer by, for each of the individual subqueries, the query optimizer determining which of a plurality of methods of performing a query has a lowest calculated cost;

calculating, by the computer system, computational costs of the filters in the subqueries by at least;

determining, by the computer system, for each of the subqueries, selectivities of the filters, each selectivity of a filter being determined by counting, by the computer system, how many records are selected by applying the filter, or

by determining, by the computer system, what fraction of the records of a total number of records in a table match each filter;

summing, by the computer system, the selectivities of the filters;

determining, by the computer system, whether the cost of the user query is expected to be more than the query formed with the clause that combines the set of parallel subqueries where the combining of the set of parallel subqueries is performed by at least comparing the computational costs of the filters in the subqueries to the user query;

where the prequeries include at least range scans against an index, and there is at least a row limit to stop the range scan when it is determined that a particular filter is not selective;

where the index includes at least a custom index, where the custom index accesses data belonging to a specified user from the database network that contains data belonging to a series of separate users, or the index includes at least an accelerator table that is an indexed table that is added to the user query to give the user query a driving index;

where the computer system includes a database network system that is a multi-tenant database system.

2. The method of claim 1 where the clause includes at least a UNION ALL clause.

3. The method of claim 1 where the index includes at least a custom index, where the custom index accesses data belonging to a specified user from the database network that contains data belonging to a series of separate users.

4. The method of claim 1 where the index includes at least a form of accelerator table that is an extra indexed table that is added to the user query to give the user query a driving index.

5. The method of claim 1 where the computer system includes a database network system that is a multi-tenant database system.

6. The method of claim 1, at least a first subquery being a performed for a first table and at least a second subquery being performed for a second table that is a different size than the second table, and the computational cost being based on the summing of the selectivities despite the first table and second table having different sizes.

7. The method of claim 1, further comprising

receiving user input;

automatically forming the user query in a database language based on the user input;

the user query parsed being in the database language.

8. The method of claim 1, the parallel queries including at least a first subquery that is a performed for a first table and at least a second subquery that is performed for a second table that is different than the second table.

9. The method of claim 1, the combined query including the subqueries, and each subquery being mutually exclusive of all other subqueries.

10. The method of claim 1, the database having many tenants, the method further comprising:

optimizing each subquery with a query optimizer based on the lowest calculated cost of the subquery for a tenant associated with the user.

11. The method of claim 1 where the computer system includes a database network system that is a multi-tenant database system;

the user being associated with one of many tenants of the multi-tenant database that share at least one table, each tenant having a different portion of the table and the database that the tenant has access to;

the combined query being limited to the portion of the multi-tenant database that the tenant has access to;

the method further comprising computing the cost of the query having the clause based on the portion of the multi-tenant database that the tenant has access to;

wherein an optimization of the query is specific to the tenant and the query.

12. The method of claim 1, further comprising:

determining a maximum limit as to the number of records returned;

a threshold percentage of records of a table, where a query term that returns more than the threshold percentage of records is considered unselective;

setting a threshold number of rows as a minimum of the maximum number of rows and a product of the threshold percentage and the rows of the table;

computing a selectivity as a number of rows returned divided by the threshold number of rows; and

a filter that is not selective on a corresponding custom index table is not joined to other custom index tables as part of the performing the query.

13. A non-transitory machine-readable medium carrying one or more sequences of instructions for optimizing queries in a database network system, which instructions, when executed by a computer system including one or more computers having a processor system including one or more processors, cause a method to be carried out, the method comprising:

receiving a user query at the computer system;

parsing, by the processor system, the user query and automatically generating a set of parallel subqueries that in combination are equivalent to the user query in results that are expected to be returned; and

forming, by the processor system, a query that is applied to multiple database tables, if a cost of the user query is expected to be more than the query formed, the forming of the query being by at least forming a clause that combines the set of parallel subqueries into a query equivalent to the user query

the method also including at least

generating, by the processor system, prequiries that are a series of queries that are run to determine an estimate of a cost with each of the parallel subqueries;

optimizing, by the computer system, individual subqueries of the parallel subqueries with a query optimizer by, for each of the individual subqueries, the query optimizer determining which of a plurality of methods of performing a query has a lowest calculated cost;

calculating, by the computer system, computational costs of the filters in the subqueries by at least determining, by the computer system, for each of the subqueries, selectivities of the filters, each selectivity of a filter being determined

by counting, by the computer system, how many records are selected by applying the filter, or

by determining, by the computer system, what fraction of the records of a total number of records in a table match each filter;

summing, by the computer system, the selectivities of the filters;

determining, by the computer system, the cost of the user query is expected to be more than the query formed with the clause, combining the set of parallel subqueries by at least comparing the computational costs of the filters in the subqueries to the user query;

where the prequeries include at least range scans against an index, and there is at least a row limit to stop the range scan when it is determined

that a particular filter is not selective;

where

the index includes at least a custom index, where the custom index accesses data belonging to a specified user from the database network that contains data belonging to a series of separate users, or

the index includes at least a form of accelerator table that is an indexed table that is added to the user query to give the user query a driving index; and

where the computer system includes a database network system that is a multi-tenant database system.

14. A computer system having one or more computers for optimizing queries in a database network system, the computer system comprising:

a processor system including at least one processor; and

a memory system including a machine readable medium having stored thereon one or more sequences of instructions which, when executed, cause a method to be carried out,

the method including at least

receiving a user query at the computer system;

parsing, by the processor system, the user query and automatically generating a set of parallel subqueries that in combination are equivalent to the user query in results that are expected to be returned, where the parsing, of the user query determines one or more OR clauses to be within the user query;

forming, by the processor system, a query that is applied to multiple database tables, if a cost of the user query is expected to be more than the query formed, the forming of the query being by at least forming a clause that combines the set of parallel subqueries into a query equivalent to the user query

the method also including at least

generating preguiries that are a series of queries that are run to determine an estimate of a cost with each of the parallel subqueries;

optimizing, by the computer system, individual subqueries of the parallel subqueries with a query optimizer by, for each of the individual subqueries, the query optimizer determining which of a plurality of methods of performing a query has a lowest calculated cost;

calculating, by the computer system, computational costs of the filters in the subqueries by at least

determining, by the computer system, for each of the subqueries, selectivities of the filters, each selectivity of a filter being determined

by counting, by the computer system, how many records are selected by applying the filter, or

by determining, by the computer system, what fraction of the records of a total number of records in a table match each filter;

summing, by the computer system, the selectivities of the filters;

determining, by the computer system, whether the cost of the user query is expected to be more than the query formed with the clause, combining the set of parallel subqueries by at least comparing the calculated computational costs of the filters in the subqueries to the user query;

where the prequeries include at least range scans against an index, and

there is at least a row limit to stop the range scan when it is determined that a particular filter is not selective;

where

the index includes at least a custom index, where the custom index accesses data belonging to a specified user from the database network that contains data belonging to a series of separate users, or

the index includes at least a form of accelerator table that is an extra indexed table that is added to the user query to give the user query a driving index; and

where the computer system includes a database network system that is a multi-tenant database system.