Columnar storage of a database index

• US 9,195,657 B2
• Filed: 03/08/2010
• Issued: 11/24/2015
• 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:
  US12/719,015
• Publication Number:
  US 20110219020A1
• Time in Patent Office: 2,087 Days
• Field of Search: 707/703, 707/758, 707/781, 707/769, 707791-793, 707/797, 707/801, 707/802, 707/999.001, 707/999.1
• US Class Current: 1/1
• 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:

a memory storing a columnar index associated with a relational database table, the columnar index comprising;

a column store comprising one or more first rows of the columnar index stored in a column-wise fashion;

a delta store comprising one or more second rows of the columnar index stored in a row-wise fashion; and

wherein the column store further comprises an absence flag array that includes an entry for each row of the first rows that indicates whether the row has been logically deleted from the column store, wherein the absence flag array indicates a first set of rows of the column store that have been updated and a second set of rows that have been deleted, and wherein the column store associated with the database table is based on a plurality of segments including a first segment and a second segment, wherein each segment comprises a set of rows of a database index, and wherein a first column array based on the first segment is stored as a different size array than a second column array based on the second segment.

2. The computer system of claim 1, wherein the memory further stores a row-wise index and wherein the computer system is configured to execute a query processing engine configured to process queries that reference both the columnar index and the row-wise index.

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

4. The computer system of claim 1, wherein the absence flag array corresponds to a first segment of the relational database table and the column store includes a second absence flag array that corresponds to a second segment of the relational database table.

5. The computer system of claim 1, wherein the column store includes a plurality of column clusters, and wherein the absence flag array is stored within the column store separately from the plurality of column clusters.

6. A method, comprising:

dividing a database index comprising a plurality of rows and a plurality of columns into a plurality of segments, wherein each segment comprises a set of rows of the database index, the database index associated with a relational database table;

converting each segment into a plurality of column arrays, including a column array for each of the plurality of columns, wherein at least one segment of the plurality of segments is compressed and wherein after compression of the at least one segment, a first column array is stored as a different size array than a second column array;

storing the plurality of column arrays in a column store; and

storing an absence flag array as a column of the column store, wherein each entry of the absence flag array indicates whether a particular row of the database index has been logically deleted from the column store, wherein the absence flag array indicates a first set of rows of the column store that have been updated and a second set of rows that have been deleted.

7. The method of claim 6, wherein the column store is stored as a second relational database table and wherein each column array is stored as a row of the second relational database table.

8. The method of claim 7, wherein rows of the second relational database table that represent column arrays for a same column of the database index are clustered together in the second relational database table.

9. The method of claim 6, further comprising storing data in a delta store comprising rows of the column store that have been updated or deleted.

10. The method of claim 9, wherein updating or deleting a particular row from the column store comprises:

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

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

updating or deleting the particular row at the delta store.

11. The method of claim 9, further comprising converting rows stored in a 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.

12. The method of claim 11, wherein the conversion is performed in response to one of determining that a number of rows in the delta store is greater than a threshold, determining that a time period has elapsed, and receiving a user command.

13. The method of claim 6, further comprising performing a query that references a columnar index that includes the column store.

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

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

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

combining the first partial results and the second partial results.

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

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

executing the query with respect to the additional column arrays.

16. The method of claim 6, further comprising updating a particular row at a delta store by copying the particular row from the column store to the delta store and marking an entry corresponding to the particular row at the absence flag array to indicate that the particular row has been logically deleted from the column store.

17. The method of claim 6, further comprising accessing the absence flag array to identify rows that have been logically deleted from the column store, executing a query that references a columnar index, and adding a filter predicate to the query to eliminate the identified rows that have been logically deleted from the column store.

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

divide each column of a database index comprising a plurality of rows and a plurality of columns into one or more column arrays, the database index associated with a relational database table;

store the one or more column arrays in a column store, wherein the one or more column arrays are stored in a column-wise fashion and wherein the column store is based on a plurality of segments, wherein each segment comprises a set of rows of the database index, and wherein a first column array based on a first segment is stored as a different size array than a second column array based on a second segment;

store an absence flag array in the column store, wherein each entry of the absence flag array indicates whether a particular row of the database index is absent from the column store; and

store data in a delta store comprising rows of the database index stored in a row-wise fashion,

wherein each row of the database index is stored in only one of the column store and the delta store, wherein the absence flag array indicates a first set of rows of the column store that have been updated and a second set of rows that have been deleted, and wherein associated with the database table is based on a plurality of segments, wherein each segment comprises a set of rows of the database index.

19. The data storage device of claim 18, wherein the absence flag array comprises an entry for each row of the relational database table, the entry indicating whether a corresponding row has been logically deleted or not logically deleted.

20. The data storage device of claim 18, wherein the column store is stored as a second relational database table, and wherein each column array is stored as a row of the second relational database table.