Database management delete efficiency

• US 9,229,961 B2
• Filed: 03/12/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/795,262
• Publication Number:
  US 20140229429A1
• Time in Patent Office: 1,029 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 system comprising:

one or more processors; and

program code including a query optimizer, the program code configured to be executed by the one or more processors to process a database query, the program code configured to;

structure a database to have a plurality of database tables having an indexes associated with one or more rows and having one or more index keys with index key values associated with particular rows of the one or more rows, wherein the indexes are organized as a search tree; and

delete rows in the database tables for database maintenance in real-time by deleting index keys of the one or more rows in the database tables, wherein;

the database is managed by deleting one or more index keys in the database tables,

the deleting the index keys of the one or more index keys in the database further includes deleting index keys of the one or more index keys in the one or more indexes related to the rows of the one or more rows in an order such that corresponding rows of the one or more rows are deleted based on a comparatively close relationship to the one or more index keys, and

the comparatively close relationship is a minimum number of jumps necessary to get from a row associated with a near key to a row associated with a search key.

2. The system of claim 1, wherein the order rows are deleted includes at least one of a hierarchical order of index keys in indexes, a spatial locality order of index keys in indexes which includes prioritizing an index key that is in a nearby location, a temporal locality order of index keys in indexes which includes prioritizing an index key that is in a memory, and a frequency order of index keys in indexes which includes prioritizing an index key that is frequently accessed to a memory.

3. The system of claim 1, wherein the order rows are deleted includes at least one of a volume order of index keys in indexes which includes prioritizing index keys in a first index that has a greater number of rows than a second index and a cardinality order of index keys in indexes which includes prioritizing index keys in a third index that has a greater quantity of unique values than a fourth index.

4. A computer program product for processing a database query, the computer program product comprising a non-transitory computer readable storage medium having program code embodied therewith, the program code comprising computer readable program code that is configured to:

structure a database to have a plurality of database tables having an indexes associated with one or more rows and having one or more index keys with index key values associated with particular rows of the one or more rows, wherein the indexes are organized as a search tree; and

delete rows in the database tables for database maintenance in real-time by deleting index keys of the one or more rows in the database tables, wherein;

the database is managed by deleting one or more index keys in the database tables,

the deleting the index keys of the one or more index keys in the database further includes deleting index keys of the one or more index keys in the one or more indexes related to the rows of the one or more rows in an order such that corresponding rows of the one or more rows are deleted based on a comparatively close relationship to the one or more index keys, and

the comparatively close relationship is a minimum number of jumps necessary to get from a row associated with a near key to a row associated with a search key.

5. The computer program product of claim 4, wherein the order rows are deleted includes at least one of a hierarchical order of index keys, a spatial locality order of index keys, which includes prioritizing an index key that is in a nearby location, a temporal locality order of index keys, which includes prioritizing an index key that is in a memory, and a frequency order of index keys, which includes prioritizing an index key that is frequently accessed to a memory.

6. The computer program product of claim 4, wherein the order rows are deleted includes at least one of a volume order of index keys, which includes prioritizing index keys in a first index that has a greater number of rows than a second index and a cardinality order of index keys, which includes prioritizing index keys in a third index that has a greater quantity of unique values than a fourth index.

7. The computer program product of claim 4, wherein the one side of the tree is a leftmost side of the tree.

8. The computer program product of claim 4, wherein the one side of the tree is a rightmost side of the tree.

9. The computer program product of claim 4, wherein jumps are movements between nodes up or down the index.

10. The computer program product of claim 4, wherein the search tree is a binary search tree.

11. A system comprising:

one or more processors; and

program code including a query optimizer, the program code configured to be executed by the one or more processors to process a database query, the program code configured to;

structure a 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

delete 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.

12. The system of claim 11, wherein the one side of the tree is a leftmost side of the tree.

13. The system of claim 11, wherein the one side of the tree is a rightmost side of the tree.

14. The system of claim 11, wherein jumps are movements between nodes up or down the index.

15. The system of claim 11, wherein the search tree is a binary search tree.