Methods and systems for joining indexes for query optimization in a multi-tenant database

• US 8,706,715 B2
• Filed: 09/21/2010
• Issued: 04/22/2014
• Est. Priority Date: 10/05/2009
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Eidson, William Charles, Collins, Jesse
• Primary Examiner(s): NGUYEN, PHONG H
• Application Number:
  US12/887,367
• Publication Number:
  US 20110082854A1
• Time in Patent Office: 1,309 Days
• Field of Search: 707/713, 707/714, 707/715, 707/741, 707/759
• US Class Current: 707/714
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries

Abstract

Methods and systems for query optimization for a multi-tenant database system are provided. Some embodiments comprise receiving at a network interface of a server in a multi-tenant database system an original query transmitted to the multi-tenant database system by a user associated with a tenant, wherein the original query is associated with data accessible by the tenant, and wherein the multi-tenant database system includes at least a first index and a second index. Metadata associated with the data is retrieved, wherein at least a portion of the data is stored in a common table within the multi-tenant database system. A tenant-selective query syntax is determined by analyzing at least one of metadata generated from information about the tenant or metadata generated from the data accessible by the tenant. An improved query is then generated using the query syntax, wherein the improved query is based at least in part upon the original query and a result of a join between a first number of rows associated with the first index and a second number of rows associated with the second index.

Claims

1. A computer-implemented method of improving a query, the method comprising:

receiving at a network interface of a server in a multi-tenant database system an original query transmitted to the multi-tenant database system by a user associated with a tenant, wherein the original query is associated with data accessible only by the tenant, and wherein the multi-tenant database system includes at least a first index and a second index, wherein the first index is a standard index and wherein the second index is a custom index to provide a private sharing paradigm within the multi-tenant database system that allows groups defined within one or more particular tenants to share information only among members of that group;

retrieving, using a processor of the server, metadata associated with the data accessible only by the tenant in the multi-tenant database system, wherein at least a portion of the data accessible only by the tenant is stored in a common table within the multi-tenant database system;

scanning a first index column to identify a first set of rows, wherein the first index column is selected based on the original query;

scanning a second index column to identify a second set of rows, wherein the second index column is based on the original query;

determining a third set of rows corresponding to an intersection of the first set of rows and the second set of rows;

determining, using the processor, a tenant-selective query syntax, wherein determining comprises analyzing at least one of metadata generated from information about the tenant or metadata generated from the data accessible by the tenant; and

generating, using the processor, an improved query using the query syntax, wherein the improved query is based upon the original query and the third set of rows.

2. The method of claim 1, further comprising:

receiving information identifying the user;

retrieving, using the processor, metadata about the user; and

wherein determining, using the processor, comprises analyzing at least one of the group consisting of metadata generated from information about the user, metadata generated from information about the tenant, and metadata generated from the data accessible by the tenant.

3. The method of claim 1, further comprising:

calculating selectivity for one or more columns of data accessible by the tenant; and

wherein determining, using a processor of the server, comprises analyzing the selectivity of the one or more columns of data accessible by the tenant.

4. The method of claim 1, wherein the improved query includes a reference to a denormalized table, wherein the denormalized table comprises data accessible by the tenant.

5. The method of claim 4, wherein the denormalized table comprises a search name lookup table.

6. The method of claim 4, wherein the denormalized table comprises at least one index on a custom data field associated with the tenant.

7. The method of claim 4, wherein the denormalized table comprises a custom foreign key column associated with the tenant.

8. The method of claim 1, wherein the first and second indices are both standard indices.

9. The method of claim 1, wherein the first and second indices are both standard b-tree indices stored in the common table.

10. The method of claim 1, wherein the first index is stored in the common table, and wherein the second index is stored in a separate indexed table different than the common table.

11. The method of claim 1, wherein the second number of rows associated with the second index is determined by joining a set of primary keys of the second index with a primary keys index of the common table.

12. A non-transitory computer-readable medium containing program code executable by a processor in a computer to improve a query in a multi-tenant database system, the program code including instructions to:

receiving at a network interface of a server in a multi-tenant database system an original query transmitted to the multi-tenant database system by a user associated with a tenant, wherein the original query is associated with data accessible only by the tenant, and wherein the multi-tenant database system includes at least a first index and a second index, wherein the first index is a standard index and wherein the second index is a custom index to provide a private sharing paradigm within the multi-tenant database system that allows groups defined within one or more particular tenants to share information only among members of that group;

retrieving, using a processor of the server, metadata associated with the data accessible only by the tenant in the multi-tenant database system, wherein at least a portion of the data accessible only by the tenant is stored in a common table within the multi-tenant database system;

scanning a first index column to identify a first set of rows, wherein the first index column is selected based on the original query;

