Methods and systems for optimizing queries in a database system

• US 9,507,822 B2
• Filed: 04/23/2013
• Issued: 11/29/2016
• Est. Priority Date: 04/19/2010
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Weissman, Craig, Taylor, James
• Primary Examiner(s): CHANNAVAJJALA, SRIRAMA T
• Application Number:
  US13/868,746
• Publication Number:
  US 20130238595A1
• Time in Patent Office: 1,316 Days
• Field of Search: 707/705, 707713-715, 707/765, 707/769, 707/772, 707/779, 709/203, 709/206
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/242 Query formulation
• CPC Class Codes: G06F 16/2425 Iterative querying; Query formulation based on the results of a preceding query
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/256 in federated or virtual databases

Abstract

Methods and systems for optimizing queries in a multi-tenant store are described. In one embodiment, such a method includes retrieving data from a multi-tenant database system having a relational data store and a non-relational data store, receiving a request specifying data to be retrieved, retrieving one or more locations of the data to be retrieved, generating a database query based on the request, in which the database query specifies a plurality of data elements to be retrieved, the plurality of data elements including one or more data elements residing within the non-relational data store and one or more other data elements residing within the relational data store, generating an optimized database query having an optimized query syntax that is distinct from a query syntax of the database query, and executing the optimized database query against the multi-tenant database system to retrieve the data.

Claims

1. A method at a host organization for optimizing database queries in a database system of the host organization, the database system having one or more processors coupled with memory and including both a relational data store and a non-relational data store therein, the method comprising:

operating the database system within the host organization;

receiving a request at the host organization, the request specifying data for retrieval from the database system;

retrieving, based on the request received at the host organization, one or more locations of the data for retrieval;

generating, at the host organization, a database query based on the request, wherein the database query specifies a plurality of data elements for retrieval, the plurality of data elements including one or more data elements residing within the non-relational data store and one or more other data elements residing within the relational data store;

optimizing the database query to include at least a sub-query or a pre-query;

executing the optimized database query against the database system to retrieve the data;

wherein optimizing the database query comprises;

(i) identifying via a first sub-query to a table within relational data store, the first portion of the data for retrieval, (ii) identifying via a second sub-query to the non-relational data store, the second portion of the data for retrieval, (iii) identifying a data delta between the first sub-query that identifies the first portion of the data retrieved within the relational data store and the second sub-query that identifies the second portion of the data retrieved within the non-relational data store, and (iv) executing a third sub-query replicating missing data from the relational data store to the non-relational data store according to the data delta;

wherein the database query comprises a join operation performed by initiating non-relational database queries on the non-relational data store where one or more foreign key parents are stored in the relational data store; and

wherein the join operation comprises a plurality of sub-queries which are generated based on query optimizations available via an optimizer agent of the host organization, the query optimizations selected from the group comprising;

a specified ordering for the plurality of sub-queries;

a target data store for execution of a corresponding sub-query;

one or more pre-query assessments based on the data for retrieval;

a replication order from the relational data store to the non-relational data store; and

an in-memory join operation specifying at least one or more of the plurality of data elements for retrieval from each of the relational data store and the non-relational data store and placed into memory accessible to the optimizer agent and a corresponding sub-query to retrieve the at least one or more of the plurality of data elements from the memory accessible to the optimizer agent in fulfillment of the request.

2. The method of claim 1, wherein the database system further comprises elements of hardware and software that are shared by a plurality of separate and distinct customer organizations, each of the separate and distinct customer organizations being remotely located from a host organization having the database system executing therein.

3. The method of claim 1:

wherein the database query comprises a plurality of sub-queries;

wherein at least one of the plurality of sub-queries are directed toward retrieving the one or more data elements residing within the non-relational data store from the non-relational data store; and

wherein at least a second one of the plurality of sub-queries are directed toward retrieving the one or more other data elements residing within the relational data store from the relational data store.

4. The method of claim 1, wherein optimizing the database query comprises requesting a query policy without having to issue pre-queries such that analytical determinations are made and then stored and specified for one or more locations of data via a customer schema.

5. The method of claim 1, wherein the join operation further comprises:

