Database query analysis technology

• US 8,452,755 B1
• Filed: 05/11/2010
• Issued: 05/28/2013
• Est. Priority Date: 05/12/2009
• Status: Active Grant

• Current Assignee: Microstrategy Incorporated
• Original Assignee: Microstrategy Incorporated
• Inventors: Li, Benjamin Z., Ye, Alex
• Primary Examiner(s): Yen, Syling
• Application Number:
  US12/777,643
• Time in Patent Office: 1,113 Days
• Field of Search: 707/706, 707/707, 707/708, 707/709, 707/711, 707/712, 707/714, 707/715, 707/716, 707/717, 707/718, 707/719, 707/721, 707/723, 707/736, 707/758, 707/765, 707/781, 707/999.001, 707/999.002, 707/999.003
• US Class Current: 707/715
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/38 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/93 Document management systems

Abstract

Database query analysis technology, in which an input query is received that relates to multiple attribute classes of data records. An index that is descriptive of the data records in data storage is accessed and relative positions in the accessed index for the multiple attribute classes are identified. The accessed index is processed based on more than one of the multiple attribute classes and the identified relative positions, and the processed index is used to identify groups of data records that are included in the data records in the data storage and that share common values for the multiple attribute classes in the input query. Metrics corresponding to the data records included in each of the identified groups of data records are accessed, computations are performed on the accessed metrics, and a report is generated that reflects results of the computations.

Claims

1. A computer-implemented method comprising:

receiving an input query that relates to multiple attribute classes of data records having attribute classes associated therewith in data storage;

identifying the multiple attribute classes related to the input query, the multiple attribute classes being a subset of less than all of the attribute classes associated with the data records in the data storage;

accessing, from electronic storage, an index that is descriptive of the data records in the data storage, the index defining positional relationships between the attribute classes of the data records, where an attribute class that has a relatively lower position in the index than another attribute class is a child attribute class of the other attribute class;

identifying relative positions in the accessed index for the multiple attribute classes identified as being related to the input query;

processing the accessed index based on more than one of the multiple attribute classes identified as being related to the input query and the identified relative positions;

identifying, using the processed index, groups of data records that are included in the data records in the data storage and that share common values for the multiple attribute classes identified as being related to the input query;

accessing, from the data storage, metrics corresponding to the data records included in each of the identified groups of data records;

performing computations on the accessed metrics that distinguish among each of the identified groups of data records;

generating a report that reflects results of the computations; and

storing, in electronic storage, the generated report,

wherein processing the accessed index based on more than one of the multiple attribute classes identified as being related to the input query and the identified relative positions comprises;

identifying portions of the accessed index that correspond to the multiple attribute classes identified as being related to the input query and disregarding portions of the accessed index that correspond to attribute classes other than the multiple attribute classes identified as being related to the input query;

based on the identified relative positions, selecting, from among the multiple attribute classes identified as being related to the input query, the attribute class that has the highest relative position within the accessed index;

for each distinct value in the selected attribute class, assigning a distinct identifier to portions of the accessed index within the selected attribute class that correspond to the distinct value;

based on the identified relative positions, selecting, from among the multiple attribute classes associated with the input query, the attribute class that has a second highest relative position after the attribute class that has the highest relative position;

for each portion of the index within the selected attribute class that has the second highest relative position, identifying an attribute value corresponding to the portion and a parent identifier of a portion of the index within the attribute class that has the highest relative position that links to the portion of the index within the selected attribute class that has the second highest relative position;

based on the identified attribute values and parent identifiers, identifying distinct attribute value and parent identifier pairs within the selected attribute class that has the second highest relative position; and

for each distinct attribute value and parent identifier pair, assigning a distinct identifier to portions of the index within the selected attribute class that has the second highest relative position that share the distinct attribute value and parent identifier pair.

2. The method of claim 1 wherein:

processing the accessed index based on more than one of the multiple attribute classes identified as being related to the input query and the identified relative positions further comprises determining whether all of the multiple attribute classes identified as being related to the input query have been processed; and

identifying, using the processed index, groups of data records that are included in the data records in the data storage and that share common values for the multiple attribute classes identified as being related to the input query occurs in response to a determination that all of the multiple attribute classes identified as being related to the input query have been processed, where identifying, using the processed index, groups of data records comprises;

identifying, from among the multiple attribute classes identified as being related to the input query, the attribute class that has the lowest relative position in the index;

analyzing the identifiers assigned to the portions of the index within the identified attribute class that has the lowest relative position in the index;

