Method and apparatus for using a hash-partitioned index to access a table that is not partitioned or partitioned independently of the hash partitioned index

• US 8,583,657 B2
• Filed: 05/28/2004
• Issued: 11/12/2013
• Est. Priority Date: 05/06/2004
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Shukla, Vikram
• Primary Examiner(s): Fleurantin, Jean B
• Application Number:
  US10/857,650
• Publication Number:
  US 20050251524A1
• Time in Patent Office: 3,455 Days
• Field of Search: 707/2, 707/102, 707/100, 707/104.1, 707/999.2, 707/999.1, 707/999.104, 707/747, 707/713, 707/718, 707/658, 707/765, 707/766, 707/769, 707/770, 707/796
• US Class Current: 707/747
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70

Abstract

One embodiment of the present invention provides a system that uses an index that is hash-partitioned to access a table that is not hash-partitioned. During system operation, the database receives a request to perform an operation involving a table in the database. If performing the operation involves looking up a key in the hash-partitioned index, the database applies a hash function to the key to identify a unique partition within the hash-partitioned index for the key, and uses the key to perform a lookup in the identified partition to identify zero or more rows of the table that match the key.

Claims

1. A method for using an index that is hash-partitioned to access a table that is not hash partitioned, executed by at least one or more processors, the method comprising:

receiving a request at a database system to perform an operation involving the table that is not hash-partitioned;

looking up a key in the hash-partitioned index by;

applying a hash function to the key to identify a unique index partition; and

using the key to perform a lookup in the identified index partition to identify a row of the table that matches the key;

adding one or more partitions to the hash-partitioned index by subdividing a source index partition to create two new partitions and creating a set of new partitions to replace a set of existing partitions in the hash-partitioned index, wherein the set of new partitions is more than the set of existing partitions;

scanning through all rows in the table;

obtaining a second key for each row in the table;

applying a new hash function to the obtained second key to identify a unique partition within the two new partitions and the set of new partitions for the obtained second key;

inserting the obtained second key into the identified partition;

replacing the source partition with the two new partitions; and

replacing the existing set of partitions with the new set of partitions.

2. The method of claim 1, wherein the operation includes at least one of:

querying the table to identify rows that match a logical condition;

updating an existing row in the table;

deleting an existing row from the table;

inserting a new row into the table;

creating a hash-partitioned index for the table;

adding a partition to the hash-partitioned index; and

coalescing a partition in the hash-partitioned index.

3. The method of claim 1, wherein applying the hash function to the key comprises applying the hash function to a prefix of the key, instead of the entire key.

4. The method of claim 1, wherein applying the hash function to the key to identify a unique partition for the key comprises calculating a partition number.

5. The method of claim 1, wherein if performing the operation comprises creating a hash-partitioned index, the method further comprises:

obtaining a key for each row in the table;

applying a hash function to the key to identify a unique partition within the hash-partitioned index for the key; and

inserting the key into the identified partition.

6. The method of claim 1, wherein if performing the operation comprises adding a partition to the hash-partitioned index, and if the hash function has a prefix property, the method further comprises:

identifying a source partition in the hash-partitioned index to be subdivided to create two new partitions to replace the source partition, thereby creating an additional partition;

if the source partition is marked unusable, attempting to identify a second index, wherein the index key of the second index is a superset of the index key of the hash-partitioned index;

if a second index is successfully identified,

scanning through one or more keys in the second index,

applying the hash function to each key to determine whether the key maps to the source partition,

if the key maps to the source partition, applying a new hash function to the key to identify one of the two new partitions, and

inserting the key into the identified new partition; and

replacing the source partition with the two new partitions.

7. The method of claim 1, wherein if performing the operation comprises adding a partition to the hash-partitioned index, and if the hash function has a prefix property, the method further comprises:

identifying a source partition in the hash-partitioned index to be subdivided to create two new partitions to replace the source partition, thereby creating an additional partition;

if the source partition is marked unusable, scanning through all the rows in the table,

obtaining a key for each row in the table,

applying the hash function to the key to determine whether the key maps to the source partition,

if the key maps to the source partition, applying a new hash function to the key to identify one of the two new partitions, and

inserting the key into the identified new partition; and

replacing the source partition with the two new partitions.