the first sub-query executed against the non-relational data store, wherein the first sub-query identifies the one or more data elements residing within the non-relational data store;

the second sub-query executed against the relational data store, wherein the second sub-query determines the data delta between the first sub-query identifies the one or more data elements residing within the non-relational data store and the one or more other data elements residing within the relational data store;

the third sub-query executed against the relational data store and the non-relational data store, wherein the third sub-query replicates data corresponding to the determined data delta from the relational data store to the non-relational data store; and

the fourth sub-query executed against the non-relational data store, wherein the fourth sub-query fetches the data for retrieval from the non-relational data store by fetching both the one or more data elements residing within the non-relational data store and the one or more other data elements replicated from the relational data store to the non-relational data store and thus available from within the non-relational data store.

6. The method of claim 1, wherein the join operation is selected from the group comprising:

a join operation specifying two or more relation tables from the relational data store;

a join operation specifying at least one relation table from the relational data store and at least one or more data structures residing within the non-relational data store;

a join operation specifying two or more separate and distinct data structures residing within the non-relational data store, wherein each of the two or more separate and distinct data structures lack an overlapping shared key.

7. The method of claim 1:

wherein the database query comprises the plurality of sub-queries; and

wherein optimizing the database query further comprises;

retrieving the data utilizing the in-memory join operation into a query layer or an in memory join operation into a global caching layer, the in memory join operation being selected based on known statistics available from an optimizer agent.

8. The method of claim 1, wherein optimizing the database query further comprises:

identifying the first sub-query to the non-relational data store;

identifying the second sub-query to the relational data store, wherein the second sub-query comprises a data delta query to an append log of the relational data store for new or updated data elements within the scope of the first sub-query to the non-relational data store which are not yet flushed from the append log of the relational data store to the non-relational data store; and

executing a flush against the relational data store to flush the new or updated data elements within the append log of the relational data store to the non-relational data store.

9. The method of claim 1, wherein the relational data store comprises a relational database implemented in accordance with a relational database management system (RDBMS), wherein a plurality of relation tables of the relational database are inter-related to each other through one or more overlapping common characteristics for each of two or more relation tables within the relational database.

10. The method of claim 1, wherein the non-relational data store comprises a distributed structured database having a plurality of underlying hardware storage devices, each providing at least a portion of a total storage capacity for the non-relational data store, and wherein data elements within the non-relational data store are referenceable on the basis of a primary key and not on the basis of one or more overlapping common characteristics between two or more relation tables.

11. The method of claim 1:

wherein the non-relational data store comprises a plurality of distributed computing nodes, each computing node comprising at least a memory, one or more processors, and one or more communicatively interfaced hard disk drives, and wherein each of the distributed computing nodes comprise an isolated non-relational database instance having functionality to read, write, and update non-relational database transactions without authorization or control from a centralized transaction authority; and

wherein the relational data store comprises a monolithic relational database instance comprising memory and processors that coordinate computing resources with a centralized transaction authority that controls whether updates or changes to the monolithic relational database instance are committed to persistent storage upon persistent storage devices communicatively interfaced to, and controlled by, the monolithic relational database instance.

12. A non-transitory computer readable storage medium having instructions stored thereon that, when executed by processor in a host system, the instructions cause the host to perform operations comprising:

retrieving, based on the request via the host system, one or more locations of the data for retrieval;

generating, at the host system, a database query based on the request, wherein the database query specifies a plurality of data elements for retrieval, the plurality of data elements including one or more data elements residing within a non-relational data store and one or more other data elements residing within a relational data store;

optimizing the database query to include at least a sub-query or a pre-query;

executing the optimized database query against the database system to retrieve the data;

wherein optimizing the database query comprises;

(i) identifying via a first sub-query to a table within relational data store, the first portion of the data for retrieval, (ii) identifying via a second sub-query to the non-relational data store, the second portion of the data for retrieval, (iii) identifying a data delta between the first sub-query that identifies the first portion of the data retrieved within the relational data store and the second sub-query that identifies the second portion of the data retrieved within the non-relational data store, and (iv) executing a third sub-query replicating missing data from the relational data store to the non-relational data store according to the data delta;

