Methods and systems for determining candidates for a custom index in a multi-tenant database environment

• US 8,583,653 B2
• Filed: 12/17/2010
• Issued: 11/12/2013
• Est. Priority Date: 05/13/2010
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Collins, Jesse, Dutta, Arup
• Primary Examiner(s): Lee, Wilson
• Assistant Examiner(s): Le, Jessica N
• Application Number:
  US12/971,978
• Publication Number:
  US 20110282881A1
• Time in Patent Office: 1,061 Days
• Field of Search: None
• US Class Current: 707/741
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement

Abstract

Methods and systems are described for determining candidates for a custom index in a multi-tenant database environment. In one embodiment, a method includes, capturing a query that is directed to a multi-tenant database, determining whether the captured query is a candidate for an additional filter, determining operators used by the captured query if the query is a candidate, determining data types of the database used by the captured query if the query is a candidate, determining whether there is a current filter for the operator and data types used by the captured query if the query is a candidate, selecting the captured query based on the determined operators, data types, and the determined current filters, and generating a custom index for the selected query.

Claims

1. A method performed by a custom index recommender system, the method comprising:

capturing a query that is directed to a multi-tenant database;

determining whether the captured query is a candidate for a custom index by a query identification tool of the system;

determining operators used by the captured query if the query is a candidate;

determining data types of the database used by the captured query if the query is a candidate;

determining whether there is a current custom index for the operator and data types used by the captured query if the query is a candidate;

writing the captured query to a query table of custom index candidates of the system, the query table containing a plurality of queries that have been selected for a custom index, an identifier for each query, and filters used by each query;

selecting the captured query from the query table based on the determined operators, data types, and the determined current custom indexes; and

generating a new custom index for the selected query based on the determined operators, data types, and the determined custom indexes.

2. The method of claim 1, wherein capturing a query comprises intercepting a query generated by a database user to be applied to the database.

3. The method of claim 1, wherein capturing a query comprises monitoring the performance of user queries to the database and identifying a user query with slow performance for capture.

4. The method of claim 1, wherein determining whether the captured query is a candidate comprises determining a duration for the captured query to run.

5. The method of claim 4, further comprising:

associating the captured query with an organization;

determining an amount of data for the organization; and

scaling the determined duration based on the amount of data for the organization.

6. The method of claim 1, wherein determining whether the captured query is a candidate comprises determining whether the query times out before completion.

7. The method of claim 1, wherein determining whether the captured query is a candidate further comprises considering how frequently the captured query is run on the database.

8. The method of claim 1, wherein determining whether the captured query is a candidate comprises running the query against the database to test the selectivity of the filter of the captured query, developing a selectivity estimate for the captured query and comparing the selectivity estimate to selectivity estimates for other queries.

9. The method of claim 8, wherein running the query comprises running the query against a portion of the database.

10. The method of claim 1, wherein determining the operators comprises scanning the filter for additive and comparative operators.

11. The method of claim 1, wherein determining a data type comprises determining columns of the database used by the captured query.

12. The method of claim 11, wherein determining whether there is a current filter comprises determining whether a current filter relates to the determined columns.

13. The method of claim 1, further comprising determining a tenant for the captured query and wherein determining whether there is a current custom index for the operator further comprises determining whether there is a custom index for the operator, data types, and tenant of the captured query.

14. A non-transitory machine-readable medium carrying one or more sequences of instructions for validating queries in a multi-tenant database system, which instructions, when executed by one or more processors, cause the one or more processors to carry out operations comprising:

capturing a query that is directed to a multi-tenant database;

determining whether the captured query is a candidate for a custom index;

determining operators used by the captured query if the query is a candidate;

determining data types of the database used by the captured query if the query is a candidate;

determining whether there is a current custom index for the operator and data types used by the captured query if the query is a candidate;

writing the captured query to a query table of custom index candidates of the system, the query table containing a plurality of queries that have been selected for a custom index, an identifier for each query, and filters used by each query;

selecting the captured query from the query table based on the determined operators, data types, and the determined current filters; and

generating a new custom index for the selected query based on the determined operators, data types, and the determined custom indexes.

15. The non-transitory machine-readable medium as recited in claim 14, wherein the instructions further cause the one or more processors to carry out further operations comprising:

associating the captured query with an organization;

determining an amount of data for the organization; and

scaling the determined duration based on the amount of data for the organization.

16. The non-transitory machine-readable medium as recited in claim 14, wherein the instructions for carrying out the step of determining whether the captured query is a candidate include instructions for determining whether the instruction times out before completion.

17. The non-transitory machine-readable medium as recited in claim 14, wherein the instructions for carrying out the step of determining whether the captured query is a candidate include instructions for considering how frequently the captured query is run on the database.

18. A custom index recommender hardware system, the system comprising:

a processor; and

one or more stored sequences of instructions which, when executed by the processor, cause the processor to implement processes comprising;

a run-time query identifier to capture a query that is directed to a multi-tenant database and to determine whether the captured query is a candidate for a custom index;

a filter analyzer to determine operators used by the captured query if the query is a candidate, to determine data types of the database used by the captured query if the query is a candidate, to determine whether there is a current custom index for the operator and data types used by the captured query if the query is a candidate, and to write the captured query to a query table of custom index candidates of the apparatus, the query table containing a plurality of queries that have been selected for a custom index, an identifier for each query, and filters used by each query; and

a custom index generator to select the captured query based on the determined operators, data types, and the determined current filters, and to generate a custom index for the selected query based on the determined operators, data types, and the determined custom indexes.

19. The system as recited in claim 18, further comprising a selectivity tester to run the query against the database to test the selectivity of the filter of the captured query, to develop a selectivity estimate for the captured query and to compare the selectivity estimate to selectivity estimates for other queries.

20. The system as recited in claim 19, wherein the selectivity tester first runs the query against only a portion of the database.