Methods and systems for optimizing queries in a multi-tenant store

• US 10,649,995 B2
• Filed: 11/04/2016
• Issued: 05/12/2020
• 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
• Application Number:
  US15/344,340
• Publication Number:
  US 20170116274A1
• Time in Patent Office: 1,285 Days
• 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 of optimizing database queries in a database system having a relational data store and a non-relational data store, the method comprising:

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

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 a first portion of the data residing within the non-relational data store and a second portion of the data residing within the relational data store;

optimizing the database query to include a join operation specifying a plurality of sub-queries to join the first portion of the data and the second portion of the data into a joined data set responsive to the request;

wherein optimizing the database query further includes;

(i) identifying a first sub-query to a table within the relational data store corresponding to the first portion of the data for retrieval, (ii) identifying a second sub-query to the non-relational data store corresponding to the second portion of the data for retrieval, (iii) replicating the table within the relational data store to the non-relational data store, and (iv) generating the optimized database query with one or more sub-queries to fetch both the first portion of the data for retrieval and the second portion of the data for retrieval from the non-relational data store;

wherein optimizing the database query by (iii) replicating the table within the relational data store to the non-relational data store further comprises optimizing the database query based on a policy to replicate a smaller dataset from its primary location to a location having the larger dataset in fulfillment of the replication; and

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

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 the policy is provided by an analytics engine executing via a processor and a memory of the database system, wherein the analytics engine provides the policy based on one of (i) previously performed database analytics or based on (ii) on-the-fly database analytics conducted via one or more sub-queries or pre-queries to perform the on-the-fly database analytics on behalf of the analytics engine.

5. The method of claim 1, 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 system, the query optimizations selected from the group comprising:

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;

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.

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

a first sub-query for execution 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;

a second sub-query for execution 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;

a third sub-query for execution 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 for execution 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.

7. 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.

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

a first sub-query for execution against the non-relational data store, wherein the first sub-query to retrieve the one or more data elements residing within the non-relational data store;

a second sub-query for execution against the relational data store, wherein the second sub-query determines a data delta between 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; and

a third sub-query for execution against the relational data store, wherein the third sub- query to retrieve the one or more other data elements residing within the relational data store based on the determined data delta.

9. The method of claim 1:

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

wherein optimizing the database query further comprises;

retrieving the data utilizing an 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.

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

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

identifying a 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.

11. 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.

12. 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.

13. 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.

14. The method of claim 1:

wherein an optimizer agent executing via a processor and a memory of the database system implements database query optimizations based on statistics and analytics stored within a global caching layer; and

wherein the global caching layer resides within the memory of the database system.

15. A system to optimize database queries for a database system,

wherein the system comprises:

a processor and a memory;

a communications interface to the database system, wherein the database system includes both 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 a first portion of the data residing within a non-relational data store and a second portion of the data residing within a relational data store;

a query optimizer to optimize the database query to include a join operation specifying a plurality of sub-queries to join the first portion of the data and the second portion of the data into a joined data set responsive to the request;

wherein the query optimizer is to further;

(i) identify a first sub-query to a table within the relational data store, corresponding to the first portion of the data for retrieval, (ii) identify a second sub-query to the non-relational data store corresponding to the second portion of the data for retrieval, (iii) replicate the table within the relational data store to the non-relational data store, and (iv) generate the optimized database query with one or more sub-queries to fetch both the first portion of the data for retrieval and the second portion of the data for retrieval from the non-relational data store; and

wherein the query optimizer to (iii) replicate the table within the relational data store to the non-relational data store comprises the query optimizer replicating the table based on a policy to replicate a smaller dataset from its primary location to a location having the larger dataset in fulfillment of the replication; and

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

16. The system of claim 15, 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:

a first sub-query to be 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;

a second sub-query for execution 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;

a third sub-query for execution 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 for execution 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.

17. The system of claim 15:

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.

18. The system of claim 15:

wherein the join operation comprises a plurality of sub-queries which are generated based on query optimizations available via the optimizer agent, 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;

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.

19. Non-transitory computer readable storage media having instructions stored thereupon that, when executed by a processor of a database system, the instructions cause the database system to optimize database queries for the database system by performing operations comprising:

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

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 a first portion of the data residing within the non- relational data store and a second portion of the data residing within the relational data store;

optimizing the database query to include a join operation specifying a plurality of sub-queries to join the first portion of the data and the second portion of the data into a joined data set responsive to the request;

wherein optimizing the database query further includes;

(i) identifying a first sub-query to a table within the relational data store corresponding to the first portion of the data for retrieval, (ii) identifying a second sub-query to the non-relational data store corresponding to the second portion of the data for retrieval, (iii) replicating the table within the relational data store to the non-relational data store, and (iv) generating the optimized database query with one or more sub-queries to fetch both the first portion of the data for retrieval and the second portion of the data for retrieval from the non-relational data store;

wherein optimizing the database query by (iii) replicating the table within the relational data store to the non-relational data store further comprises optimizing the database query based on a policy to replicate a smaller dataset from its primary location to a location having the larger dataset in fulfillment of the replication; and

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