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

• US 9,965,511 B2
• Filed: 02/12/2014
• Issued: 05/08/2018
• 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): Nguyen, Thu Nga
• Application Number:
  US14/179,155
• Publication Number:
  US 20140164357A1
• Time in Patent Office: 1,546 Days
• Field of Search: None
• 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 non-transitory computer readable medium having stored thereon instructions that, when executed, are configurable to cause one or more processors to:

receive a user database query in a structured query language with the one or more processors;

parse the user database query and automatically generate, with the one or more processors, a set of parallel database sub queries that in combination are equivalent to the user database query in results that are expected to be returned, wherein individual database sub queries in the set of parallel database sub queries are compared against other optimizable filters against the user database query;

perform one or more runtime prequeries to gather optimization information for a selected tenant of a multitenant environment corresponding to the user database query;

optimize each database sub query based on the lowest calculated cost of data access, wherein each database sub query is fully optimized utilizing a database query optimizer;

execute, with the one or more processors, the set of parallel database sub queries against multiple database tables, if a cost of data access of the user database query is expected to be more than a cost of data access of a new database query formed by combining the returned results of the set of parallel database sub queries, the forming of the new database query being accomplished by at least forming a clause that combines the set of parallel database sub queries into a database query equivalent to the user database query; and

return, with the one or more processors, results of the new database query.

2. The non-transitory computer readable medium of claim 1 where the clause includes at least a UNION ALL clause.

3. The non-transitory computer readable medium of claim 1 where the parsing of the user database query determines one or more OR clauses to be within the user database query.

4. The non-transitory computer readable medium of claim 1, further comprising:

generating prequeries that are a series of database queries that are run to determine an estimate of a cost of data access with each of the parallel database subqueries;

determining if the cost of data access of the user database query is expected to be more than the database query formed with the clause combining the set of parallel database subqueries by at least comparing a set of calculated computational costs of data access of filters in the subqueries to the user database query.

5. The non-transitory computer readable medium of claim 4, the cost of data access of the database query formed with the clause combining the set of parallel database subqueries being determined by calculating computational costs based on a selectivity of the filters for each of the database subqueries, the selectivity of the filters being determined by a count of how many records are selected by applying the filter.

6. The non-transitory computer readable medium of claim 5 where the calculating of the computational costs are based on a sum of selectivities of the filters for each of the database subqueries.

7. The non-transitory computer readable medium of claim 5 where selectivity of a filter is a measure of a number of rows matching each filter as a fraction of a total number of rows that a user has in a table.

8. The non-transitory computer readable medium of claim 4 where the prequeries include at least range scans against an index.

9. The non-transitory computer readable medium of claim 8 where the prequeries include at least a row limit to stop the range scan when it is determined that a particular filter is not selective.

10. The non-transitory computer readable medium of claim 8 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.

11. The non-transitory computer readable medium of claim 8 where the index includes at least a form of accelerator table that is an extra indexed table that is added to the user database query to give the user database query a driving index.

12. The non-transitory computer readable medium of claim 1 further comprising:

optimizing each database subquery with a query optimizer based on the lowest calculated cost.

13. The non-transitory computer readable medium of claim 1 where the computer system includes a database network system that is a multi-tenant database system.

14. The non-transitory computer readable medium of claim 1, further comprising:

determining if the cost of data access of the user database query is expected to be more than the database query formed with the clause combining the set of parallel database subqueries by at least comparing the calculated computational costs of the filters in the database subqueries to the user database query;

the cost of data access of the database query formed with the clause combining the set of parallel database subqueries being determined by calculating computational costs based on a selectivity of the filters for each of the database subqueries, the selectivity of the filters being determined by a count of how many records by applying the filter or as a measure of a number of rows matching each filter as a fraction of a total number of rows that a user has in a table;

where the parsing of the user database query determines one or more OR clauses to be within 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 database query to give the user database query a driving index;

where the calculated computational costs are based on the sum of the determined selectivities of the filters for each of the database subqueries; and

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

15. A method comprising:

receive a user database query in a structured query language with the one or more processors;

the processor system parsing the user database query and automatically generate a set of parallel database sub queries that in combination are equivalent to the user database query in results that are expected to be returned, wherein individual database sub queries in the set of parallel database sub queries are compared against other optimizable filters against the user database query;

the processor system performing one or more runtime prequeries to gather optimization information for a selected tenant of a multitenant environment corresponding to the user database query;

the processor system optimizing each database sub query based on the lowest calculated cost of data access, wherein each database sub query is fully optimized utilizing a database query optimizer;

the processor system executing the set of parallel database sub queries against multiple database tables, if a cost of data access of the user database query is expected to be more than a cost of data access of a new database query formed by combining the returned results of the set of parallel database sub queries, the forming of the new database query being accomplished by at least forming a clause that combines the set of parallel database sub queries into a database query equivalent to the user database query; and

the processor system returning results of the new database query.

17. The method of claim 15, further comprising:

determining if the cost of data access of the user database query is expected to be more than the query formed with the clause combining the set of parallel database subqueries by at least comparing the calculated computational costs of the filters in the subqueries to the user database query;

the cost of data access of the query formed with the clause combining the set of parallel database subqueries being determined by calculating computational costs based on a selectivity of the filters for each of the database subqueries, the selectivity of the filters being determined by a count of how many records by applying the filter or as a measure of a number of rows matching each filter as a fraction of a total number of rows that a user has in a table;

where the parsing of the user database query determines one or more OR clauses to be within the user database 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;

where the calculated computational costs are based on the sum of the determined selectivities of the filters for each of the database subqueries.

19. The method of claim 15 where the calculating of the computational costs are based on a sum of selectivities of the filters for each of the database subqueries.

20. The method of claim 15 where the prequeries include at least range scans against an index.

16. A system having one or more hardware computing devices, each having one or more processors and associated memory, configurable for optimizing queries in a database system, the system comprising:

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 database user query at the computer system;

the system parsing the user database query and automatically generating a set of parallel database sub queries that in combination are equivalent to the user database query in results that are expected to be returned, wherein the individual database sub queries in the set of parallel database sub queries are compared against other optimizable filters against the user database query;

the system performing one or more runtime prequeries to gather optimization information for a selected tenant of a multitenant environment corresponding to the user database query;

the system optimizing each database sub query based on the lowest calculated cost of data access, wherein each database sub query is fully optimized utilizing a query optimizer;

the system forming a database query that is applied to multiple database tables, if a cost of data access of the user database query is expected to be more than the database query formed, optimizing each database subquery based on the lowest calculated cost of data access, the forming of the database query being by at least forming a clause that combines the set of parallel database subqueries into a database query equivalent to the user database query.

18. The system of claim 16, wherein the computer system is further configured to:

generate prequeries that are a series of database queries that are run to determine an estimate of a cost with each of the parallel database subqueries;

determine if the cost of the user database query is expected to be more than the database query formed with the clause combining the set of parallel database subqueries by at least comparing the calculated computational costs of the filters in the database subqueries to the user database query;

the cost of the database query formed with the clause combining the set of parallel database subqueries being determined by calculating computational costs based on a selectivity of the filters for each of the database subqueries, the selectivity of the filters being determined by a count of how many records by applying the filter or as a measure of a number of rows matching each filter as a fraction of a total number of rows that a user has in a table;

where the parsing of the user database query determines one or more OR clauses to be within the user database 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;

where the calculated computational costs are based on the sum of the determined selectivities of the filters for each of the database subqueries.