Static query optimization

• US 9,251,204 B2
• Filed: 06/23/2011
• Issued: 02/02/2016
• Est. Priority Date: 06/23/2010
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Collins, Jesse, Bathija, Jaikumar, O'Brien, John F.
• Primary Examiner(s): Allen, Brittany N
• Application Number:
  US13/167,498
• Publication Number:
  US 20110320435A1
• Time in Patent Office: 1,685 Days
• Field of Search: 707/718, 707/719
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries

Abstract

In some embodiments, a computer-implemented method for tuning queries for a multi-tenant database system is provided. A processor retrieves actual statistics associated with data stored on one or more servers in the multi-tenant database system. The data may be associated with one or more tenants of the multi-tenant database system. A subset of the actual statistics is selected, wherein the subset of the actual statistics is related to tenants having a data trait targeted for optimization. The processor determines synthetic statistics based on the subset of the actual statistics. An original query is received at the multi-tenant database system, wherein the original query operates upon data associated with a tenant that has the data trait targeted for optimization. The processor determines an optimal query plan based on the original query and synthetic statistics. Finally, the processor executes the original query based on the optimal query plan.

Claims

1. A computer-implemented method for tuning queries for a multi-tenant database system, the method comprising:

retrieving actual statistics associated with data stored on one or more servers in the multi-tenant database system, wherein the data is associated with one or more tenants of the multi-tenant database system;

selecting a subset of the actual statistics, wherein the subset of the actual statistics is related to tenants having a data trait targeted for optimization, wherein a tenant having a data trait targeted for optimization has at least one of the following data traits;

(1) a high volume of transactions, (2) a high number of transactions involving large file sizes, (3) a high number of resource-intensive transactions, (4) high utilization of a rarely-used column or table, or (5) high utilization of a rarely-used resource;

determining, using one or more processors associated with the one or more servers, synthetic statistics based on the subset of the actual statistics, wherein the synthetic statistics are derived from the subset of actual statistics by modifying one or more aspects of the data based on a subset of the tenants of the multi-tenant database system, the subset of tenants having the data trait targeted for optimization, and then re-calculating statistical data to generate the synthetic statistics;

receiving an original query transmitted to the multi-tenant database system by a user associated with a tenant that has the data trait targeted for optimization, wherein the original query operates upon data associated with the tenant; and

determining, using the processor, an optimal query plan based on the original query and the synthetic statistics.

2. The method of claim 1, wherein determining the optimal query plan comprises:

computing, using the one or more processors, a plurality of query plans; and

selecting the optimal query plan from the plurality of query plans.

3. The method of claim 1, wherein determining synthetic statistics comprises calculating an average value of a selected statistic in the subset of the actual statistics across one or more tenants having the data trait targeted for optimization;

and

wherein the optimal query plan is based upon the average value in place of a value of the selected statistic.

4. The method of claim 1, wherein determining synthetic statistics comprises determining the total number of tenants having the data trait targeted for optimization;

and

wherein the optimal query plan is based upon the total number of tenants having the data trait targeted for optimization in place of the total number of tenants in the multi-tenant database system.

5. The method of claim 1, wherein determining synthetic statistics comprises setting a pre-determined value for a selected statistic in the subset of the actual statistics;

and

wherein the optimal query plan is based upon the pre-determined value in place of a value of the selected statistic.

6. The method of claim 5, wherein the pre-determined value for the selected statistic is based upon an exemplary tenant having the data trait targeted for optimization, and wherein the exemplary tenant has the highest value for the selected statistic.

7. The method of claim 1, wherein the synthetic statistics comprise an average of statistical profiles for one or more tenants having the data trait targeted for optimization, and wherein a statistical profile for a tenant comprises one or more actual statistics associated with the tenant.

8. A computer-implemented method for executing optimized queries in a multi-tenant database system, the method comprising:

receiving an original query transmitted to one or more servers of the multi-tenant database system, wherein the original query operates upon data associated with a tenant of a plurality of tenants of the multi-tenant database system, wherein the tenant has a data trait targeted for optimization;

retrieving synthetic statistics, wherein the synthetic statistics are based on actual statistics associated with one or more tenants of the multi-tenant database system, and wherein the one or more tenants have the data trait targeted for optimization, wherein a tenant having a data trait targeted for optimization has at least one of the following data traits;

(1) a high volume of transactions, (2) a high number of transactions involving large file sizes, (3) a high number of resource-intensive transactions, (4) high utilization of a rarely-used column or table, or (5) high utilization of a rarely-used resource;

