System and methods of improving a multi-tenant database query using contextual knowledge about non-homogeneously distributed tenant data

• US 8,543,566 B2
• Filed: 11/10/2006
• Issued: 09/24/2013
• Est. Priority Date: 09/23/2003
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Weissman, Craig, Moellenhoff, Dave, Wong, Simon
• Primary Examiner(s): Pham, Hung Q
• Assistant Examiner(s): CHEUNG, HUBERT G
• Application Number:
  US11/558,761
• Publication Number:
  US 20070124276A1
• Time in Patent Office: 2,510 Days
• Field of Search: 707/715
• US Class Current: 707/713
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24575 using context
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries

Abstract

A query optimizing system and methods employ contextual knowledge about the types and use of data and/or applications in tables underlying a relational database to provide improved queries and/or make recommendations to a query optimizer of a database based upon knowledge of the data and/or application gathered. A multi-tenant database, in which querying is conducted on multiple tenant data stored in a single table, provides for determining tenant-level statistics, data sharing, user/tenant views, user-level access/capacities, custom entities, custom fields and/or other contextual information about users and tenants, and for providing query optimization and/or query optimizer recommendations corresponding to such information.

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 one or more 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 requested tenant-level data;

optimizing the generated one or more queries based on the generated tenant-level statistics to increase system performance for an individual tenant among the plurality of tenants whose data is being searched and based further on contextual information having data specific to the individual tenant among the plurality of tenants, wherein the contextual information describes distribution of the individual tenant'"'"'s data as stored within the database system.

2. The method of claim 1:

wherein the database system of the Multitenant Database System comprises a Relational Database Management System (RDBMS); and

wherein the method further comprises intercepting the generated one or more queries prior to reaching the RDBMS.

3. The method of claim 1, wherein the contextual information further describes:

permission for the individual tenant to access specific data; and

permission for the individual tenant to perform specific operations within the Multitenant Database System.

4. 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 one or more data tables comprises a tenant-specific virtual schema that describes a logical structure of the respective tenant'"'"'s data stored within the one or more data tables.

5. The method of claim 4:

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 generated tenant-level statistics track a total number of distinct values for indexed columns.

6. The method of claim 4:

wherein the optimized generated one or more queries are custom entity aware and custom field aware to meet the requirements of the individual tenant having created one or more custom entities or one or more custom fields within the database system.

7. The method of claim 1, wherein the contextual information further describes characteristics of the individual tenant'"'"'s data as stored within the database system including:

a length of records and a corresponding quantity of indexable fields for the records.

8. The method of claim 1, wherein the optimizing the generated one or more queries comprises:

reducing an amount of data which must be read from disk to satisfy the generated one or more queries based on a selectivity of tables or columns which yield a fewest quantity of the one or more rows.

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

optimizing the generated one or more queries based on a number of distinct values for the individual tenant'"'"'s data within a shared column being less than a threshold, the shared column having data for other tenants among the plurality of tenants in addition to the individual tenant'"'"'s data.

10. The method of claim 1, wherein an optimizer for the database system provides native statistics which are aggregated across the plurality of tenants but lack the contextual information for the individual tenant'"'"'s data as stored within the database system.

11. The method of claim 1, wherein the optimizing the generated one or more queries based on the contextual information for the individual tenant'"'"'s data as stored within the database system comprises:

optimizing the generated one or more queries based on a field for the individual tenant having an expected non-null value in all cases for the individual tenant, wherein the same field is null as to one or more other tenants among the plurality of tenants.

12. The method of claim 11, the optimizing the generated one or more queries based on the field for the individual tenant having the expected non-null value in all cases for the individual tenant comprises applying a filter to the field so that the optimized generated one or more queries account for the expected non-null value.

13. The method of claim 1, wherein the optimizing the generated one or more queries based on the contextual information for the individual tenant'"'"'s data as stored within the database system comprises:

optimizing the generated one or more queries based on a number of rows that are accessible by the individual tenant; and

wherein the method further comprises calculating the number of rows that are accessible by the individual tenant based on ownership data for the one or more rows.

14. The method of claim 13, wherein the optimizing the generated one or more queries based on the number of rows that are accessible by the individual tenant comprises:

(a) structuring the optimized generated one or more queries to retrieve all of the data in the one or more rows that are accessible by the individual tenant; and

