Columnar storage of a database index

• US 10,496,621 B2
• Filed: 10/23/2015
• Issued: 12/03/2019
• Est. Priority Date: 03/08/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Oks, Artem A., Larson, Per-Ake, Rangarajan, Srikumar, Zwilling, Michael James, Blakeley, Jose A., Kodavalla, Hanumantha R.
• Primary Examiner(s): Yen, Syling
• Application Number:
  US14/921,239
• Publication Number:
  US 20160042019A1
• Time in Patent Office: 1,502 Days
• Field of Search: 707703, 707736, 707758, 707781, 707769, 707791-793, 707797, 707801, 707802
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes

Abstract

Methods, systems, and computer-readable media of columnar storage of a database index are disclosed. A particular columnar index includes a column store that stores rows of the columnar index in a column-wise fashion and a delta store that stores rows of the columnar index in a row-wise fashion. The column store also includes an absence flag array. The absence flag array includes entries that indicate whether certain rows have been logically deleted from the column store.

Claims

1. A computer system, comprising:

at least one processor;

at least one memory storing a columnar index associated with a single relational database table, the columnar index comprising;

a column store comprising a plurality of rows of the columnar index stored in a column-wise fashion, wherein the columnar index associated with the single relational database table is divided into a plurality of segments, wherein individual segments of the plurality of segments correspond to individual subsets of a plurality of rows of the single relational database table, and wherein the column store includes a plurality of column arrays for the individual segments of the plurality of segments; and

a delta store comprising particular rows of the columnar index that have been updated or deleted stored in a row-wise fashion,

wherein the computer system is configured to;

for individual segments of the plurality of segments, store respective absence flag arrays in the column store, wherein the respective absence flag arrays include flags corresponding to individual rows of a corresponding segment, and wherein the respective absence flag arrays indicate which rows of the corresponding segment have been logically deleted from the column store;

in response to an update for a first row of a first segment, in a first absence flag array corresponding to the first segment, set a first flag identifying the first row;

in response to a delete for a second row of the first segment, in the first absence flag array corresponding to the first segment, set a second flag identifying the second row; and

in response to a query, execute a query processing engine configured to execute the query by concurrently executing;

a first query operator on the column store in a column-wise fashion, and

a second query operator on the delta store in a row-wise fashion.

2. The computer system of claim 1, wherein the computer system is further configured to execute a data transfer component to move a third row of the columnar index from the delta store to the column store.

3. A method, comprising:

dividing a database index for a single relational database table into a plurality of segments, wherein the database index comprises a plurality of rows and a plurality of columns, and wherein individual segments comprise a subset of the plurality of rows of the database index;

converting the individual segments into a plurality of column arrays, wherein the plurality of column arrays includes a column array for each of the plurality of columns;

for the individual segments of the plurality of segments, storing the plurality of column arrays in a column store;

storing data in a row-wise fashion in a delta store comprising rows of the column store that have been updated or deleted;

for the individual segments of the plurality of segments, storing at least one respective absence flag array in the column store, wherein the at least one respective absence flag array includes individual flags corresponding to individual rows of a corresponding segment, and wherein the at least one respective absence flag array indicates which rows of the corresponding segment have been logically deleted from the column store;

in response to an update for a first row of a first segment, in a first absence flag array corresponding to the first segment, setting a first flag identifying the first row;

in response to a delete for a second row of the first segment, in the first absence flag array corresponding to the first segment, setting a second flag identifying the second row; and

in response to a query, concurrently executing;

a first query operator on the column store in a column-wise fashion, and

a second query operator on the delta store in a row-wise fashion.

4. The method of claim 3, wherein the column store is stored as a second relational database table and wherein each of the plurality of column arrays is stored as a row of the second relational database table.

5. The method of claim 4, wherein rows of the second relational database table that represent column arrays of the same column of the database index are clustered together in the second relational database table.

6. The method of claim 3, wherein:

updating a particular row from the column store includes;

copying the particular row from the column store to the delta store;

marking an entry in an absence flag array that corresponds to the particular row; and

updating the particular row at the delta store; and

deleting the particular row from the column store includes marking the entry in the absence flag array that corresponds to the particular row.

7. The method of claim 3, further comprising inserting a new row into the database index by inserting the new row into the delta store.

8. The method of claim 3, further comprising converting rows stored in the delta store into one or more additional column arrays, storing the one or more additional column arrays in the column store, and removing the converted rows from the delta store.

9. The method of claim 8, wherein the conversion is performed in response to at least one of:

determining that a number of rows in the delta store is greater than a threshold, determining that a time period has elapsed, or receiving a user command.

10. The method of claim 3, further comprising performing a particular query that references a columnar index of the database index.

11. The method of claim 10, wherein one or more column arrays used for processing the particular query is copied into a contiguous portion of a memory cache.

12. The method of claim 10, wherein performing the particular query comprises:

executing the particular query with respect to the column store to generate first partial results;

executing the particular query with respect to the delta store to generate second partial results; and

combining the first partial results and the second partial results.

13. The method of claim 10, wherein performing the particular query comprises:

converting the delta store to one or more additional column arrays; and

executing the particular query with respect to the additional column arrays.

14. The method of claim 3, further comprising, in response to the query:

filtering out data from results of the first query operator based on the absence flag arrays; and

aggregating the filtered results of the first query operator and results of the second query operator.

15. The method of claim 3, further comprising:

in response to the update for the first row of the first segment, copying the first row from the column store to the delta store; and

in response to the delete for the second row of the first segment, copying the second row from the column store to the delta store.

16. The method of claim 15, further comprising:

in response to the update for the first row of the first segment, deleting the first row from the column store; and

in response to the delete for the second row of the first segment, deleting the second row from the column store.

17. The method of claim 3, further comprising independently compressing each of the column arrays for each of the segments in the column store.

18. The method of claim 17 wherein the compressed column arrays occupy different amounts of storage space in the column store.

19. The method of claim 17, wherein compressing each of the column arrays includes application of a bit packing algorithm, a dictionary compression algorithm, a run-length encoding algorithm, or any combination thereof.

20. The method of claim 3, wherein subsets of the rows are mutually disjoint.

21. The method of claim 5, wherein, for each segment of the plurality of segments:

the at least one respective absence flag array includes a plurality of bit locations corresponding respectively to the rows of the segment; and

for each bit location of the bit locations, a first predetermined value at the bit location indicates logical deletion of the corresponding row from the column store.

22. A data storage device comprising instructions that, when executed by a computer, cause the computer to:

divide a database index for a single relational database table into a plurality of segments, wherein the database index comprises a plurality of rows and a plurality of columns, and wherein individual segments comprise a subset of the plurality of rows of the database index;

convert the individual segments into a plurality of column arrays, wherein the plurality of column arrays includes a column array for each of the plurality of columns;

for the individual segments of the segments, store the plurality of column arrays in a column store;

store data in a row-wise fashion in a delta store comprising rows of the column store that have been updated or deleted;

for the individual segments of the plurality of segments, store at least one respective absence flag array in the column store, wherein at least one the respective absence flag array includes individual flags corresponding to individual rows of a corresponding segment, and wherein the at least one respective absence flag array indicates which rows of the corresponding segment have been logically deleted from the column store;

in response to an update for a first row of a first segment, in a first absence flag array corresponding to the first segment, set a first flag identifying the first row;

in response to a delete for a second row of the first segment, in the first absence flag array corresponding to the first segment, set a second flag identifying the second row; and

in response to a query, concurrently execute;

a first query operator on the column store in a column-wise fashion, and

a second query operator on the delta store in a row-wise fashion.