Hybrid bifurcation of intersection nodes

Patent metadata

Field	Value
Publication number	US-9323812-B2
Application number	US-201313861037-A
Country	US
Kind code	B2
Filing date	Apr 11, 2013
Priority date	Apr 11, 2013
Publication date	Apr 26, 2016
Grant date	Apr 26, 2016

Abstract

A method of processing a set of intersection queries in a multi-dimensional data structure may include receiving the set of intersection queries for the multi-dimensional data structure. The method may also include determining whether to process each of the set the intersection queries individually, or whether to process the set of intersection queries together using pre-cached modifier mappings. The method may additionally include processing the set of intersection queries, and providing intersection values that correspond to the set of intersection queries.

First claim

What is claimed is:

1. A method of processing a set of intersection queries in a multi-dimensional data structure, the method comprising:
receiving the set of intersection queries for the multi-dimensional data structure;
determining whether to process each of the set the intersection queries individually, or whether to process the set of intersection queries together using pre-cached modifier mappings, wherein:
the pre-cached modifier mappings comprise mappings between values in nodes in the multi-dimensional data structure and values used to adjust the respective nodes before the respective nodes are rolled up into parent nodes; and
processing the set of intersection queries together comprises:
determining a set of intersection nodes from the set of intersection queries;
enumerating a set of base nodes that descend from the set of intersection nodes;
removing any duplicate base nodes from the set of base nodes;
projecting each base node in the set of base nodes onto one or more corresponding intersection nodes using the pre-cached modifier mappings to compute intersection values for the intersection nodes; and
providing the intersection values;

processing the set of intersection queries; and
providing the intersection values that correspond to the set of intersection queries.

2. The method of claim 1 wherein processing the intersection queries individually comprises, for each intersection query in the set of intersection queries:
determining an intersection node from the intersection query;
determining a set of base nodes that descend from the intersection node;
computing a modifier for each node in the set of base nodes;
projecting each base node onto the intersection node using the corresponding modifier to compute an intersection value; and
providing the intersection value.

3. The method of claim 1 wherein determining whether to process each of the set the intersection queries individually, or whether to process the set of intersection queries together using the pre-cached modifier mappings, is based on a size of the set of intersection queries, such that processing the set of intersection queries individually is more likely when the size of the set of intersection queries is below a threshold, and processing the set of intersection queries together is more likely when the size of the set of intersection queries is above a threshold.

4. The method of claim 1 wherein determining whether to process each of the set the intersection queries individually, or whether to process the set of intersection queries together using the pre-cached modifier mappings, is based on a sparsity of the multi-dimensional data structure, such that processing the set of intersection queries individually is more likely when the sparsity of the multi-dimensional data structure is below a threshold, and processing the set of intersection queries together is more likely when the sparsity of the multi-dimensional data structure is above a threshold.

5. The method of claim 1 wherein determining whether to process each of the set the intersection queries individually, or whether to process the set of intersection queries together using the pre-cached modifier mappings, is based on an average depth of the multi-dimensional data structure for the set of intersection queries, such that processing the set of intersection queries individually is more likely when the average depth of the multi-dimensional data structure is below a threshold, and processing the set of intersection queries together is more likely when the average depth of the multi-dimensional data structure is above a threshold.

6. The method of claim 1 wherein determining whether to process each of the set the intersection queries individually, or whether to process the set of intersection queries together using the pre-cached modifier mappings, is based on a base level width of the multidimensional data structure, such that processing the set of intersection queries individually is more likely when the base-level width of the multi-dimensional data structure is below a threshold, and processing the set of intersection queries together is more likely when the base-level width of the multi-dimensional data structure is above a threshold.

7. A non-transitory computer-readable memory comprising a sequence of instructions which, when executed by one or more processors, causes the one or more processors to process a set of intersection queries in a multi-dimensional data structure by:
receiving the set of intersection queries for the multi-dimensional data structure;
determining whether to process each of the set the intersection queries individually, or whether to process the set of intersection queries together using pre-cached modifier mappings, wherein:
the pre-cached modifier mappings comprise mappings between values in nodes in the multi-dimensional data structure and values used to adjust the respective nodes before the respective nodes are rolled up into parent nodes; and
processing the set of intersection queries together comprises:
determining a set of intersection nodes from the set of intersection queries;
enumerating a set of base nodes that descend from the set of intersection nodes;
removing any duplicate base nodes from the set of base nodes;
projecting each base node in the set of base nodes onto one or more corresponding intersection nodes using the pre-cached modifier mappings to compute intersection values for the intersection nodes; and

providing the intersection values;
processing the set of intersection queries; and
providing the intersection values that correspond to the set of intersection queries.

8. The non-transitory computer-readable memory according to claim 7 wherein processing the intersection queries individually comprises, for each intersection query in the set of intersection queries: determining an intersection node from the intersection query; determining a set of base nodes that descend from the intersection node; computing a modifier for each node in the set of base nodes; projecting each base node onto the intersection node using the corresponding modifier to compute an intersection value; and providing the intersection value.

9. The non-transitory computer-readable memory according to claim 7 wherein determining whether to process each of the set the intersection queries individually, or whether to process the set of intersection queries together using the pre-cached modifier mappings, is based on a size of the set of intersection queries, such that processing the set of intersection queries individually is more likely when the size of the set of intersection queries is below a threshold, and processing the set of intersection queries together is more likely when the size of the set of intersection queries is above a threshold.

10. The non-transitory computer-readable memory according to claim 7 wherein determining whether to process each of the set the intersection queries individually, or whether to process the set of intersection queries together using the pre-cached modifier mappings, is based on a sparsity of the multi-dimensional data structure, such that processing the set of intersection queries individually is more likely when the sparsity of the multi-dimensional data structure is below a threshold, and processing the set of intersection queries together is more likely when the sparsity of the multi-dimensional data structure is above a threshold.

11. The non-transitory computer-readable memory according to claim 7 wherein determining whether to process each of the set the intersection queries individually, or whether to process the set of intersection queries together using the pr

Assignees

• Oracle Int Corp

Inventors

• Bhatia Rajesh
• Tungaturthy Prasad
• Hsu Pei Ken

Classifications

• G06F16/2458 Primary

  Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries · CPC title

• G06F16/283

  Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP · CPC title

• G06F17/30533 Primary

  Physics · mapped topic

• G06F17/30592

  Physics · mapped topic