METHODS AND SYSTEMS FOR PERFORMING CROSS STORE JOINS IN A MULTI-TENANT STORE

• US 20110258178A1
• Filed: 12/20/2010
• Published: 10/20/2011
• Est. Priority Date: 04/19/2010
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: EIDSON, BILL C., Oliver, Kevin, Weissman, Craig, Fell, Simon Z., Taylor, James, Schneider, Donovan A.
• Granted Patent: US 10,162,851 B2
• Time in Patent Office: Days
• US Class Current: 707/714
• CPC Class Codes: G06F 16/242 Query formulation
• CPC Class Codes: G06F 16/2455 Query execution

Abstract

Methods and systems for performing cross store joins 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 from the multi-tenant database system, retrieving, based on the request, 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, and executing the database query against the multi-tenant database system to retrieve the data.

Claims

1. A method of retrieving data from a multi-tenant 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 multi-tenant database system, the request specifying data to be retrieved from the multi-tenant database system;

retrieving, based on the request via the host system, one or more locations of the data to be retrieved;

generating, at the host system, a database query based on the request, wherein 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; and

executing the database query against the multi-tenant database system to retrieve the data.

2. The method of claim 1:

wherein a customer schema describes the one or more locations of data to be retrieved, the customer schema specifying each of the plurality of data elements of the data as residing within either the non-relational data store or residing within the relational data store, or as being available from both the non-relational data store and the relational data store; and

wherein the method further comprises retrieving, via the host system, the customer schema responsive to receiving the request.

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 executing the database query against the multi-tenant database system comprises referencing data elements stored in both the relational data store and the non-relational data store.

5. The method of claim 1, wherein the database query specifies a join operation.

6. The method of claim 5, 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:

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 to be retrieved;

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 to be retrieved 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.

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

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 to be 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;

a third sub-query to be 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 to be executed against the non-relational data store, wherein the fourth sub-query fetches the data to be retrieved 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.

8. The method of claim 5, 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.

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

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

10. The method of claim 9, wherein the third sub-query comprises one of:

a time-based sub-query to be executed against the relational data store, wherein the time-based sub-query specifies the one or more other data elements to be retrieved from the relational data store based one those data elements within the relational data store having a time stamp that is later than any timestamp corresponding to those data elements within the one or more data elements residing within the non-relational data store; and

a record identifier based sub-query to be executed against the relational data store, wherein the record identifier based sub-query specifies the one or more other data elements to be retrieved from the relational data store based one those data elements within the relational data store having a record identifier that is numerically greater than any record identifier corresponding to those data elements within the one or more data elements residing within the non-relational data store.

11. The method of claim 9, further comprising:

receiving new transactions at the multi-tenant database system, each new transaction specifying new data to be written to the non-relational data store;

writing the new data to an append log of the relational data store; and

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 comprises the third sub-query to retrieve the one or more other data elements residing within the relational data store from the append log of the relational data store.

12. The method of claim 11, further comprising flushing the new data written to the append log of the relational data store to the non-relational data store when the append log reaches a flush threshold.

13. The method of claim 1, wherein the one or more data elements residing within the non-relational data store comprise a plurality of compressed flat files or a plurality of binary files or a combination of the compressed flat files and the binary files.

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

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

16. The method of claim 1:

wherein the relational data store comprises a relational database implementation selected from the group comprising;

an Oracle compatible database implementation, an IBM DB2 Enterprise Server compatible relational database implementation, a MySQL compatible relational database implementation, and a Microsoft SQL Server compatible relational database implementation; and

wherein the non-relational data store comprises a NoSQL non-relational database implementation selected from the group comprising a Vampire compatible non-relational database implementation, an Apache Cassandra compatible non-relational database implementation, a BigTable compatible non-relational database implementation, and an HBase compatible non-relational database implementation.

17. The method of claim 1:

wherein receiving the request via an interface of the multi-tenant database system comprises receiving the request via a web-server of the multi-tenant database system, wherein the web-server provides a web-based interface to a remotely located end-user client machine originating the request; and

wherein the request comprises a request for services from the multi-tenant database system operating within a host organization for the multi-tenant database system.

18. The method of claim 1, wherein the multi-tenant 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 multi-tenant database system executing therein.

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

20. A non-transitory computer readable storage medium having instructions stored thereon that, when executed by processor in a host system, perform a method comprising:

receiving a request specifying data to be retrieved from a multi-tenant database system;

retrieving based on the request, one or more locations of the data to be retrieved;

generating a database query based on the request, wherein 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 a non-relational data store of the multi-tenant database system and one or more other data elements residing within a relational data store of the multi-tenant database system; and

executing the database query against the multi-tenant database system to retrieve the data.

21. The non-transitory computer readable storage medium of claim 20, wherein the database query specifies a join operation, the join operation 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 to be 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;

a third sub-query to be 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 to be executed against the non-relational data store, wherein the fourth sub-query fetches the data to be retrieved 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.

22. A system comprising:

a processor and a memory;

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

a request processor to receive a request specifying data to be retrieved from the multi-tenant database system;

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

a sub-query generator to generate a database query based on the request, wherein 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 of the multi-tenant database system and one or more other data elements residing within the relational data store of the multi-tenant database system; and

a query executor to execute the database query against the multi-tenant database system to retrieve the data.

23. The system of claim 22, 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 to be 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;

a third sub-query to be 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 to be executed against the non-relational data store, wherein the fourth sub-query fetches the data to be retrieved 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.