8. The method of claim 1, wherein if performing the operation comprises adding a partition to the hash-partitioned index, and if the hash function does not have a prefix property, the method further comprises:

creating a set of new partitions to replace the set of existing partitions, wherein the number of new partitions is one greater than the number of existing partitions;

scanning through all the keys in the existing partitions,

applying a new hash function to each key to identify a unique partition within the set of new partitions for the key, and

inserting the key into the identified partition; and

replacing the existing set of partitions with the new set of partitions.

9. The method of claim 1, wherein if performing the operation comprises coalescing a partition in the hash-partitioned index, and if the hash function has a prefix property, the method further comprises:

identifying two source partitions in the hash-partitioned index that share the same prefix to be coalesced to create a single new partition, thereby reducing the number of partitions by one;

if both of the source partitions are marked usable, coalescing the two source partitions to create the new partition by

scanning through all the keys in the two source partitions, and

inserting the keys into the single new partition; and

replacing the two source partitions with the new partition.

10. The method of claim 1, wherein if performing the operation comprises coalescing a partition to the hash-partitioned index, and if the hash function has a prefix property, the method further comprises:

identifying two source partitions in the hash-partitioned index that share the same prefix to be coalesced to create a single new partition, thereby reducing the number of partitions by one;

if at least one of the two source partitions is marked unusable, attempting to identify a second index, wherein the index key of the second index is a superset of the index key of the hash-partitioned index;

if a second index is successfully identified,

scanning through one or more keys in the second index,

applying the hash function to each key to determine whether the key maps to one of the source partitions, and

if the key maps to one of the source partitions, inserting the key into the identified new partition; and

replacing the source partition with the two new partitions.

11. The method of claim 1, wherein if performing the operation comprises coalescing a partition to the hash-partitioned index, and if the hash function has a prefix property, the method further comprises:

identifying two source partitions in the hash-partitioned index that share the same prefix to be coalesced to create a single new partition, thereby reducing the number of partitions by one;

if at least one of the two source partitions is marked unusable,

scanning through all the rows in the table,

obtaining a key for each row in the table,

applying the hash function to the key to determine whether the key maps to one of the source partitions, and

if the key maps to one of the source partitions, inserting the key into the identified new partition; and

replacing the source partition with the two new partitions.

12. The method of claim 1, wherein if performing the operation comprises coalescing a partition in the hash-partitioned index, and if the hash function does not have a prefix property, the method further comprises:

creating a set of new partitions to replace the set of existing partitions, wherein the number of new partitions is one less than the number of existing partitions;

scanning through all the keys in the existing partitions;

applying a new hash function to each key to identify a unique partition within the set of new partitions for the key;

inserting the key into the identified partition; and

replacing the existing set of partitions with the new set of partitions.

13. The method of claim 1, wherein if performing the operation comprises coalescing a partition in the hash-partitioned index, and if the hash function does not have a prefix property, the method further comprises:

creating a set of new partitions to replace the set of existing partitions, wherein the number of new partitions is one less than the number of existing partitions;

scanning through all the rows in the table;

obtaining a key for each row in the table;

applying a new hash function to the key to identify a unique partition within the set of new partitions for the key;

inserting the key into the identified partition; and

replacing the existing set of partitions with the new set of partitions.

14. The method of claim 1, wherein the hash function has a prefix property.

27. The non-transitory computer-readable storage medium of claim 1 9, wherein if performing the operation comprises coalescing a partition in the hash-partitioned index, and if the hash function does not have a prefix property, the method further comprises:

creating a set of new partitions to replace the set of existing partitions, wherein the number of new partitions is one less than the number of existing partitions;

scanning through all the rows in the table;

obtaining a key for each row in the table;

applying a new hash function to the key to identify a unique partition within the set of new partitions for the key;

inserting the key into the identified partition; and

replacing the existing set of partitions with the new set of partitions.

15. A non-transitory computer readable storage medium storing instructions that when executed by a computer cause the computer to perform a method that uses a hash partitioned index to access a table that is not hash partitioned, the method comprising:

receiving a request at a database system to perform an operation involving

the table that is not hash-partitioned;

looking up a key in the hash-partitioned index by;

applying a hash function to the key to identify a unique index partition; and

using the key to perform a lookup in the identified index partition to identify a row of the table that matches the key;

