Dynamic data organization

• US 6,223,182 B1
• Filed: 06/30/1998
• Issued: 04/24/2001
• Est. Priority Date: 06/30/1998
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Robertson, Timothy, Feng, Linda, Agarwal, Nipun
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US09/106,448
• Time in Patent Office: 1,029 Days
• Field of Search: 707/7, 707/3, 707/1, 707/102
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A binary hyperspatial code (BH code) is generated for each row in a table to be partitioned. An intermediate table containing the BH codes and rowids of the original table is created within the database. The intermediate table allows for efficient database operations to be performed to determine how to partition the table without causing the data in the table to go off-line. After the desired partitions have been identified from accessing the intermediate table, the table is subdivided into the desired partitions. In one embodiment, the partitions are stored as index-organized tables index on the BH codes so that rows that are close together (as defined by the BH codes) are likely to be located in the same disk block.

Claims

1. A method of organizing data in a data container including a plurality of records, each of said plurality of records including a plurality of fields, said method comprising the computer-implemented steps of:

determining codes for corresponding records of said plurality records based on bit-interleaving values from at least two of said plurality of fields belonging to said corresponding records;

creating a first database object having a plurality of rows corresponding to said plurality of records and a first column for holding said codes for said corresponding records and a second column for holding a reference to said corresponding records;

creating a second database object containing prefixes of said codes based on said first database object; and

subdividing the data container into a plurality of subsets based on said second database object.

2. The method of claim 1, wherein the data container is accessible to a user during the step of subdividing the data container based on said first database object.

3. The method of claim 2, wherein the step of subdividing the data container into plurality of subsets includes the step of partitioning the data container into a plurality of partitions.

4. The method of claim 2, further comprising the step of storing said plurality of subsets as a tree data structure having a plurality of entries corresponding to said plurality of records arranged in an order dictated by said codes for said corresponding records.

5. The method of claim 2, wherein at least of one of the bit interleaved values is non-spatiotemporal.

6. The method of claim 1, wherein the step of subdividing the data container into a plurality of subsets includes the steps of:

grouping entries of the second database objects into ‘

p’

groups, wherein p is a square root of a number of the entries of the second database; and

separately joining each of the groups with the data container to form the subsets.

7. A method of organizing data in a data container including a plurality of records, each of said plurality of records including a plurality of fields, said method comprising the computer-implemented steps of:

determining codes for corresponding records of said plurality records based on bit-interleaving values from at least two of said plurality of fields belonging to said corresponding records;

subdividing the data container into a plurality of subsets based on said codes; and

storing said plurality of subsets as a tree data structure having a plurality of entries corresponding to said plurality of records arranged in an order dictated by said codes for said corresponding records.

8. The method of claim 7, wherein the step of storing said plurality of subsets includes the step of storing said plurality of subsets as a B-tree data structure indexed on said codes.

9. The method of claim 7, wherein at least of one of the bit interleaved values is non-spatiotemporal.

10. A computer-readable medium bearing instruction for organizing data in a data container including a plurality of records, each of said plurality of records including a plurality of fields, said instructions arranged for causing one or more processors to perform the steps of:

determining codes for corresponding records of said plurality records based on bit-interleaving values from at least two said plurality of fields belonging to said corresponding records;

creating a first database object having a plurality of rows corresponding to said plurality of records and a first column for holding said codes for said corresponding records and a second column for holding a reference to said corresponding records;

creating a second database object containing prefixes of said codes based on said first database object; and

subdividing the data container into a plurality of subsets based on said second database object.

11. The computer-readable medium of claim 10, wherein the data container is accessible to a user during the step of subdividing the data container based on said first database object.

12. The computer-readable medium of claim 10, wherein the step of subdividing the data container into a plurality of subsets includes the step of partitioning the data container into a plurality of partitions.

13. The computer-readable medium of claim 10, further comprising the step of storing said plurality of subsets as a tree data structure having a plurality of entries corresponding to said plurality of records indexed on said codes for said corresponding records.

14. The computer-readable medium of claim 10, wherein at least of one of the bit interleaved values is non-spatiotemporal.

15. The computer-readable medium of claim 10, wherein the step of subdividing the data container into a plurality of subsets includes the steps of:

grouping entries of the second database objects into ‘

p’

groups, wherein p is a square root of a number of the entries of the second database; and

separately joining each of the groups with the data container to form the subsets.

16. A computer-readable medium bearing instruction for organizing data in a data container including a plurality of records, each of said plurality of records including a plurality of fields, said instructions arranged for causing one or more processors to perform the steps of:

determining codes for corresponding records of said plurality records based on bit-interleaving values from at least two of said plurality of fields belonging to said corresponding records;

subdividing the data container into a plurality of subsets based on said codes;

storing said plurality of subsets as a tree data structure having a plurality of entries corresponding to said plurality of records arranged in an order dictated by said codes for said corresponding records.

17. The computer-readable medium of claim 16, wherein the step of storing said plurality of subsets as a tree data structure having a plurality of entries corresponding to said plurality of records indexed on said codes for said corresponding records includes the step of storing said plurality of subsets as a B-tree data structure arranged in an order dictated by said codes.

18. The computer-readable medium of claim 16, wherein at least of one of the bit interleaved values is non-spatiotemporal.