Use of primary and secondary indexes to facilitate aggregation of records of an OLAP data cube

• US 7,761,407 B1
• Filed: 10/10/2006
• Issued: 07/20/2010
• Est. Priority Date: 10/10/2006
• Status: Active Grant

• Current Assignee: Medallia, Inc.
• Original Assignee: Medallia, Inc.
• Inventors: Stern, Ulrich
• Primary Examiner(s): Padmanabhan; Kavita
• Application Number:
  US11/546,126
• Time in Patent Office: 1,379 Days
• Field of Search: None
• US Class Current: 707/602
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/2445 Data retrieval commands; View definitions
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

Systems or apparatus, methods, data structures and/or computer programs are provided for implementing an OLAP system that has increased query execution speed, requires reduced data storage capacity for an OLAP system and/or facilitates scaling of an OLAP system to large data cubes. The OLAP system can advantageously be implemented as an all-main memory OLAP system.

Claims

1. A method for facilitating aggregation of records of an OLAP data cubs, each record of the OLAP data cube comprising a value for each of a plurality of atoms which each represent a variable of an OLAP system, wherein the records of the OLAP data cube are ordered in accordance with the values of first and second atoms for each record, thereby producing a sorted OLAP data Cube, such that each record having a specified value of the first atom is located in the sorted OLAP data cube in a contiguous group together with other records, if any, of the OLAP data cube having the same specified value of the first atom, and such that within each contiguous group of one or more records having the same specified value of the first atom, each record having a specified value of the second atom is located in a contiguous subgroup together with other records, if any, having the same specified value of the second atom, the method using a computer system to perform the steps of:

identifying a contiguous group of one or more records having a value of the first atom that matches a value of the first atom identified by a first filter data structure, wherein the contiguous group of one or more records is identified using a data structure that identifies each possible value of the first atom, together with the location in the sorted OLAP data cube of a first record of a contiguous group of one or more records having that value of the first atom;

identifying a record of the identified contiguous group having a value of the second atom that matches a value of the second atom identified by a second filter data structure;

successively evaluating one or more records of the identified contiguous group in a first direction away from the identified record, beginning with the record that is adjacent to the identified record in the first direction, to determine, for each evaluated record, whether the evaluated record has a value of the second atom that matches the value of the second atom identified by the second filter data structure, wherein;

if the evaluated record has a value of the second atom that matches the value of the second atom identified by the second filter data structure, the evaluated record is identified as a record to be included in the aggregation and the step of successively evaluating in a first direction continues with the next adjacent record in the first direction;

if the evaluated record does not have a value of the second atom that matches the value of the second atom identified by the second filter data structure, the step of successively evaluating in the first direction terminates;

successively evaluating one or more records of the identified contiguous group in a second direction away from the identified record that is opposite to the first direction, beginning with the record that is adjacent to the identified record in the second direction, to determine, for each evaluated record, whether the evaluated record has a value of the second atom that matches the value of the second atom identified by the second filter data structure, wherein;

if the evaluated record has a value of the second atom that matches the value of the second atom identified by the second filter data structure, the evaluated record is identified as a record to be included in the aggregation and the step of successively evaluating in the second direction continues with the next adjacent record in the second direction;

if the evaluated record does not have a value of the second atom that matches the value of the second atom identified by the second filter data structure, the step of, successively evaluating in the second direction terminates.

2. A method as in claim 1, further comprising the step of the records of the OLAP data cube to produce the sorted OLAP data cube.

3. A method as in claim 2, further comprising the step of aggregating the record or records identified for inclusion in the aggregation in the steps of successively evaluating.

4. A method as in claim 1, further comprising the step or aggregating the record or, records identified for inclusion in the aggregation in the steps of successively evaluating.

5. A method as in claim 1, wherein the step of identifying a record of the identified contiguous group comprises the step of performing a binary search to identify the record.

6. A method as in claim 1, wherein the step of identifying a record of the identified contiguous group comprises the step of performing a dictionary search to identify the record.

7. A method as in claim 1, wherein

the OLAP data cube, the first filter data structure and the second filter data structure are stored in a main memory.

8. A computer readable medium or media encoded with one or more computer programs and/or data structures for facilitating aggregation of records of an OLAP data cube, each record of the OLAP data cube comprising a value for each of a plurality of atoms which each represent a variable of an OLAP system, wherein the records of the OLAP data cube are ordered in accordance with the Values of first and second atoms for each record, thereby producing a sorted OLAP data cube, such that each record having a specified value of the first atom is located in the sorted OLAP data cube in a contiguous group together with other records, if any, of the OLAP data cube having the same specified value of the first atom, and such that within each contiguous group of one or more records having the same specified value of the first atom, each record having a specified value of the second atom is located on a contiguous subgroup together with other records, if any, having the same specified value of the second atom, the one or more computer programs and/or data structures, comprising:

instructions and/or data for identifying a contiguous group of one or more records having a value of the first atom that matches a value of the first atom identified by a first filter data structure, wherein the instructions and/or data comprise a data structure that identifies each possible value of the first atom, together with the location in the sorted OLAP data cube of a first record of a contiguous group of one or more records having that value of the first atom;

instructions and/or data for identifying a record of the identified contiguous group having a value of the second atom that matches a value of the second atom identified by a second filter data structure;

