Query optimization in a multi-tenant database system

• US 8,423,535 B2
• Filed: 04/15/2010
• Issued: 04/16/2013
• Est. Priority Date: 09/23/2003
• Status: Expired due to Term

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Weissman, Craig, Moellenhoff, Dave, Wong, Simon, Nakada, Paul
• Primary Examiner(s): PHAM, KHANH B
• Application Number:
  US12/760,975
• Publication Number:
  US 20100274779A1
• Time in Patent Office: 1,097 Days
• Field of Search: 707713-715, 707/718, 707/770
• US Class Current: 707/718
• 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

The present invention provides techniques for storing information on a multi-tenant database system to control query latency that includes a method that stores the information on the database among a plurality of tables arranged in columns and rows. For each of a subset of the plurality of tables, sets of the rows are distributed amongst different storage nodes on the database, with the set of rows stored at a common node having a common index value. Data storage and retrieval capabilities to the database are provided to allow access to the information, in response to requests from one of a plurality of remotely disposed computer systems. The retrieval capability includes a query condition that includes a query index value, with the query condition and the query index value being established to control retrieval latency. Also disclosed is a machine-readable medium carrying one or more sequences of instructions for storing information on a multi-tenant database system to control query latency when executed by one or more processors and cause the one or more processors to carry out steps of the method. A data center for storing information on a multi-tenant database system to control query latency is also disclosed that carries-out the functions of the method.

Claims

1. A method in a Multitenant Database System, the method comprising:

generating tenant-level statistics for each of a plurality of tenants having data stored within a database system of the Multitenant Database System, wherein the database system includes one or more data tables to store the data, each data table having one or more columns defining data categories and one or more rows associated with one or more tenants among the plurality of tenants having data stored within the data tables;

receiving communications from user systems over a network to request tenant-level data from the Multitenant Database System, the communications received at an interface of the Multitenant Database System;

generating one or more queries designed to access the information requested; and

optimizing the one or more queries based on the tenant-level statistics to increase system performance for an individual tenant among the plurality of tenants whose data is being searched.

2. The method of claim 1, further comprising:

generating user-level statistics for each of a plurality of users associated with each of the plurality of tenants; and

optimizing the one or more queries based on the user-level statistics in addition to optimizing the one or more queries based on the tenant-level statistics.

3. The method of claim 1, wherein optimizing the one or more queries based on the tenant-level statistics comprises tuning a query optimizer based on particular data characteristics of the tenant whose data is being searched and based on a particular query to be executed.

4. The method of claim 1, wherein generating the tenant-level statistics for each of a plurality of tenants comprises tracking the tenant-level statistics in addition to system-level statistics.

5. The method of claim 4, wherein the system-level statistics are aggregate across many tenants among the plurality of tenants having data stored within the data tables.

6. The method of claim 1:

wherein a statistics generating module generates the tenant-level statistics; and

wherein a query optimization module optimizes the one or more queries based on the tenant-level statistics.

7. The method of claim 1, wherein optimizing the one or more queries based on the tenant-level statistics comprises deciding which of the one or more data tables to retrieve first.

8. The method of claim 1, wherein optimizing the one or more queries based on the tenant-level statistics comprises deciding which side of a Many-to-Many relationship table to enter first, wherein the Many-to-Many relationship table is accessible from both an entity side and from a user side.

9. The method of claim 1, wherein optimizing the one or more queries based on the tenant-level statistics comprises programmatically configuring a query optimizer by supplying hints to the query optimizer to alter the behavior of the query optimizer.

10. The method of claim 1, further comprising storing the tenant-level statistics on a per-tenant basis in tenant database storage areas of the Multitenant Database System.

11. The method of claim 1, wherein the Multitenant Database System includes a tenant database divided into individual tenant storage areas via a physical arrangement or a logical arrangement, and wherein the individual tenant storage areas comprise user storage allocated for each respective user.

12. The method of claim 1, wherein optimizing the one or more queries based on the tenant-level statistics comprises making choices about query access paths for list style queries to generate a report.

13. The method of claim 1, wherein optimizing the one or more queries based on the tenant-level statistics comprises choosing a filter which is most selective for fields that contain enumerated lists of values.

14. The method of claim 1, wherein optimizing the one or more queries based on the tenant-level statistics comprises choosing between two different query paths based on a count of a number of rows to which a user has visibility.

15. The method of claim 1, further comprising:

reading, via an optimization engine, data from multi-tenant data tables;

storing metadata into tenant-level tables; and

wherein optimizing the one or more queries based on the tenant-level statistics comprises retrieving and processing the tenant-level tables.

16. The method of claim 1, wherein optimizing the one or more queries based on the tenant-level statistics comprises:

evaluating a each of a plurality of filters for expected selectiveness; and

choosing a most selective filter.

17. The method of claim 16, wherein the expected selectiveness of a filter is based on the filter being restricted to matching data within specified a period of time.

18. The method of claim 1, wherein optimizing the one or more queries based on the tenant-level statistics comprises instructing an optimizer to begin with a sharing filter for a user, the sharing filter being limited to visibility for the user.

19. The method of claim 1:

wherein an overall database structure or schema for the database system is fixed; and

wherein each of the plurality of tenants having data stored within the data tables comprises a tenant-specific virtual schema that describes the logical structure of the respective tenant'"'"'s data stored within the data tables.

20. The method of claim 19:

wherein the tenant-specific virtual schema comprises a plurality of customizable fields, each of the plurality of customizable fields being indexable per designation; and

wherein the tenant-level statistics track a total number of distinct values for indexed columns.

21. A non-transitory medium storing program code that, when executed by a central processing unit of a Multitenant Database System, the program code causes the Multitenant Database System to perform operations including:

generating tenant-level statistics for each of a plurality of tenants having data stored within a database system of the Multitenant Database System, wherein the database system includes one or more data tables to store the data, each data table having one or more columns defining data categories and one or more rows associated with one or more tenants among the plurality of tenants having data stored within the data tables;

receiving communications from user systems over a network to request tenant-level data from the Multitenant Database System, the communications received at an interface of the Multitenant Database System;

generating one or more queries designed to access the information requested; and

optimizing the one or more queries based on the tenant-level statistics to increase system performance for an individual tenant among the plurality of tenants whose data is being searched.

22. A Multitenant Database System, comprising:

a database system including one or more data tables to store data for a plurality of tenants, each data table having one or more columns defining data categories and one or more rows associated with one or more tenants among the plurality of tenants having data stored within the data tables;

a statistics generating module to generate tenant-level statistics for each of the plurality of tenants having data stored within the database system of the Multitenant Database System;

an interface to receive communications from user systems over a network requesting tenant-level data from the Multitenant Database System via one or more queries designed to access the information requested; and

a query optimization module to execute in process space of the Multitenant Database System via a central processing unit, wherein the query optimization module is to optimize the one or more queries based on the tenant-level statistics to increase system performance for an individual tenant among the plurality of tenants whose data is being searched.