Interval-partitioning method for multidimensional data

• US 6,003,036 A
• Filed: 02/12/1998
• Issued: 12/14/1999
• Est. Priority Date: 02/12/1998
• Status: Expired due to Term

• Current Assignee: Michael W. Martin
• Original Assignee: Michael W. Martin
• Inventors: Martin, Michael W.
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): ALAM, SHAHID AL
• Application Number:
  US09/022,936
• Time in Patent Office: 670 Days
• Field of Search: 707/8, 707/100, 707/3, 707/201, 707/5, 707/9, 707/501, 707/101, 707/102
• US Class Current: 1/1
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A data structure that uses one or more keys which are members of a multidimensional composite key to partition sparse data (FIG. 2A, FIG. 2B) into a hypercube like structure (FIG. 1). Only the data structure produced by the method in this invention is actually better than a hypercube since all involved keys can have true symmetric access as opposed to just the keys that have the highest sort order significance. Equivalent query efficiency could only be otherwise obtained through storing multiple copies of the sparse data sorted on different permutations of the member keys of the multidimensional composite key (FIG. 2C). The data structure has two major components: the partitioned data with or without the boundary keys and the non-dense index necessarily containing the boundary keys (FIG. 3). This data structure and partitioning method can be used to partition multidimensional data across physical hardware storage devices and parallel computer architectures (FIG. 4) to produce variable grained data partitions that can be queried, loaded, or updated in parallel and simultaneous multidimensional index selectivity. And finally, as noted above, this same partitioning method can be used in a nested fashion or in combination with other data structures to provide good performance for the batch maintenance of volatile data and special performance advantages for true time-series data.

Claims

1. A method of partitioning data regardless of the sparsity of said data on to computer memory or computer storage media with one or more keys or groups of keys from said data such that the selectivity produced by any combination of said keys or said groups of one or more keys can be precisely controlled comprising the steps of:

a) determining the number of records from said data to be packed into each unit partition

b) determining selectivity of each said key or said group of one or more keys chosen from said composite key so that the combined selectivity of all said keys or said groups of one or more keys is equal to the total number of unit partitions in said data

c) arbitrarily choosing a first component key or group of one or more component keys from said chosen component keys in said composite key

d) partitioning said data by said first key or group of one or more keys of said chosen component keys possibly followed by one or more of the other component keys in said composite key

e) creating a non-dense index formed from said first key or group of one or more keys and possibly followed by one or more of the other component keys in said composite key aligned with the boundaries of said partitions created in step d)

f) choosing a new first key or group of one or more keys from said chosen component keys in said composite key

g) repeating steps d), e), and f) within each said partition created from the previous iteration of step d) as many times as required to produce said total number of unit partitions contained within said data thereby producing an organization of said data whose said selectivity of combinations of said keys can be precisely controlled by said selectivity for each said key or group of one or more said keys as determined in step b).

2. A method of partitioning data regardless of the sparsity of said data on to computer memory or computer storage media with one or more keys or groups of keys from said data such that the selectivity of any combination of involved said keys or said groups of one or more keys is symmetric yet the degree of packing of records from said data into unit partitions can be precisely controlled comprising the steps of:

a) determining the number of records from said data to be packed into each unit partition

b) determining selectivity of each said key or said group of one or more keys chosen from said composite key so that the combined selectivity of all said keys or said groups of one or more keys is equal to the total number of unit partitions in said data

c) arbitrarily choosing a first component key or group of one or more component keys from said chosen component keys in said composite key

d) partitioning said data by said first key or group of one or more keys of said chosen component keys possibly followed by one or more of the other component keys in said composite key

e) creating a non-dense index formed from said first key or group of one or more keys and possibly followed by one or more of the other component keys in said composite key aligned with the boundaries of said partitions created in step d)

f) choosing a new first key or group of one or more keys from said chosen component keys in said composite key

g) repeating steps d), e), and f) within each said partition created from the previous iteration of step d) as many times as required to produce said total number of unit partitions contained within said data thereby producing an organization of said data whose said selectivity for any combination of said keys or said groups of one or more keys can be made to be symmetric by step b) and whose packing of said records into said unit partitions can be precisely controlled by step a).

3. The method of claim 2, wherein all said unit partitions, file pages, or I/O sectors are fully packed to hold the maximum number of said records per unit partition.

4. The method of claim 3, wherein said records within each said unit partition are further subpartitioned by the method of claim 3 in a nested fashion such that additional said computer memory or said computer storage media are not required.

5. The method of claim 4 combined with other data structures or partitioning methods such that said data can be partitioned across hardware devices or entire computers with conventional methods and subpartitioned by the method of claim 3 in a nested fashion such that additional said computer memory or said computer storage are not required.

6. A method of partitioning data regardless of the sparsity of said data on to computer memory or computer storage media with one or more keys or groups of keys from said data such that the selectivity of any combination of involved said keys or said groups of one or more keys is symmetric yet a non-dense index which requires no addition computer memory or computer storage media space can be built comprising the steps of:

a) determining the number of records from said data to be packed into each unit partition taking into account the extra available space in said unit partitions due to the removal of one or more said component records from one said record in said unit partitions

b) determining selectivity of each said key or said group of one or more records chosen from said composite key so that the combined selectivity of all said keys or said groups of one or more keys is equal to the total number of unit partitions in said data

c) arbitrarily choosing a first component key or group of one or more component keys from said chosen component keys in said composite key

d) partitioning said data by said first key or group of one or more keys of said chosen component keys possibly followed by one or more of the other component keys in said composite key

e) creating a non-dense index formed from said first key or group of one or more keys and possibly followed by one or more of the other component keys in said composite key aligned with the boundaries of said partitions created in step d) and removing one or more said component keys from one said record out of each said unit partition corresponding to each entry in said non-dense index

f) choosing a new first key or group of one or more keys from said chosen component keys in said composite key

g) repeating steps d), e), and f) within each said partition created from the previous iteration of step d) as many times as required to produce said total number of unit partitions contained within said data thereby producing an organization of said data whose said selectivity for any combination of said keys or said groups of one or more keys can be made to be symmetric by st b) and on which a corresponding non-dense index requiring no additional computer memory or computer storage media space can be built.