scanning a second index column to identify a second set of rows, wherein the second index column is based on the original query;

determining a third set of rows corresponding to an intersection of the first set of rows and the second set of rows;

determining, using the processor, a tenant-selective query syntax, wherein determining comprises analyzing at least one of metadata generated from information about the tenant or metadata generated from the data accessible by the tenant; and

generating, using the processor, an improved query using the query syntax, wherein the improved query is based upon the original query and the third set of rows.

13. The computer-readable medium of claim 12, wherein the program code includes further instructions to:

receiving information identifying the user;

retrieving, using the processor, metadata about the user; and

wherein determining, using the processor, comprises analyzing at least one of the group consisting of metadata generated from information about the user, metadata generated from information about the tenant, and metadata generated from the data accessible by the tenant.

14. The computer-readable medium of claim 12, wherein the program code includes further instructions to:

calculating selectivity for one or more columns of data accessible by the tenant; and

wherein determining, using a processor of the server, comprises analyzing the selectivity of the one or more columns of data accessible by the tenant.

15. The computer-readable medium of claim 12, wherein the improved query includes a reference to a denormalized table, wherein the denormalized table comprises data accessible by the tenant.

16. The computer-readable medium of claim 15, wherein the denormalized table comprises a search name lookup table.

17. The computer-readable medium of claim 15, wherein the denormalized table comprises at least one index on a custom data field associated with the tenant.

18. The computer-readable medium of claim 15, wherein the denormalized table comprises a custom foreign key column associated with the tenant.

19. The computer-readable medium of claim 12, wherein the first and second indices are both standard indices.

20. The computer-readable medium of claim 12, wherein the first and second indices are both standard b-tree indices stored in the common table.

21. The computer-readable medium of claim 12, wherein the first index is stored in the common table, and wherein the second index is stored in a separate indexed table different than the common table.

22. The computer-readable medium of claim 12, wherein the second number of rows associated with the second index is determined by joining a set of primary keys of the second index with a primary keys index of the common table.

23. A system for improving a query in a multi-tenant database system, the system comprising:

a processor;

a network interface; and

a computer-readable medium tangibly embodied with instructions to;

receiving at a network interface of a server in a multi-tenant database system an original query transmitted to the multi-tenant database system by a user associated with a tenant, wherein the original query is associated with data accessible only by the tenant, and wherein the multi-tenant database system includes at least a first index and a second index, wherein the first index is a standard index and wherein the second index is a custom index to provide a private sharing paradigm within the multi-tenant database system that allows groups defined within one or more particular tenants to share information only among members of that group;

retrieving, using a processor of the server, metadata associated with the data accessible only by the tenant in the multi-tenant database system, wherein at least a portion of the data accessible only by the tenant is stored in a common table within the multi-tenant database system;

scanning a first index column to identify a first set of rows, wherein the first index column is selected based on the original query;

scanning a second index column to identify a second set of rows, wherein the second index column is based on the original query;

determining a third set of rows corresponding to an intersection of the first set of rows and the second set of rows;

determining, using the processor, a tenant-selective query syntax, wherein determining comprises analyzing at least one of metadata generated from information about the tenant or metadata generated from the data accessible by the tenant; and

generating, using the processor, an improved query using the query syntax, wherein the improved query is based upon the original query and the third set of rows.

24. The system of claim 23, wherein the computer-readable medium is tangibly embodied with further instructions to:

receiving information identifying the user;

retrieving, using the processor, metadata about the user; and

wherein determining, using the processor, comprises analyzing at least one of the group consisting of metadata generated from information about the user, metadata generated from information about the tenant, and metadata generated from the data accessible by the tenant.

25. The system of claim 23, wherein the computer-readable medium is tangibly embodied with further instructions to:

calculating selectivity for one or more columns of data accessible by the tenant; and

wherein determining, using a processor of the server, comprises analyzing the selectivity of the one or more columns of data accessible by the tenant.

26. The system of claim 23, wherein the improved query includes a reference to a denormalized table, wherein the denormalized table comprises data accessible by the tenant.

27. The system of claim 26, wherein the denormalized table comprises a search name lookup table.

28. The system of claim 26, wherein the denormalized table comprises at least one index on a custom data field associated with the tenant.

29. The system of claim 26, wherein the denormalized table comprises a custom foreign key column associated with the tenant.

30. The system of claim 23, wherein the first and second indices are both standard indices.

31. The system of claim 23, wherein the first and second indices are both standard b-tree indices stored in the common table.

32. The system of claim 23, wherein the first index is stored in the common table, and wherein the second index is stored in a separate indexed table different than the common table.

33. The system of claim 23, wherein the second number of rows associated with the second index is determined by joining a set of primary keys of the second index with a primary keys index of the common table.