Database management delete efficiency

• US 9,229,960 B2
• Filed: 02/11/2013
• Issued: 01/05/2016
• Est. Priority Date: 02/11/2013
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bestgen, Robert J., Beuch, Daniel E.
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): CHEUNG, HUBERT G
• Application Number:
  US13/763,971
• Publication Number:
  US 20140229427A1
• Time in Patent Office: 1,058 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/214 Database migration support
• CPC Class Codes: G06F 16/902 using more than one table in sequence, i.e. systems with three or more layers

Abstract

A method, system, and computer program product to efficiently delete data from a database is disclosed. The method, system, and computer program product may include structuring the database to have a plurality of tables having indexes to related rows and having keys with key values associated with particular rows. The method, system, and computer program product may include deleting rows in the database tables by deleting keys in indexes related to the rows in an order such that corresponding rows are deleted based on relation to the keys. The method, system, and computer program product may include ordering the rows to be deleted based on concepts such as hierarchy, spatial locality, temporal locality, frequency of access, number of rows, and value uniqueness. Comparatively closely related relationships may be prioritized to be deleted.

Claims

1. A computer-implemented method of managing a database contained in a storage facility, comprising:

structuring the database to a have a plurality of tables having indexes to related rows and having keys associated with particular rows, the database including a first table and a first index for accessing the first table,

the first index being organized as a search tree having a plurality of nodes, the plurality of nodes including a plurality of lower-most child nodes, each lower-most child node storing a key corresponding with a row of the first table; and

deleting three or more rows in the first table by deleting keys in corresponding lower-most child nodes of the first index in a first order,

the first order beginning at a first lower-most child node to be deleted, the first lower-most child node being a node closest to one side of the tree,

the first order including a first subsequent node to be next deleted after the first lower-most child node, the first subsequent node being a second lower-most child node reachable from the first lower-most child node in a first number of jumps in the tree, wherein a second number of jumps from the second lower-most child node is required to reach a third lower-most child node to be deleted, wherein the first number of jumps is fewer than the second number of jumps.

2. The method of claim 1, wherein the one side of the tree is a leftmost side of the tree.

3. The method of claim 1, wherein the one side of the tree is a rightmost side of the tree.

4. The method of claim 1, wherein jumps are movements between nodes up or down the index.

5. The method of claim 1, wherein the search tree is a binary search tree.

6. A computer-implemented method of managing a database, comprising:

receiving a request to delete a first row and a second row in a database table of a database;

determining a first index node of a first value of the first row and a second index node of a second value of the second row of an index of the database, wherein the first and second index nodes are contained in an index tree of the database;

comparing a first relationship involving the first index node and a third index node of the index of the database with a second relationship involving the second index node and the third index node of the index of the database; and

setting the first row to be deleted before the second row if the first relationship is a first comparatively closely related relationship, setting the second row to be deleted before the first row if the second relationship is a second comparatively closely related relationship, and setting the first row to be deleted before the second row otherwise;

wherein the first comparatively closely related relationship and the second comparatively closely related relationship are defined as each being a minimum number of jumps necessary to get from a row associated with a near key to a row associated with a search key.

7. The method of claim 6, wherein the first relationship and the second relationship are hierarchical relationships involving index nodes.

8. The method of claim 6, wherein the first relationship and the second relationship are spatial locality relationships involving index nodes, which include a difference in index node locations.

9. The method of claim 6, wherein the first relationship and the second relationship are temporal locality relationships involving index nodes, which include whether a particular index node is in a memory.

10. The method of claim 6, wherein the first relationship and the second relationship are frequency relationships involving index nodes, which include whether a particular index node is frequently accessed to a memory.

11. The method of claim 6, further comprising selecting a first index that has a greater number of rows than a second index.

12. The method of claim 6, further comprising selecting a first index that has a greater quantity of unique values than a second index.

13. The method of claim 6, wherein jumps are movements up or down the nodes of the index.

14. A computer-implemented method of managing a database contained in a storage facility, comprising:

structuring the database to have a table having an index to related rows, the index being a binary tree having a plurality of nodes, wherein lower-most child nodes include keys with key values associated with particular rows;

deleting at least a first, a second, and a third key in a first order, including

deleting the first key on a first side of the binary tree; and

deleting the second key, wherein the second key requires a fewer number of jumps from the first key than the number of jumps to the third key from the first key.

15. The method of claim 14, wherein jumps are movements up or down the plurality of nodes of the index.