METHOD OF IMPROVING A QUERY TO A DATABASE SYSTEM

• US 20070124276A1
• Filed: 11/10/2006
• Published: 05/31/2007
• Est. Priority Date: 09/23/2003
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Weissman, Craig, Wong, Simon, Moellenhoff, Dave
• Granted Patent: US 8,543,566 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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

In embodiments, methods and systems for improving a query in a database system are provided. These method and system embodiments can enable greater contextual knowledge about the types and use of data in tables underlying a relational database to be employed to improve query efficiency. By employing contextual information, embodiments can provide improved queries and/or make recommendations to a query optimizer of a database system to improve its operation based upon knowledge of the data and/or application gathered. Embodiments can be useful in improving query performance in multi-tenant database systems.

Claims

1. A method of improving a query in a database, the method comprising:

receiving a query directed to the database, the database storing data specific to each one of a plurality of tenants such that at least two of the tenants store at least a portion of data specific to the at least two tenants in a common table within the database and wherein each tenant is permitted access only to data associated with that tenant; and

providing, in place of the query, an improved query, the improved query determined based at least in part upon the query received and a set of contextual information, the contextual information describing a characteristic of the data specific to at least one of a plurality of tenants, thereby enabling constructing the improved query to be aware of the data specific to a tenant to which the improved query will be addressed.

2. The method of claim 1, wherein receiving a query directed to the database includes:

intercepting a query directed to an optimizer integrated with the database prior to the query reaching an optimizer integrated with the database.

3. The method of claim 1, wherein providing, in place of the query, an improved query includes:

selecting a set of contextual information applicable to the query from a plurality of sets of contextual information applicable to the plurality of tenants in the database.

4. The method of claim 3, wherein selecting a set of contextual information applicable to the query from a plurality of sets of contextual information applicable to the plurality of tenants in the database includes:

selecting at least one from a plurality of row level sharing rules that prevent a user associated with a particular tenant from seeing data in the database associated with the particular tenant to which the user is not permitted to access; and

creating the improved query so that the improved query indicates to a database how to search the data in the database that the user is permitted to search in a way that is likely to be improved over a way that the query received would have been searched in the database.

5. The method of claim 1, wherein providing, in place of the query, an improved query includes:

determining, based at least in part upon the query received and the set of contextual information, the improved query so that the improved indicates to a database how to search the data in the database in a way that is likely to be improved over a way that the query received would have been searched in the database.

6. The method of claim 1, wherein providing, in place of the query, an improved query includes:

determining, based at least in part upon the query received and the set of contextual information, the improved query, an improved query that includes at least one reference to a denormalized data structure, the denormalized structure permitting at least one of;

accessing names in the database stored in a name table, enabling customers to build indexes by copying denormalized field values into a universal indexed table, and using a “

reverse index”

to locate a foreign key from a parent to a child foreign key table.

7. The method of claim 1, wherein providing, in place of the query, an improved query, the improved query determined based at least in part upon the query received and a set of contextual information, the contextual information describing a characteristic of the data specific to one of the plurality of tenants includes:

improving the query received by rewriting or generating different SQL based at least in part upon at least one of a tenant-level sharing model, statistics and metadata.

8. The method of claim 7, wherein improving the query received by rewriting or generating different SQL based at least in part upon at least one of a tenant-level sharing model, statistics and metadata further includes:

determining a selectivity of a predicate filter on a column of a table based on only data for a single tenant.

9. The method of claim 8, wherein a characteristic of data for a single tenant defines a cardinality of a column only within a single tenant.

10. The method of claim 7, wherein improving the query received by rewriting or generating different SQL based at least in part upon at least one of a tenant-level sharing model, statistics and metadata includes:

copying values of an indexed column into a separate denormalized-indexed table and wherein the denormalized-indexed table is separately indexed natively by a relational database management system (RDBMS).

11. The method of claim 7, wherein improving the query received by rewriting or generating different SQL based at least in part upon a tenant-level sharing model, statistics and metadata includes:

determining whether to copy into the denormalized-indexed table is based at least in part on a tenant-specific criterion.

12. The method of claim 7, wherein improving the query received by rewriting or generating different SQL based at least in part upon a tenant-level sharing model, statistics and metadata includes:

rewriting or generating the improved query with an extra join in the denormalized-indexed table.

13. The method of claim 7, wherein improving the query received by rewriting or generating different SQL based at least in part upon a tenant-level sharing model, statistics and metadata includes:

determining whether to make an extra join to the denormalized-indexed tables is based on at least one of;

a set of tenant-level statistics, a set of cardinalities, a set of selectivities and metadata.

14. The method of claim 1, wherein providing, in place of the query, an improved query further includes:

rewriting or generating SQL of the received query to provide a hint in the improved query, wherein the hint instructs a relational database management system to lead the query with a table determined to be likely to produce improved query results when a user has access to only a small percentage subset of rows in a portion of the database associated with the tenant.

15. The method of claim 1, wherein providing, in place of the query, an improved query further includes:

rewriting or generating SQL of the received query to provide an improved query that instructs a relational database management system to perform a hash semi-join against a full set of rows that are visible to a user when the user is not an admin.

16. The method of claim 1, wherein providing, in place of the query, an improved query further includes:

rewriting or generating SQL of the received query to provide an improved query that leads with an entity id and performs a nested loop to the sharing table when the query leads with a small number of entity rows.

17. The method of claim 1, wherein providing, in place of the query, an improved query further includes:

providing the improved query to an optimizer integrated with the database in place of the query directed to the database.

18. The method of claim 1, wherein providing, in place of the query, an improved query further includes:

determining a number of rows that are accessible to a user, including at least one of;

(a) determining the number of accessible rows is limited to a search of a specific tenant;

(b) determining the number of accessible rows is limited to a search of a division (subset) of a tenant.

(c) accessing a sharing table that lists the users or user groups that may access the row, wherein sharing table is determined based on an ownership column associated with a row; and

(e) accessing a role hierarchy metadata table that lists the number of people below a user.

19. The method of claim 1, further comprising:

estimating whether a filter incorporated into the query is selective by performing a pre-fetch query, different from the query, wherein the pre-fetch query includes;

identifying a number of rows that match a filter; and

discontinuing the pre-fetch query and classifying the filter as non-selective when the number of rows exceeds a threshold limit.

20. A method for transmitting code to improve a query in a database over a machine accessible transmission medium, the method including:

transmitting code that causes one or more processors to receive a query directed to the database, the database storing data specific to each one of a plurality of tenants such that at least two of the tenants store at least a portion of data specific to the at least two tenants in a common table within the database; and

transmitting code that causes one or more processors to provide, in place of the query, an improved query, the improved query determined based at least in part upon the query received and a set of contextual information, the contextual information describing a characteristic of the data specific to at least one of a plurality of tenants, thereby enabling constructing the improved query to be aware of the data specific to a tenant to which the improved query will be addressed.