determining, using one or more processors associated with the one or more servers, synthetic statistics based on the subset of the actual statistics, wherein the synthetic statistics are derived from the subset of actual statistics by modifying one or more aspects of the data, and then re-calculating statistical data to generate the synthetic statistics based on a subset of the tenants of the multi-tenant database system, the subset of tenants having the data trait targeted for optimization;

executing, using the one or more processors, an optimal query plan based on the synthetic statistics.

9. The method of claim 8, wherein the synthetic statistics are uniformly configured across all database instances in the multi-tenant database system.

10. The method of claim 8, wherein determining the optimal query plan comprises:

computing, using the one or more processors, a plurality of query plans; and

selecting the optimal query plan from the plurality of query plans; and

wherein executing the original query based on the query plan comprises executing the original query based on the optimal query plan.

11. The method of claim 8, wherein the synthetic statistics comprise an average value of a selected statistic in the subset of the actual statistics across one or more tenants having the data trait targeted for optimization;

and

wherein the optimal query plan is based upon the average value in place of a value of the selected statistic.

12. The method of claim 8, wherein the synthetic statistics comprise the total number of tenants having the data trait targeted for optimization;

and

wherein the optimal query plan is based upon the total number of tenants having the data trait targeted for optimization in place of the total number of tenants in the multi-tenant database system.

13. The method of claim 8, wherein the synthetic statistics comprise a pre-determined value for a selected statistic in the subset of the actual statistics;

and

wherein the optimal query plan is based upon the pre-determined value in place of a value of the selected statistic.

14. The method of claim 13, wherein the pre-determined value for the selected statistic is based upon an exemplary tenant having the data trait targeted for optimization, and wherein the exemplary tenant has the highest value for the selected statistic.

15. The method of claim 13, wherein the pre-determined value for the selected statistic is based upon manually-configured settings.

16. The method of claim 8, wherein the synthetic statistics comprise an average of statistical profiles for one or more tenants having the data trait targeted for optimization, and wherein a statistical profile for a tenant comprises one or more actual statistics associated with the tenant.

17. A non-transitory computer-readable medium containing program code executable by a processor in a computer to tune a query, the program code including instructions to:

retrieve actual statistics associated with data stored on one or more servers in the multi-tenant database system, wherein the data is associated with one or more tenants of the multi-tenant database system;

select a subset of the actual statistics, wherein the subset of the actual statistics is related to tenants having a data trait targeted for optimization, wherein a tenant having a data trait targeted for optimization has at least one of the following data traits;

(1) a high volume of transactions, (2) a high number of transactions involving large file sizes, (3) a high number of resource-intensive transactions, (4) high utilization of a rarely-used column or table, or (5) high utilization of a rarely-used resource;

determine, using one or more processors associated with the one or more servers, synthetic statistics based on the subset of the actual statistics, wherein the synthetic statistics are derived from the subset of actual statistics by modifying one or more aspects of the data, and then re-calculating statistical data to generate the synthetic statistics based on a subset of the tenants of the multi-tenant database system, the subset of tenants having the data trait targeted for optimization;

receive an original query transmitted to the multi-tenant database system by a user associated with a tenant that has the data trait targeted for optimization, wherein the original query operates upon data associated with the tenant; and

generate, using the processor, an optimal query plan based on the original query and the synthetic statistics.

18. A system comprising:

one or more processors; and

a memory encoded with instructions to configure the one or more processors to;

retrieve actual statistics associated with data stored on one or more servers in the multi-tenant database system, wherein the data is associated with one or more tenants of the multi-tenant database system;

select a subset of the actual statistics, wherein the subset of the actual statistics is related to tenants having a data trait targeted for optimization, wherein a tenant having a data trait targeted for optimization has at least one of the following data traits;

(1) a high volume of transactions, (2) a high number of transactions involving large file sizes, (3) a high number of resource-intensive transactions, (4) high utilization of a rarely-used column or table, or (5) high utilization of a rarely-used resource;

determine, using one or more processors associated with the one or more servers, synthetic statistics based on the subset of the actual statistics, wherein the synthetic statistics are derived from the subset of actual statistics by modifying one or more aspects of the data, and then re-calculating statistical data to generate the synthetic statistics based on a subset of the tenants of the multi-tenant database system, the subset of tenants having the data trait targeted for optimization;

receive an original query transmitted to the multi-tenant database system by a user associated with a tenant that has the data trait targeted for optimization, wherein the original query operates upon data associated with the tenant;

generate, using the processor, an optimal query plan based on the original query and the synthetic statistics; and

execute the original query based on the optimal query plan.

19. The system of claim 18, wherein the synthetic statistics are uniformly configured across all database instances in the multi-tenant database system.