adding one or more partitions to the hash-partitioned index by subdividing a source index partition to create two new partitions and creating a set of new partitions to replace a set of existing partitions in the hash-partitioned index, wherein the set of new partitions is more than the set of existing partitions;

scanning through all rows in the table;

obtaining a second key for each row in the table;

applying a new hash function to the obtained second key to identify a unique partition within the two new partitions and the set of new partitions for the obtained second key;

inserting the obtained second key into the identified partition;

replacing the source partition with the two new partitions; and

replacing the existing set of partitions with the new set of partitions.

16. The computer-readable storage medium of claim 15, wherein the operation includes at least one of:

querying the table to identify rows that match a logical condition;

updating an existing row in the table;

deleting an existing row from the table;

inserting a new row into the table;

creating a hash-partitioned index for the table;

adding a partition to the hash-partitioned index; and

coalescing a partition in the hash-partitioned index.

17. The computer-readable storage medium of claim 15, wherein applying the hash function to the key comprises applying the hash function to a prefix of the key, instead of the entire key.

18. The computer-readable storage medium of claim 15, wherein applying the hash function to the key to identify a unique partition for the key comprises calculating a partition number.

19. The computer-readable storage medium of claim 15, wherein if performing the operation comprises creating a hash-partitioned index, the method further comprises:

obtaining a key for each row in the table;

applying a hash function to the key to identify a unique partition within the hash-partitioned index for the key; and

inserting the key into the identified partition.

20. The non-transitory computer-readable storage medium of claim 15, wherein if performing the operation comprises adding a partition to the hash partitioned index, and if the hash function has a prefix property, the method further comprises:

identifying a source partition in the hash partitioned index to be subdivided to create two new partitions to replace the source partition, thereby creating an additional partition;

if the source partition is marked unusable, attempting to identify a second index, wherein the index key of the second index is a superset of the index key of the hash partitioned index;

if a second index is successfully identified,

scanning through one or more keys in the second index;

applying the hash function to each key to determine whether the key maps to the source partition;

if the key maps to the source partition, applying a new hash function to the key to identify one of the two new partitions; and

inserting the key into the identified new partition; and

replacing the source partition with the two new partitions.

21. The non-transitory computer-readable storage medium of claim 15, wherein if performing the operation comprises adding a partition to the hash-partitioned index, and if the hash function has a prefix property, the method further comprises:

identifying a source partition in the hash-partitioned index to be subdivided to create two new partitions to replace the source partition, thereby creating an additional partition;

if the source partition is marked unusable,

scanning through all the rows in the table;

obtaining a key for each row in the table;

applying the hash function to the key to determine whether the key maps to the source partition;

if the key maps to the source partition, applying a new hash function to the key to identify one of the two new partitions, and inserting the key into the identified new partition; and

replacing the source partition with the two new partitions.

22. The non-transitory computer-readable storage medium of claim 15, wherein if performing the operation comprises adding a partition to the hash-partitioned index, and if the hash function does not have a prefix property, the method further comprises:

creating a set of new partitions to replace the set of existing partitions, wherein the number of new partitions is one greater than the number of existing partitions;

scanning through all the keys in the existing partitions;

applying a new hash function to each key to identify a unique partition within the set of new partitions for the key;

inserting the key into the identified partition; and

replacing the existing set of partitions with the new set of partitions.

23. The non-transitory computer-readable storage medium of claim 15, wherein if performing the operation comprises coalescing a partition in the hash-partitioned index, and if the hash function has a prefix property, the method further comprises:

identifying two source partitions in the hash-partitioned index that share the same prefix to be coalesced to create a single new partition, thereby reducing the number of partitions by one;

if both of the source partitions are marked usable, coalescing the two source partitions to create the new partition by scanning through all the keys in the two source partitions, and inserting the keys into the single new partition; and

replacing the two source partitions with the new partition.

24. The non-transitory computer-readable storage medium of claim 15, wherein if performing the operation comprises coalescing a partition to the hash-partitioned index, and if the hash function has a prefix property, the method further comprises:

identifying two source partitions in the hash-partitioned index that share the same prefix to be coalesced to create a single new partition, thereby reducing the number of partitions by one;

if at least one of the two source partitions is marked unusable, attempting to identify a second index, wherein the index key of the second index is a superset of the index key of the hash-partitioned index;