wherein the database query comprises a join operation performed by initiating non-relational database queries on the non-relational data store where one or more foreign key parents are stored in the relational data store; and

wherein the join operation comprises a plurality of sub-queries which are generated based on query optimizations available via an optimizer agent of the host organization, the query optimizations selected from the group comprising;

a specified ordering for the plurality of sub-queries;

a target data store for execution of a corresponding sub-query;

one or more pre-query assessments based on the data for retrieval;

a replication order from the relational data store to the non-relational data store; and

an in-memory join operation specifying at least one or more of the plurality of data elements for retrieval from each of the relational data store and the non-relational data store and placed into memory accessible to the optimizer agent and a corresponding sub-query to retrieve the at least one or more of the plurality of data elements from the memory accessible to the optimizer agent in fulfillment of the request.

13. A system comprising:

a processor and a memory;

a communications interface to a database system having a relational data store and a non-relational data store implemented therein;

a request processor to receive a request at the host system for a database system, the request specifying data for retrieval from the database system;

a customer schema processor to retrieve, based on the request, one or more locations of the data for retrieval;

a query layer agent to generate a database query based on the request, wherein the database query specifies a plurality of data elements for retrieval, the plurality of data elements including one or more data elements residing within a non-relational data store and one or more other data elements residing within a relational data store;

a query optimizer to optimize the database query to include at least a sub-query or a pre-query;

wherein the query layer agent to execute the optimized database query against the database system to retrieve the data;

wherein the query optimizer to further;

(i) identify via a first sub-query to a table within relational data store, the first portion of the data for retrieval, (ii) identify via a second sub-query to the non-relational data store, the second portion of the data for retrieval, (iii) identify a data delta between the first sub-query that identifies the first portion of the data retrieved within the relational data store and the second sub-query that identifies the second portion of the data retrieved within the non-relational data store, and (iv) execute a third sub-query to replicate missing data from the relational data store to the non-relational data store according to the data delta;

wherein the database query comprises a join operation performed by initiating non-relational database queries on the non-relational data store where one or more foreign key parents are stored in the relational data store; and

wherein the join operation comprises a plurality of sub-queries which are generated based on query optimizations available via an optimizer agent of the host organization, the query optimizations selected from the group comprising;

a specified ordering for the plurality of sub-queries;

a target data store for execution of a corresponding sub-query;

one or more pre-query assessments based on the data for retrieval;

a replication order from the relational data store to the non-relational data store; and

an in-memory join operation specifying at least one or more of the plurality of data elements for retrieval from each of the relational data store and the non-relational data store and placed into memory accessible to the optimizer agent and a corresponding sub-query to retrieve the at least one or more of the plurality of data elements from the memory accessible to the optimizer agent in fulfillment of the request.

14. The system of claim 13, wherein the sub-query generator to generate the database query based on the request comprises the sub-query generator to generate a plurality of sub queries based on the request to fulfill the request, the sub-queries comprising:

the first sub-query executed against the non-relational data store, wherein the first sub-query identifies the one or more data elements residing within the non-relational data store;

the second sub-query executed against the relational data store, wherein the second sub-query determines a data delta between the first sub-query identifies the one or more data elements residing within the non-relational data store and the one or more other data elements residing within the relational data store;

the third sub-query executed against the relational data store and the non-relational data store, wherein the third sub-query replicates data corresponding to the determined data delta from the relational data store to the non-relational data store; and

a fourth sub-query executed against the non-relational data store, wherein the fourth sub-query fetches the data for retrieval from the non-relational data store by fetching both the one or more data elements residing within the non-relational data store and the one or more other data elements replicated from the relational data store to the non-relational data store and thus available from within the non-relational data store.

15. The system of claim 13:

wherein the database query comprises the plurality of sub-queries;

wherein at least one of the plurality of sub-queries are directed toward retrieving the one or more data elements residing within the non-relational data store from the non-relational data store; and

wherein at least a second one of the plurality of sub-queries are directed toward retrieving the one or more other data elements residing within the relational data store from the relational data store.

16. The system of claim 13, wherein the query optimizer is to request a query policy without having to issue pre-queries such that analytical determinations are made and then stored and specified for one or more locations of data via a customer schema.