Disk optimized paging for column oriented databases

• US 9,922,060 B2
• Filed: 04/25/2016
• Issued: 03/20/2018
• Est. Priority Date: 12/30/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Petculescu, Cristian, Netz, Amir
• Primary Examiner(s): Woo, Isaac M
• Application Number:
  US15/137,827
• Publication Number:
  US 20160239513A1
• Time in Patent Office: 694 Days
• Field of Search: 707600-899
• CPC Class Codes: G06F 16/16 File or folder operations, e.g. details of user interfaces specifically adapted to file systems
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof

Abstract

Implementing a database system using a plurality of sequentially ordered drives to store sequential portions of columns of the database, but where the database system is usable by a system configured for use with in-memory database systems. The method includes loading one or more columns of a database into main memory of a computing system as a table based database. The method further includes dividing a column of the database into sequential portions. Each of the sequential portions is of sufficient size to create efficient transfers using hard disk controllers to transfer an entire sequential portion. The method further includes writing each of the sequential portions sequentially onto sequentially ordered drives in a round robin fashion such that sequential portions of the column are on sequential drives.

Claims

1. In a computing environment, a database system using a plurality of sequentially ordered drives to store sequential portions of columns of the database, but where the database system is usable by a system configured for use with in-memory database systems, the system comprising:

one or more processors;

a plurality of sequentially ordered drives for storing data;

main memory; and

one or more computer readable media, wherein the one or more computer readable media comprise computer executable instructions that are executable by at least one of the one or more processors to cause at least one of the one or more processors to perform the following;

load one or more columns of a database into main memory of a computing system as a table based database;

divide a column of the database into sequential portions;

write each of the sequential portions sequentially onto the sequentially ordered drives in a round robin fashion such that sequential portions of the column are stored on sequential drives, the sequential portions of the column being stored on sequential drives enabling parallelism during querying;

copy at least some of the sequential portions from the sequentially ordered drives into a ring buffer; and

upon determining that certain data copied into the ring buffer is hot data that has a predetermined frequency of reuse, transfer the hot data to another buffer.

2. The database system of claim 1, wherein each of the sequentially ordered drives is an SSD drive.

3. The database system of claim 1, wherein each of the sequential portions is a segment.

4. The database system of claim 1, wherein each of the drives stores database data on a file per column basis such that each drive has a single data file for a given column of the database irrespective of how many portions of a column are stored at a given drive.

5. The database system of claim 1, wherein the computer executable instructions are further executable by at least one of the one or more processors to cause at least one of the one or more processors to:

for one or more other columns, divide a column of the database into sequential portions and write each of the sequential portions sequentially onto sequentially ordered drives in a round robin fashion.

6. The database system of claim 1, wherein the ring buffer is implemented in the main memory.

7. The database system of claim 6, wherein said another buffer is implemented in the main memory of the computing system.

8. The database system of claim 1, wherein said another buffer is smaller than the ring buffer.

9. The database system of claim 1, wherein items in said another buffer are recycled at a slower rate than items in the ring buffer.

10. A computing system comprising:

one or more processors;

a ring buffer, the ring buffer including a first pointer and a second pointer, wherein the first pointer marks a start of a free portion of the ring buffer and the second pointer marks an end of the free portion, the free portion comprising a portion of the ring buffer that is available to be overwritten by data being read to the ring buffer; and

one or more computer readable media, wherein the one or more computer readable media comprise computer executable instructions that are executable by at least one of the one or more processors to cause at least one of the one or more processors to perform the following;

subsequent to a data item in the ring buffer being used, wherein the data item is currently outside of the free portion during use, move the second ring buffer from a first side of the data item, to an opposing side of the data item, such that the data item is contained within the free portion subsequent to the use, thereby marking a memory location of the ring buffer containing the data item as free for use.

11. The computing system of claim 10, wherein the computer executable instructions are further executable by at least one of the one or more processors to cause at least one of the one or more processors to:

detect a potential new use of the data item; and

upon determining that the data item has not been overwritten in the ring buffer, moving the second pointer back to the first side of the data item, such that the data item is no longer contained within the free portion.

12. The computing system of claim 10, wherein the computer executable instructions are further executable by at least one of the one or more processors to cause at least one of the one or more processors to:

reuse the data item subsequent to the moving the second pointer back to the first side of the data item.

13. The computing system of claim 12, wherein the computer executable instructions are further executable by at least one of the one or more processors to cause at least one of the one or more processors to:

subsequent to a data item in the ring buffer being re-used, move the second ring buffer from the first side of the data item, to the opposing side of the data item again, such that the data item is again contained within the free portion of the ring buffer.

14. The computing system of claim 10, wherein the computer executable instructions are further executable by at least one of the one or more processors to cause at least one of the one or more processors to:

further base movement of the second pointer on a determination as to a predetermined percentage of data that is needed from the ring buffer.

15. A computing system comprising:

one or more processors;

a ring buffer, the ring buffer including a first pointer and a second pointer, wherein the first pointer marks a start of a free portion of the ring buffer and the second pointer marks an end of the free portion, the free portion comprising a portion of the ring buffer that is available to be overwritten by data being read to the ring buffer; and

one or more computer readable media, wherein the one or more computer readable media comprise computer executable instructions that are executable by at least one of the one or more processors to cause at least one of the one or more processors to perform the following;

subsequent to a data item in the ring buffer being used, wherein the data item is currently outside of the free portion during use, writing the data item to a front of the free portion, next to the first pointer.

16. The computing system of claim 15, wherein the computer executable instructions are further executable by at least one of the one or more processors to cause at least one of the one or more processors to:

move the first pointer to an opposing side of the data item in such a manner as to capture the data item within the free portion, between the first pointer and the second pointer.