if a second index is successfully identified,

scanning through one or more keys in the second index,

applying the hash function to each key to determine whether the key maps to one of the source partitions, and

if the key maps to one of the source partitions, inserting the key into the identified new partition; and

replacing the source partition with the two new partitions.

25. The non-transitory computer-readable storage medium of claim 15, wherein if performing the operation comprises coalescing a partition to the hash-partitioned index, and if the hash function has a prefix property, the method further comprises:

identifying two source partitions in the hash-partitioned index that share the same prefix to be coalesced to create a single new partition, thereby reducing the number of partitions by one;

if at least one of the two source partitions is marked unusable,

scanning through all the rows in the table,

obtaining a key for each row in the table,

applying the hash function to the key to determine whether the key maps to one of the source partitions, and

if the key maps to one of the source partitions, inserting the key into the identified new partition; and

replacing the source partition with the two new partitions.

26. The non-transitory computer-readable storage medium of claim 15, wherein if performing the operation comprises coalescing a partition in the hash-partitioned index, and if the hash function does not have a prefix property, the method further comprises:

creating a set of new partitions to replace the set of existing partitions, wherein the number of new partitions is one less than the number of existing partitions;

scanning through all the keys in the existing partitions;

applying a new hash function to each key to identify a unique partition within the set of new partitions for the key;

inserting the key into the identified partition; and

replacing the existing set of partitions with the new set of partitions.

28. The non-transitory computer-readable storage medium of claim 15, wherein the hash function has a prefix property.

29. An apparatus for using an index that is hash-partitioned to access a table that is not hash-partitioned comprising:

a database system;

a processor;

a receiving mechanism that receives requests to perform an operation involving a table in the table that is not hash-partitioned;

a lookup mechanism that looks up a key in the hash-partitioned index by;

applying the hash function to the key to identify a unique index partition, and use the key to perform a lookup in the identified index partition to identify a row of the table that matches the key; and

a index-partition adding mechanism that adds one or more partitions to the hash partitioned index by subdividing a source index partition to create two new partitions and creating a set of new partitions to replace a set of existing partitions in the hash-partitioned index, wherein the set of new partitions is more than the set of existing partitions, and wherein the index-partition added mechanism is further configured to;

scanning through all rows in the table;

obtaining a second key for each row in the table;

applying a new hash function to the obtained second key to identify a unique partition within the two new partitions and the set of new partitions for the obtained second key;

inserting the obtained second key into the identified partition;

replacing the source partition with the two new partitions; and

replacing the existing set of partitions with the new set of partitions.

30. The apparatus of claim 29, wherein the operation includes at least one of:

querying the table to identify rows that match a logical condition;

updating an existing row in the table;

deleting an existing row from the table;

inserting a new row into the table;

creating a hash-partitioned index for the table;

adding a partition to the hash-partitioned index; and

coalescing a partition in the hash-partitioned index.

31. The apparatus of claim 29, wherein the lookup means is further configured to apply the hash function to a prefix of the key, instead of the entire key.

32. The apparatus of claim 29, wherein the lookup means is further configured to calculate a partition number.

33. The apparatus of claim 29, wherein the apparatus further comprises an index creating mechanism, wherein if the operation comprises creating a hash-partitioned index, the index creation mechanism:

obtain a key for each row in the table,

apply a hash function to the key to identify a unique partition within the hash-partitioned index for the key, and to insert the key into the identified partition.

34. The apparatus of claim 29, wherein the apparatus further comprises an index addition mechanism, wherein if performing the operation comprises adding a partition to the hash-partitioned index, and if the hash function has a prefix property, the index addition mechanism:

identifies a source partition in the hash-partitioned index to be subdivided to create two new partitions to replace the source partition, thereby creating an additional partition;

if the source partition is marked unusable, attempts to identify a second index, wherein the index key of the second index is a superset of the index key of the hash-partitioned index;

if a second index is successfully identified,

scans through one or more keys in the second index,

applies the hash function to each key to determine whether the key maps to the source partition,

if the key maps to the source partition, applies a new hash function to the key to identify one of the two new partitions, and to insert the key into the identified new partition; and

replaces the source partition with the two new partitions.