based on the analysis, identifying groups of the portions of the index within the identified attribute class that share a common identifier; and

identifying groups of data records that are mapped to by an identified group of the portions of the index within the identified attribute class that share a common identifier.

3. The method of claim 2 wherein processing the accessed index based on more than one of the multiple attribute classes identified as being related to the input query and the identified relative positions further comprises:

in response to a determination that all of the multiple attribute classes associated with the input query have not been processed;

based on the identified relative positions, selecting, from among the multiple attribute classes identified as being related to the input query, the attribute class that has a third highest relative position in the index after the attribute class that has the second highest relative position;

for each portion of the index within the selected attribute class that has the third highest relative position, identifying an attribute value corresponding to the portion and a parent identifier of a portion of the index within the attribute class that has the second highest relative position that links to the portion of the index within the selected attribute class that has the third highest relative position;

based on the identified attribute values and parent identifiers, identifying distinct attribute value and parent identifier pairs within the selected attribute class that has the third highest relative position; and

for each distinct attribute value and parent identifier pair, assigning a distinct identifier to portions of the index within the selected attribute class that has the third highest relative position that share the distinct attribute value and parent identifier pair.

4. The method of claim 3 wherein identifying, using the processed index, groups of data records that are included in the data records in the data storage and that share common values for the multiple attribute classes identified as being related to the input query comprises:

conditioned on the attribute class that has the third highest relative position being the attribute class, among the multiple attribute classes associated with the input query, that has the lowest relative position in the index;

analyzing the identifiers assigned to the portions of the index within the attribute class that has the third highest relative position;

based on the analysis, identifying groups of the portions of the index that are within the attribute class that has the third highest relative position and that share a common identifier; and

identifying groups of data records that are mapped to by an identified group of the portions of the index that are within the attribute class that has the third highest relative position and that share a common identifier.

5. A computer-implemented method comprising:

receiving an input query that relates to multiple attribute classes of data records having attribute classes associated therewith in data storage;

identifying the multiple attribute classes related to the input query, the multiple attribute classes being a subset of less than all of the attribute classes associated with the data records in the data storage;

accessing, from electronic storage, an index that is descriptive of the data records in the data storage, the index defining positional relationships between the attribute classes of the data records, where an attribute class that has a relatively lower position in the index than another attribute class is a child attribute class of the other attribute class;

identifying portions of the index that correspond to the multiple attribute classes identified as being related to the input query;

modifying the accessed index by removing portions of the accessed index that correspond to attribute classes other than the multiple attribute classes identified as being related to the input query;

analyzing the modified index;

based on the analysis, identifying redundancies that are present in the modified index, the redundancies resulting from removal of the portions of the index that correspond to the attribute classes other than the multiple attribute classes identified as being related to the input query;

compressing the identified redundancies in the modified index;

updating index mapping definitions based on compression of the identified redundancies in the modified index;

identifying, using the compressed index and the updated mapping definitions, groups of data records that are included in the data records in the data storage and that share common values for the multiple attribute classes identified as being related to the input query;

accessing, from the data storage, metrics corresponding to the data records included in each of the identified groups of data records;

performing computations on the accessed metrics that distinguish among each of the identified groups of data records;

generating a report that reflects results of the computations; and

storing, in electronic storage, the generated report.

6. The method of claim 5 wherein:

compressing the identified redundancies in the modified index comprises compressing two different portions of the index within a particular attribute class into a single portion of the index within the particular attribute class; and

updating index mapping definitions based on compression of the identified redundancies in the modified index comprises;

identifying data records mapped to by each of the two different portions of the index, and

causing the single portion of the index to map to the identified data records.

7. The method of claim 5 wherein modifying the accessed index by removing portions of the accessed index that correspond to attribute classes other than the multiple attribute classes identified as being related to the input query comprises updating relationships between the multiple attribute classes identified as being related to the input query.

8. At least one computer-readable storage medium encoded with executable instructions that, when executed by at least one processor, cause the at least one processor to perform operations comprising:

receiving an input query that relates to multiple attribute classes of data records having attribute classes associated therewith in data storage;

identifying the multiple attribute classes related to the input query, the multiple attribute classes being a subset of less than all of the attribute classes associated with the data records in the data storage;

accessing, from electronic storage, an index that is descriptive of the data records in the data storage, the index defining positional relationships between the attribute classes of the data records, where an attribute class that has a relatively lower position in the index than another attribute class is a child attribute class of the other attribute class;

identifying relative positions in the accessed index for the multiple attribute classes identified as being related to the input query;