instructions and/or data for successively evaluating one or more records of the identified contiguous group in a first direction away from the identified record, beginning with the record that is adjacent to the identified record in the first direction, to determine, for each evaluated record, whether the evaluated record has a value of the second atom that matches the value of the second atom identified by the second filter data structure, wherein;

if the evaluated record has a value of the second atom that matches the value of the second atom identified by the second filter data structure, the evaluated record is identified as a record to be included in the aggregation and the successive evaluation in a first direction continues with the next adjacent record in the first direction;

if the evaluated record does not have a value or the second atom that matches the value of the second atom identified by the second filter data structure, the successive evaluation in the first direction terminates;

instructions and/or data for successively evaluating one or more records of the identified contiguous group in a second direction away from the identified record that is opposite to the first direction, beginning with the record that is adjacent to the identified record in the second direction, to determine, for each evaluated record, whether the evaluated record has a value of the second atom that matches the value of the second atom identified by the second filter data structure, wherein;

if the evaluated record has a value of the second atom that matches the value of the second atom identified by the second filter data structure, the evaluated record is identified as a record to be included in the aggregation and the successive evaluation in the second direction continues with the next adjacent record in the second direction;

if the evaluated record does not have a value of the second atom that matches the value of the second atom identified by the second filter data structure, the successive evaluation in the second direction terminates.

9. A computer readable storage medium or media as in claim 8, further comprising instructions and/or data for ordering the records of the OLAP data cube to produce the sorted OLAP data cube.

10. A computer readable storage medium or media as in claim 9, further comprising instructions and/or data for aggregating the record or records identified for inclusion in the aggregation by the instructions and/or data for successively evaluating.

11. A computer readable storage medium or media as in claim 8, further comprising instructions and/or data for aggregating the record or records identified for inclusion in the aggregation by the instructions and/or data for successively evaluating.

12. A computer readable storage medium or media as in claim 8, wherein the instructions and/or data for identifying a record or the identified contiguous group comprise instructions and/or data for performing a binary search to identify the record.

13. A computer readable storage medium or media as in claim 8, wherein the instructions and/or data for identifying a record of the identified contiguous group comprise instructions and/or data for performing a dictionary search to identify the record.

14. A computer readable storage medium or media as in claim 8, wherein the OLAP data cube, the first filter data structure and the second filter data structure are stored in a main memory.

15. A computer system for facilitating aggregation of records of an OLAP data cube, each record of the OLAP data cube comprising a value for each of a plurality of atoms which each represent a variable of an OLAP system, wherein the records of the OLAP data cube are ordered in accordance with the values of first and second atoms for each record, thereby producing a sorted OLAP data cube, such that each record having a specified value of the first atom is located in the sorted OLAP data cube in a contiguous group together with other records, if any, of the OLAP data cube having the same specified value of the first atom, and such that within each contiguous group of one or more records having the same specified value of the first atom, each record having a specified value of the second atom is located in a contiguous subgroup together with other records, if any, having the same specified value of the second atom, the computer system comprising a processing device and main memory for use in:

identifying a contiguous group of one or more records having a value of the first atom that matches a value of the first atom identified by a first filter data structure, wherein the contiguous group of one or more records is identified using a data structure that identifies each possible value of the first atom, together with the location in the sorted OLAP data cube of a first record of a contiguous group of one or more records having that value of the first atom;

identifying a record of the identified contiguous group having a value of the second atom that matches a value of the secondd atom identified by a second filter data structure;

successively evaluating one or more records of the identified contiguous group in a first direction away from the identified record, beginning with the record that is adjacent to the identified record in the first direction, to determine, for each evaluated record, whether the evaluated record has a value of the second atom that matches the value of the second atom identified by the second filter data structure, wherein;

if the evaluated record has a value of the second atom that matches the value or the second atom identified by the second filter data structure, the evaluated record is identified as a record to be included in the aggregation and the successive evaluation in a first direction continues with the next adjacent record in the first direction;

if the evaluated record does not have a value of the second atom that matches the value of the second atom identified by the second filter data structure, the successive evaluation in the first direction terminates;

successively evaluating one or more records of the identified contiguous group in a second direction away from the identified record that is opposite to the first direction, beginning with the record that is adjacent to the identified record in the second direction, to determine, for each evaluated record, whether the evaluated record has a value of the second atom that matches the value of the second atom identified by the second filter data structure, wherein;

if the evaluated record has a value of the second atom that matches the value of the second atom identified by the second filter data structure, the evaluated record is identified ac a record to be included in the aggregation and the successive evaluation in the second direction continues with the next adjacent record in the second direction;

if the evaluated record does not have a value of the second atom that matches the value of the second atom identified by the second filter data structure, the successive evaluation in the second direction terminates.

16. A computer system as in claim 15, wherein the processing device and main memory are further for use in ordering the records of the OLAP data cube to produce the sorted CLAP data cube.

17. A computer system as in claim 16, wherein the processing device and main memory are further for use in aggregating the record or records identified for inclusion in the aggregation by the successively evaluating.

18. A computer system as in claim 15, wherein the processing device and main memory are further for use in aggregating the record or records identified for inclusion in the aggregation by the successively evaluating.

19. A computer system as in claim 15, wherein the identifying a record of the identified contiguous group comprises performing a binary search to identify the record.

20. A computer system as in claim 15, wherein the identifying a record of the identified contiguous group comprises performing a dictionary search to identify the record.

21. A computer system as in claim 15, wherein the OLAP data cube, the first filter data structure and the second filter data structure are stored in the main memory.