35. The apparatus of claim 29, wherein the apparatus further comprises an index addition mechanism, wherein if performing the operation comprises adding a partition to the hash-partitioned index, and if the hash function has a prefix property, the index addition mechanism:

identifies a source partition in the hash-partitioned index to be subdivided to create two new partitions to replace the source partition, thereby creating an additional partition;

if the source partition is marked unusable,

scans through all the rows in the table,

obtains a key for each row in the table,

applies the hash function to the key to determine whether the key maps to the source partition,

if the key maps to the source partition, applies a new hash function to the key to identify one of the two new partitions, and to insert the key into the identified new partition; and

replaces the source partition with the two new partitions.

36. The apparatus of claim 29, wherein the apparatus further comprises an index creating mechanism, wherein if performing the operation comprises adding a partition to the hash-partitioned index, and if the hash function does not have a prefix property, the index creating mechanism:

creates a set of new partitions to replace the set of existing partitions, wherein the number of new partitions is one greater than the number of existing partitions;

scans through all the keys in the existing partitions;

applies a new hash function to each key to identify a unique partition within the set of new partitions for the key;

inserts the key into the identified partition; and

replaces the existing set of partitions with the new set of partitions.

37. The apparatus of claim 29, wherein the apparatus further comprises a coalescing mechanism, wherein if performing the operation comprises coalescing a partition in the hash-partitioned index, and if the hash function has a prefix property, the coalescing mechanism:

identifies two source partitions in the hash-partitioned index that share the same prefix to be coalesced to create a single new partition, thereby reducing the number of partitions by one;

if both of the source partitions are marked usable, scans through all the keys in the two source partitions and inserts the keys into the single new partition; and

replaces the two source partitions with the new partition.

38. The apparatus of claim 29, wherein the apparatus further comprises a coalescing mechanism, wherein if performing the operation comprises coalescing a partition in the hash-partitioned index, and if the hash function has a prefix property, the coalescing mechanism:

identifies two source partitions in the hash-partitioned index that share the same prefix to be coalesced to create a single new partition, thereby reducing the number of partitions by one;

if at least one of the two source partitions is marked unusable, attempts to identify a second index, wherein the index key of the second index is a superset of the index key of the hash-partitioned index;

if a second index is successfully identified,

scans through one or more keys in the second index,

applies the hash function to each key to determine whether the key maps to one of the source partitions, and

if the key maps to one of the source partitions, inserts the key into the new partition; and

replaces the two source partitions with the new partition.

39. The apparatus of claim 29, wherein the apparatus further comprises a coalescing mechanism, wherein if performing the operation comprises coalescing a partition in the hash-partitioned index, and if the hash function has a prefix property, the coalescing mechanism:

identifies two source partitions in the hash-partitioned index that share the same prefix to be coalesced to create a single new partition, thereby reducing the number of partitions by one;

if at least one of the two source partitions is marked unusable, the coalescing mechanism further;

scans through all the rows in the table;

obtains a key for each row in the table;

applies the hash function to the key to determine whether the key maps to one of the source partitions;

if the key maps to one of the source partitions, inserts the key into the new partition; and

replaces the two source partitions with the new partition.

40. The apparatus of claim 29, wherein the apparatus further comprises a coalescing mechanism, wherein if performing the operation comprises coalescing a partition in the hash-partitioned index, and if the hash function does not have a prefix property, the coalescing mechanism:

creates a set of new partitions to replace the set of existing partitions, wherein the number of new partitions is one less than the number of existing partitions;

scans through all the keys in the existing partitions;

applies a new hash function to each key to identify a unique partition within the set of new partitions for the key;

inserts the key into the identified partition; and

replaces the existing set of partitions with the new set of partitions.

41. The apparatus of claim 29, wherein the apparatus further comprises a coalescing mechanism, wherein if performing the operation comprises coalescing a partition in the hash-partitioned index, and if the hash function does not have a prefix property, the coalescing mechanism:

creates a set of new partitions to replace the set of existing partitions, wherein the number of new partitions is one less than the number of existing partitions;

scans through all the rows in the table;

obtains a key for each row in the table;

applies a new hash function to the key to identify a unique partition within the set of new partitions for the key;

inserts the key into the identified partition; and

replaces the existing set of partitions with the new set of partitions.

42. The apparatus of claim 29, wherein the hash function has a prefix property.