METHOD AND APPARATUS FOR DATABASE

• US 20150088844A1
• Filed: 03/01/2013
• Published: 03/26/2015
• Est. Priority Date: 04/30/2012
• Status: Active Grant

• Current Assignee: MongoDB, Inc.
• Original Assignee: Tightdb, Inc. (MongoDB, Inc.)
• Inventors: Stigsen, Alexander, Christiansen, Bjarne, Reinhold, Lasse
• Granted Patent: US 9,811,548 B2
• Time in Patent Office: Days
• US Class Current: 707/703
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 8/30 Creation or generation of source code

Abstract

A method for representing a database in a computer readable medium. Accessing a first table in the database. The first table has rows of data, each row of data having one or more columns. Storing a first representation of the first table in a volatile computer memory in a column-oriented format, the column-oriented format comprising at least one B-tree for at least one column, wherein the B-tree is composed of at least one array and the at least one B-tree includes references to a plurality of arrays, each array of the plurality of arrays comprised of data corresponding to the rows of one column of the table, wherein the storing further comprising storing data corresponding to the rows in a packed format. Storing a second representation of the database on the computer-readable medium, the second representation substantially identical to the first representation.

Claims

1. A system for providing services to a plurality of users, the system comprised of:

a nonvolatile storage, the nonvolatile storage including a plurality of databases, each database in the plurality of databases corresponding to a single entity;

a computer, the computer including a volatile memory and a controller;

a communications network, the communications network coupling the storage and the computer in communication; and

wherein the controller for performing;

receiving a signal over the communications network, the signal comprising a request for data relating to a first entity;

retrieving a database from the plurality of databases in the nonvolatile storage into the memory over the communications network, the database comprising a database for the first entity; and

performing at least one operation on the database in the volatile memory; and

generating a second signal for transmission over the communications network, the second signal responsive to the request for data.

2. The system of claim 1, wherein the database represented as a packed, column-oriented storage of data in a B-tree structure that is recursively composed of a plurality of arrays.

3. The system of claim 1, wherein the controller further for storing the database in the storage after the generating.

4. The system of claim 1, wherein the at least one operation selected from the set of (i) creation of at least one new record in the database, (ii) retrieval of at least one record in the database, (iii) update of at least one record in the database, and (iv) deletion of at least one record in the database.

5. The system of claim 1, wherein the database represented as a packed, column-oriented storage of data in a B-tree structure that is recursively composed of a plurality of adaptive arrays.

6. The system of claim 1, wherein the storage comprised of a cloud based storage solution provided by a first company and wherein the computer comprising a cloud based processing solution provided by a second company.

7. The system of claim 6, wherein the first company and the second company different entities.

8. The system of claim 6, wherein the cloud based storage solution selected from the set comprising:

(i) Amazon S3, (ii) Rackspace Cloud Files, (iii) Microsoft Windows Azure, (iv) Google App Engine, (v) Amazon Dynamo, (vi) a cloud based key-value store with each value corresponding to a database, (vii) a cloud delivered Riak database, (vii) a cloud delivered Couchbase database, and (viii) a cloud based file store with each file corresponding to a database.

9. The system of claim 6, wherein the cloud based processing solution selected from the set comprising:

(i) Amazon EC2, (ii) GoGrid GoGrid, (iii) Microsoft Windows Azure, (iv) Rackspace Cloud Server, (v) Salesforce'"'"'s Heroku and (vi) a cloud based computing resource delivery service.

10. A system for providing services to a plurality of users, the system comprised of:

a computer, the computer including a volatile memory and a controller;

a communications network, the communications network coupling the computer in communication with resources; and

wherein the controller for performing;

receiving a first signal over the communications network from a second computer, the first signal comprising a request for data relating to a first entity;

transmitting a second signal over the communications network to a third computer, the second signal comprising a request for a database;

receiving a third signal from the third computer, the third signal comprising a database;

loading the database into the volatile memory in a first representation that is substantially identical to the format to a second representation of the database in the third signal;

performing at least one operation on the database in the volatile memory; and