processing the accessed index based on more than one of the multiple attribute classes identified as being related to the input query and the identified relative positions;

identifying, using the processed index, groups of data records that are included in the data records in the data storage and that share common values for the multiple attribute classes identified as being related to the input query;

accessing, from the data storage, metrics corresponding to the data records included in each of the identified groups of data records;

performing computations on the accessed metrics that distinguish among each of the identified groups of data records;

generating a report that reflects results of the computations; and

storing, in electronic storage, the generated report,

wherein processing the accessed index based on more than one of the multiple attribute classes identified as being related to the input query and the identified relative positions comprises;

identifying portions of the accessed index that correspond to the multiple attribute classes identified as being related to the input query and disregarding portions of the accessed index that correspond to attribute classes other than the multiple attribute classes identified as being related to the input query;

based on the identified relative positions, selecting, from among the multiple attribute classes identified as being related to the input query, the attribute class that has the highest relative position within the accessed index;

for each distinct value in the selected attribute class, assigning a distinct identifier to portions of the accessed index within the selected attribute class that correspond to the distinct value;

based on the identified relative positions, selecting, from among the multiple attribute classes associated with the input query, the attribute class that has a second highest relative position after the attribute class that has the highest relative position;

for each portion of the index within the selected attribute class that has the second highest relative position, identifying an attribute value corresponding to the portion and a parent identifier of a portion of the index within the attribute class that has the highest relative position that links to the portion of the index within the selected attribute class that has the second highest relative position;

based on the identified attribute values and parent identifiers, identifying distinct attribute value and parent identifier pairs within the selected attribute class that has the second highest relative position; and

for each distinct attribute value and parent identifier pair, assigning a distinct identifier to portions of the index within the selected attribute class that has the second highest relative position that share the distinct attribute value and parent identifier pair.

10. The at least one computer-readable storage medium of claim 8 wherein:

processing the accessed index based on more than one of the multiple attribute classes identified as being related to the input query and the identified relative positions further comprises determining whether all of the multiple attribute classes identified as being related to the input query have been processed; and

identifying, using the processed index, groups of data records that are included in the data records in the data storage and that share common values for the multiple attribute classes identified as being related to the input query occurs in response to a determination that all of the multiple attribute classes identified as being related to the input query have been processed, where identifying, using the processed index, groups of data records comprises;

identifying, from among the multiple attribute classes identified as being related to the input query, the attribute class that has the lowest relative position in the index;

analyzing the identifiers assigned to the portions of the index within the identified attribute class that has the lowest relative position in the index;

based on the analysis, identifying groups of the portions of the index within the identified attribute class that share a common identifier; and

identifying groups of data records that are mapped to by an identified group of the portions of the index within the identified attribute class that share a common identifier.

11. The at least one computer-readable storage medium of claim 10 wherein processing the accessed index based on more than one of the multiple attribute classes identified as being related to the input query and the identified relative positions further comprises:

in response to a determination that all of the multiple attribute classes associated with the input query have not been processed;

based on the identified relative positions, selecting, from among the multiple attribute classes identified as being related to the input query, the attribute class that has a third highest relative position in the index after the attribute class that has the second highest relative position;

for each portion of the index within the selected attribute class that has the third highest relative position, identifying an attribute value corresponding to the portion and a parent identifier of a portion of the index within the attribute class that has the second highest relative position that links to the portion of the index within the selected attribute class that has the third highest relative position;

based on the identified attribute values and parent identifiers, identifying distinct attribute value and parent identifier pairs within the selected attribute class that has the third highest relative position; and

for each distinct attribute value and parent identifier pair, assigning a distinct identifier to portions of the index within the selected attribute class that has the third highest relative position that share the distinct attribute value and parent identifier pair.

12. The at least one computer-readable storage medium of claim 11 wherein identifying, using the processed index, groups of data records that are included in the data records in the data storage and that share common values for the multiple attribute classes identified as being related to the input query comprises:

conditioned on the attribute class that has the third highest relative position being the attribute class, among the multiple attribute classes associated with the input query, that has the lowest relative position in the index;

analyzing the identifiers assigned to the portions of the index within the attribute class that has the third highest relative position;

based on the analysis, identifying groups of the portions of the index that are within the attribute class that has the third highest relative position and that share a common identifier; and

identifying groups of data records that are mapped to by an identified group of the portions of the index that are within the attribute class that has the third highest relative position and that share a common identifier.

9. An electronic system comprising:

at least one electronic data storage device; and

at least one processor configured to perform operations comprising;

receiving an input query that relates to multiple attribute classes of data records having attribute classes associated therewith in data storage;

