Query optimization in a multi-tenant database system

• US 20050065925A1
• Filed: 09/23/2003
• Published: 03/24/2005
• Est. Priority Date: 09/23/2003
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Weissman, Craig, Nakada, Paul, Wong, Simon, Moellenhoff, Dave
• Granted Patent: US 7,529,728 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99939 Privileged access

Abstract

More efficient querying of a multi-tenant database using dynamic tuning of database indices. A layer of meta-data associates data items with tenants, e.g., via tags, and the meta-data is used to optimize searches by channeling processing resources during a query to only those pieces of data bearing the relevant tenant'"'"'s unique tag.

Claims

1. A method of optimizing a query in a multi-tenant database, said database having one or more data tables, each table having one or more logical columns defining data categories and one or more logical rows associated with one or more tenants, wherein a plurality of tenants have data stored in the data tables, the method comprising:

generating tenant-level statistics for each of said plurality of tenants for each of the data tables;

receiving a SQL query; and

optimizing the SQL query based on the tenant-level statistics.

2. The method of claim 1, wherein each tenant includes one or more associated users, the method further including:

generating user-level statistics for each user of each tenant for each of the data tables; and

optimizing the SQL query based on the user-level statistics.

3. The method of claim 2, wherein the user-level statistics are stored to a user metadata table.

4. The method of claim 2, wherein generating user-level statistics includes determining a total number of distinct rows for each of said plurality of users.

5. The method of claim 4, wherein the total number is an approximate number based on one or more of a) a number of rows viewable by the user and users below the user in a role hierarchy, b) a number of rows that are shared by a group to which the user belongs and c) a number of rows that are manually shared to the user by another user or group of users.

6. The method of claim 2, wherein generating user-level statistics for a user is performed according to one of a) on a scheduled basis, b) after a predetermined number of queries by the user, and c) each time an unconstrained query is run by the user.

7. The method of claim 1, wherein generating tenant-level statistics is performed on a periodic basis.

8. The method of claim 1, wherein generating includes determining a total number of distinct rows accessible for each of said plurality of tenants.

9. The method of claim 8, wherein the tenant-level statistics are stored to a tenant metadata table.

10. The method of claim 1, wherein at least one column of one of said tables includes data associated with two or more tenants.

11. A multi-tenant database system, comprising:

a database having one or more data tables, each table having one or more columns defining data categories and one or more rows associated with one or more tenants, wherein a plurality of tenants have data stored in the data tables;

a statistics generating module configured to generate tenant-level statistics for each tenant for each of the data tables; and

a query optimization module, configured to optimize a database query based on the tenant-level statistics.

12. The multi-tenant database system of claim 11, wherein each tenant includes one or more associated users, wherein the statistics generating module is further configured to generate user-level statistics for each user, and wherein the query optimization module is further configured to optimize the database query based on the user-level statistics.

13. The system of claim 12, further including a memory module, wherein the statistics generating module stores the user-level statistics to a metadata table in the memory module.

14. The system of claim 12, wherein the statistics generating module generates user-level statistics by determining a total number of distinct rows for each of said plurality of users.

15. The system of claim 14, wherein the total number is an approximate number based on one or more of a) a number of rows viewable by the user and users below the user in a role hierarchy, b) a number of rows that are shared by a group to which the user belongs and c) a number of rows that are manually shared to the user by another user or group of users.

16. The system of claim 12, wherein the statistics generating module generates user-level statistics for a user according to one of a) on a scheduled basis, b) after a predetermined number of queries by the user, and c) each time an unconstrained query is run by the user.

17. The system of claim 11, wherein the statistics generating module generates tenant-level statistics on a periodic basis.

18. The system of claim 11, wherein the statistics generating module generates tenant-level statistics by determining a total number of distinct rows viewable for each of said plurality of tenants.

19. The system of claim 18, further including a memory module, wherein the statistics generating module stores the tenant-level statistics to a tenant metadata table in the memory module.

20. The system of claim 11, wherein at least one column of one of said tables includes data associated with two or more tenants.

21. A method of optimizing a query in a multi-tenant database, said database having one or more data tables, each table having one or more logical columns defining data categories and one or more logical rows associated with one or more tenants, wherein a plurality of tenants have data stored in the data tables, and wherein each tenant includes one or more users, the method comprising:

processing the data tables so as to determine tenant-level statistics for each of said plurality of tenants;

processing the data tables so as to determine user-level statistics for each of said plurality of user;

receiving a SQL query; and

optimizing the SQL query based on one or both of the tenant-level statistics and the user-level statistics.

22. The method of claim 21, further including:

storing the user-level statistics to a user-level metadata table in a memory module; and

storing the tenant-level statistics to a tenant-level metadata table in the memory module.

23. The method of claim 21, wherein determining user-level statistics includes determining a total number of distinct rows for each of said plurality of users, and wherein determining tenant-level statistics includes determining a total number of distinct rows for each of said plurality of tenants.

24. The method of claim 21, wherein processing the data tables to determine tenant-level statistics is performed on a periodic basis.

25. The method of claim 21, wherein processing the data tables to determine user-level statistics for a user is performed according to one of a) on a scheduled basis, b) after a predetermined number of queries by the user, and c) each time an unconstrained query is run by the user.