(b) applying filters to the retrieved data.

15. The method of claim 1, further comprising:

tracking a total number of the one or more rows for each entity type for each of the plurality of tenants of the Multitenant Database System; and

tracking a percentage of the one or more rows that each and every user of the Multitenant Database System has access to as metadata.

16. The method of claim 1:

wherein the method further comprises partitioning the individual tenant into multiple sub-tenants; and

wherein the optimizing the generated one or more queries based on the contextual information for the individual tenant'"'"'s data as stored within the database system comprises pushing a predicate into a query improver which optimizes the generated one or more queries, wherein the predicate causes filtering according to the partitioning of the individual tenant into the multiple sub-tenants.

17. The method of claim 1:

wherein the method further comprises splitting an entity table for the individual tenant into multiple divisions tracked via an index on a physical division column; and

wherein the optimizing the generated one or more queries based on the contextual information for the individual tenant'"'"'s data as stored within the database system comprises filtering based on one division among the multiple divisions to reduce searching to only the one or more rows of the one division.

18. The method of claim 1, wherein the optimizing the generated one or more queries comprises:

selecting a column among a plurality of columns for which a highest cardinality is determined based on a selectivity of filters used on the plurality of columns; and

optimizing the generated one or more queries so that the selected column for the highest cardinality leads the generated one or more queries.

19. The method of claim 1, wherein the optimizing the generated one or more queries comprises using a reverse index to locate a foreign key from a parent to a child foreign key table by referencing a universal indexed table having denormalized field values therein.

20. The method of claim 1, wherein the optimizing the generated one or more queries comprises combining a parallel list of “

OR”

equality conditions on one field into a single “

IN”

condition.

21. The method of claim 1, wherein the optimizing the generated one or more queries comprises introducing a single filter to the optimized generated one or more queries to replace a parallel set of “

AND”

conditions of the generated one or more queries.

22. The method of claim 1, wherein the optimizing the generated one or more queries comprises leading the optimized generated one or more queries with reference to sharing tables for the individual tenant and accessing a queried entity via an indexed owner field of the queried entity.

23. The method of claim 1, wherein the optimizing the generated one or more queries comprises introducing into the optimized generated one or more queries a hash semi-join against a full set of the one or more rows accessible to the individual tenant.

24. The method of claim 1, wherein the optimizing the generated one or more queries based on the contextual information for the individual tenant'"'"'s data as stored within the database system comprises:

introducing a pre-fetch query into the optimized generated one or more queries, wherein the pre-fetch query requests a number of the one or more rows matching a filter specified in the generated one or more queries.

25. The method of claim 24, wherein the introducing the pre-fetch query further includes using a row number limit to trigger an early exit of the pre-fetch query.

26. The method of claim 1, wherein the optimizing the generated one or more queries based on the contextual information for the individual tenant'"'"'s data as stored within the database system comprises:

introducing a pre-fetch query into the optimized generated one or more queries, wherein the pre-fetch query determines a number of entries required for each of multiple viable retrieval paths; and

removing one or more of the multiple viable retrieval paths based on the number of entries required as determined by the pre-fetch query.

27. The method of claim 1, wherein the optimizing the generated one or more queries comprises:

limiting the optimized generated one or more queries to a reduced number of the one or more rows to be displayed at a time via a User Interface (UI) when the generated one or more queries are UI queries.

28. The method of claim 1, wherein the optimizing the generated one or more queries based on the contextual information for the individual tenant'"'"'s data as stored within the database system comprises:

determining that a join operation of the generated one or more queries is deferrable until after a row number limit of the generated one or more queries and deferring the join operation in the optimized generated one or more queries.

29. 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 one or more 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 requested tenant-level data;

optimizing the generated one or more queries based on the generated tenant-level statistics to increase system performance for an individual tenant among the plurality of tenants whose data is being searched and based further on contextual information having data specific to the individual tenant among the plurality of tenants, wherein the contextual information describes distribution of the individual tenant'"'"'s data as stored within the database system.

30. 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 one or more 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 requested tenant-level data; and

a query optimization module to optimize the one or more queries based on the generated tenant-level statistics for an individual tenant among the plurality of tenants whose data is being searched and based further on contextual information having data specific to the individual tenant among the plurality of tenants, wherein the contextual information describes distribution of the individual tenant'"'"'s data as stored within the database system.