identifying the multiple attribute classes related to the input query, the multiple attribute classes being a subset of less than all of the attribute classes associated with the data records in the data storage;

accessing, from electronic storage, an index that is descriptive of the data records in the data storage, the index defining positional relationships between the attribute classes of the data records, where an attribute class that has a relatively lower position in the index than another attribute class is a child attribute class of the other attribute class;

identifying relative positions in the accessed index for the multiple attribute classes identified as being related to the input query;

processing the accessed index based on more than one of the multiple attribute classes identified as being related to the input query and the identified relative positions;

identifying, using the processed index, groups of data records that are included in the data records in the data storage and that share common values for the multiple attribute classes identified as being related to the input query;

accessing, from the data storage, metrics corresponding to the data records included in each of the identified groups of data records;

performing computations on the accessed metrics that distinguish among each of the identified groups of data records;

generating a report that reflects results of the computations; and

storing, in electronic storage, the generated report,

wherein processing the accessed index based on more than one of the multiple attribute classes identified as being related to the input query and the identified relative positions comprises;

identifying portions of the accessed index that correspond to the multiple attribute classes identified as being related to the input query and disregarding portions of the accessed index that correspond to attribute classes other than the multiple attribute classes identified as being related to the input query;

based on the identified relative positions, selecting, from among the multiple attribute classes identified as being related to the input query, the attribute class that has the highest relative position within the accessed index;

for each distinct value in the selected attribute class, assigning a distinct identifier to portions of the accessed index within the selected attribute class that correspond to the distinct value;

based on the identified relative positions, selecting, from among the multiple attribute classes associated with the input query, the attribute class that has a second highest relative position after the attribute class that has the highest relative position;

for each portion of the index within the selected attribute class that has the second highest relative position, identifying an attribute value corresponding to the portion and a parent identifier of a portion of the index within the attribute class that has the highest relative position that links to the portion of the index within the selected attribute class that has the second highest relative position;

based on the identified attribute values and parent identifiers, identifying distinct attribute value and parent identifier pairs within the selected attribute class that has the second highest relative position; and

for each distinct attribute value and parent identifier pair, assigning a distinct identifier to portions of the index within the selected attribute class that has the second highest relative position that share the distinct attribute value and parent identifier pair.

13. The system of claim 9 wherein:

processing the accessed index based on more than one of the multiple attribute classes identified as being related to the input query and the identified relative positions further comprises determining whether all of the multiple attribute classes identified as being related to the input query have been processed; and

identifying, using the processed index, groups of data records that are included in the data records in the data storage and that share common values for the multiple attribute classes identified as being related to the input query occurs in response to a determination that all of the multiple attribute classes identified as being related to the input query have been processed, where identifying, using the processed index, groups of data records comprises;

identifying, from among the multiple attribute classes identified as being related to the input query, the attribute class that has the lowest relative position in the index;

analyzing the identifiers assigned to the portions of the index within the identified attribute class that has the lowest relative position in the index;

based on the analysis, identifying groups of the portions of the index within the identified attribute class that share a common identifier; and

identifying groups of data records that are mapped to by an identified group of the portions of the index within the identified attribute class that share a common identifier.

14. The system of claim 13 wherein processing the accessed index based on more than one of the multiple attribute classes identified as being related to the input query and the identified relative positions further comprises:

in response to a determination that all of the multiple attribute classes associated with the input query have not been processed;

based on the identified relative positions, selecting, from among the multiple attribute classes identified as being related to the input query, the attribute class that has a third highest relative position in the index after the attribute class that has the second highest relative position;

for each portion of the index within the selected attribute class that has the third highest relative position, identifying an attribute value corresponding to the portion and a parent identifier of a portion of the index within the attribute class that has the second highest relative position that links to the portion of the index within the selected attribute class that has the third highest relative position;

based on the identified attribute values and parent identifiers, identifying distinct attribute value and parent identifier pairs within the selected attribute class that has the third highest relative position; and

for each distinct attribute value and parent identifier pair, assigning a distinct identifier to portions of the index within the selected attribute class that has the third highest relative position that share the distinct attribute value and parent identifier pair.

15. The system of claim 14 wherein identifying, using the processed index, groups of data records that are included in the data records in the data storage and that share common values for the multiple attribute classes identified as being related to the input query comprises:

conditioned on the attribute class that has the third highest relative position being the attribute class, among the multiple attribute classes associated with the input query, that has the lowest relative position in the index;

analyzing the identifiers assigned to the portions of the index within the attribute class that has the third highest relative position;