generating a third signal for transmission over the communications network to the second computer, the third signal responsive to the request for data.

11. The system of claim 10, wherein, the first representation does not include any deserialization or unboxing of the second representation.

12. The system of claim 10, wherein the database represented as a packed, column-oriented storage of data in a B-tree structure that is recursively composed of a plurality of arrays.

13. A method for representing a database in a computer readable medium, the method comprising:

accessing a first table in the database, the first table having a plurality of rows of data, each row of data having one or more columns;

storing a first representation of the first table in a volatile computer memory in a column-oriented format, the column-oriented format comprising at least one B-tree for at least one column, wherein the B-tree is composed of at least one array and the at least one B-tree includes references to a plurality of arrays, each array of the plurality of arrays comprised of data corresponding to the rows of one column of the table, wherein the storing further comprising storing data corresponding to the rows in a packed format; and

storing a second representation of the database on the computer-readable medium, the second representation substantially identical to the first representation.

14. The method of claim 13, further comprising:

performing one or more database operations on the first representation while maintaining a database atomicity, consistency, isolation and durability guarantees on the database and the second representation in the computer-readable medium, the first representation and second representation remaining substantially identical at the successful completion of each transaction.

15. The method of claim 14, wherein the performing one or more database operations comprises a retrieval operation locating a matching row using one of (i) pattern matching AND/XOR instructions and (ii) SIMD instructions applied to multiple row datum of a single column simultaneously.

16. The method of claim 14, wherein the performing one or more database operations comprises a copy-on-modify behavior with modifications being appended as copied arrays to the end of the first representation up the B-tree structure.

17. The method of claim 16, wherein the database is versioned across transactions via lookback to earlier arrays in the first representation.

18. The method of claim 13, wherein the storing the second representation does not include any serialization or boxing of the second representation.

19. The method of claim 13, wherein the storing the second representation accomplished by mapping the volatile memory of the computer to a portion of the computer-readable medium.

20. The method of claim 13, wherein the storing the second representation accomplished by mapping the volatile memory of the computer to a portion of the computer-readable medium.

21. The method of claim 13, wherein the packed format comprises using a power of two amount of space to store each datum.

22. A method of extending a definition of a first variable used in a first computer program, wherein the first computer program is encoded in a programming language, and the first computer program is stored in a computer-readable medium, the method comprising during execution of the first computer program on a computer system:

determining from the definition of the first variable a schema, wherein the schema describes a plurality of columns of a table of a database;

defining a first representation of the first table in a computer-readable memory coupled to the first computer, the first representation comprising a column-oriented format further comprising at least one B-tree for at least one column, wherein the B-tree is composed of at least one array and the at least one B-tree includes references to a plurality of arrays, each array of the plurality of arrays comprised of data corresponding to the rows of one column of the table, wherein the storing further comprising storing data corresponding to the rows in a packed format; and

wherein the first representation supports a database transaction on the table indicated by the first computer program, and wherein the first representation provides database atomicity, consistency, isolation and durability guarantees on completion of the database transaction.

23. The method of claim 22, wherein the first representation thread-safe across access by a second computer program operating on the database.

24. The method of claim 22, further comprising extending a definition of a second variable in a second computer program by repeating the determining and defining on the second variable, the second variable referring to the database.

25. The method of claim 24, wherein the first computer program and the second computer program written in different programming languages.

26. The method of claim 22, wherein the first computer program written in a general purpose computer programming language.

27. The method of claim 22, further comprising a retrieval operation for a single record in the database and wherein the retrieval operation performs in O(n log n) time with low constant overhead.

28. The method of claim 22, further comprising receiving a search having at least two criteria and executing the search using a zig-zag loop to identify a row matching the at least two criteria.

29. A method of searching a database stored in a computer readable medium, the method comprising, the database comprised of a first table, the first table having a plurality of rows of data, each row of data having one or more columns:

receiving a signal, the signal comprising a search, the search comprised of at least two criteria for searching the database;

constructing a zig-zag loop for performing the search; and

executing the zig-zag loop on the database to identify a plurality of rows matching the at least two criteria.