based on the analysis, identifying groups of the portions of the index that are within the attribute class that has the third highest relative position and that share a common identifier; and

identifying groups of data records that are mapped to by an identified group of the portions of the index that are within the attribute class that has the third highest relative position and that share a common identifier.

16. At least one computer-readable storage medium encoded with executable instructions that, when executed by at least one processor, cause the at least one processor to perform operations comprising:

receiving an input query that relates to multiple attribute classes of data records having attribute classes associated therewith in data storage;

identifying the multiple attribute classes related to the input query, the multiple attribute classes being a subset of less than all of the attribute classes associated with the data records in the data storage;

accessing, from electronic storage, an index that is descriptive of the data records in the data storage, the index defining positional relationships between the attribute classes of the data records, where an attribute class that has a relatively lower position in the index than another attribute class is a child attribute class of the other attribute class;

identifying portions of the index that correspond to the multiple attribute classes identified as being related to the input query;

modifying the accessed index by removing portions of the accessed index that correspond to attribute classes other than the multiple attribute classes identified as being related to the input query;

analyzing the modified index;

based on the analysis, identifying redundancies that are present in the modified index, the redundancies resulting from removal of the portions of the index that correspond to the attribute classes other than the multiple attribute classes identified as being related to the input query;

compressing the identified redundancies in the modified index;

updating index mapping definitions based on compression of the identified redundancies in the modified index;

identifying, using the compressed index and the updated mapping definitions, groups of data records that are included in the data records in the data storage and that share common values for the multiple attribute classes identified as being related to the input query;

accessing, from the data storage, metrics corresponding to the data records included in each of the identified groups of data records;

performing computations on the accessed metrics that distinguish among each of the identified groups of data records;

generating a report that reflects results of the computations; and

storing, in electronic storage, the generated report.

17. The at least one computer-readable storage medium of claim 16 wherein:

compressing the identified redundancies in the modified index comprises compressing two different portions of the index within a particular attribute class into a single portion of the index within the particular attribute class; and

updating index mapping definitions based on compression of the identified redundancies in the modified index comprises;

identifying data records mapped to by each of the two different portions of the index, and

causing the single portion of the index to map to the identified data records.

18. The at least one computer-readable storage medium of claim 16 wherein modifying the accessed index by removing portions of the accessed index that correspond to attribute classes other than the multiple attribute classes identified as being related to the input query comprises updating relationships between the multiple attribute classes identified as being related to the input query.

19. An electronic system comprising:

at least one electronic data storage device; and

at least one processor configured to perform operations comprising;

receiving an input query that relates to multiple attribute classes of data records having attribute classes associated therewith in data storage;

identifying the multiple attribute classes related to the input query, the multiple attribute classes being a subset of less than all of the attribute classes associated with the data records in the data storage;

accessing, from electronic storage, an index that is descriptive of the data records in the data storage, the index defining positional relationships between the attribute classes of the data records, where an attribute class that has a relatively lower position in the index than another attribute class is a child attribute class of the other attribute class;

identifying portions of the index that correspond to the multiple attribute classes identified as being related to the input query;

modifying the accessed index by removing portions of the accessed index that correspond to attribute classes other than the multiple attribute classes identified as being related to the input query;

analyzing the modified index;

based on the analysis, identifying redundancies that are present in the modified index, the redundancies resulting from removal of the portions of the index that correspond to the attribute classes other than the multiple attribute classes identified as being related to the input query;

compressing the identified redundancies in the modified index;

updating index mapping definitions based on compression of the identified redundancies in the modified index;

identifying, using the compressed index and the updated mapping definitions, groups of data records that are included in the data records in the data storage and that share common values for the multiple attribute classes identified as being related to the input query;

accessing, from the data storage, metrics corresponding to the data records included in each of the identified groups of data records;

performing computations on the accessed metrics that distinguish among each of the identified groups of data records;

generating a report that reflects results of the computations; and

storing, in electronic storage, the generated report.

20. The system of claim 19 wherein:

compressing the identified redundancies in the modified index comprises compressing two different portions of the index within a particular attribute class into a single portion of the index within the particular attribute class; and

updating index mapping definitions based on compression of the identified redundancies in the modified index comprises;

identifying data records mapped to by each of the two different portions of the index, and

causing the single portion of the index to map to the identified data records.

21. The system of claim 19 wherein modifying the accessed index by removing portions of the accessed index that correspond to attribute classes other than the multiple attribute classes identified as being related to the input query comprises updating relationships between the multiple attribute classes identified as being related to the input query.