Storing a key value to a deleted row based on key range density

Patent metadata

Field	Value
Publication number	US-9323798-B2
Application number	US-201313740298-A
Country	US
Kind code	B2
Filing date	Jan 14, 2013
Priority date	Jan 14, 2013
Publication date	Apr 26, 2016
Grant date	Apr 26, 2016

Abstract

In an embodiment, a first key value is received. A plurality of candidate rows are found in a database table, wherein the plurality of candidate rows are deleted. For the plurality of candidate rows, a plurality of respective impacts on a plurality of respective densities of each of other key values that are stored within a first key range of the first key value are calculated. For the plurality of candidate rows, a plurality of function results of the plurality of respective impacts on the plurality of respective densities are calculated. A selected candidate row of the plurality of candidate rows with a smallest function result of the plurality of function results of the plurality of respective impacts on the plurality of respective densities is selected. The first key value is stored to the selected candidate row.

First claim

What is claimed is:

1. A method comprising:
receiving a first key value to be stored to a database table;
responsive to receiving the first key value, finding a plurality of candidate rows in the database table, wherein no row of the plurality of candidate rows contains a valid key value, and wherein the first key value is capable of being stored in any row of the plurality of candidate rows;
calculating, for each candidate row of the plurality of candidate rows, a corresponding plurality of respective impacts on a plurality of respective current densities of each of other key values that are stored within a first key range of the first key value,
wherein the calculating the plurality of respective impacts comprises calculating potential densities of other key ranges minus the plurality of respective current densities of the other key ranges, wherein the first key range and the other key ranges overlap;
for each candidate row of the plurality of candidate rows, calculating a respective function result of the corresponding plurality of respective impacts on the plurality of respective current densities;
selecting a candidate row of the plurality of candidate rows with a smallest function result of the corresponding plurality of respective impacts on the plurality of respective current densities among all function results of the plurality of candidate rows;
storing the first key value to the selected candidate row, wherein the storing further comprises:
updating a row containing a valid key value with the first key value; and
moving the updated row to the selected candidate row.

2. The method of claim 1 , wherein the plurality of candidate rows are selected from a group consisting of: all rows without a valid key value within the first key range of the first key value, a sample of all rows without a valid key value within the first key range of the first key value, all rows without a valid key value that are within a threshold value of the first key range of the first key value, and wherein the calculating the plurality of function results of the plurality of respective impacts on the plurality of respective current densities further comprises calculating a plurality of sums of the plurality of respective impacts on the plurality of respective current densities.

3. The method of claim 1 , wherein the calculating the corresponding plurality of respective impacts further comprises:
calculating ((a respective last relative record number of the other key ranges minus a respective first relative record number of the other key ranges plus one minus a respective deleted count of the other key ranges, as impacted by potential insertion of the first key value) divided by (a respective key count of the other key ranges)) minus the plurality of current densities of the other key ranges.

4. The method of claim 1 , further comprising:
if the first key range of the first key value does not have any rows without a valid key value, inserting the first key value to a row without a valid key value that is closest to the first key range.

5. The method of claim 1 , further comprising:
periodically searching for a found key range with a smallest density and moving an endpoint row of the found key range to a median row without a valid key value within the found key range.

6. The method of claim 1 , further comprising:
periodically searching for a found key range with a largest deleted count and moving an endpoint row of the found key range to a median row without a valid key value within the found key range.

7. The method of claim 1 , further comprising:
performing the calculating the plurality of respective impacts, the calculating the plurality of function results, the selecting the selected candidate row, and the storing the first key value to the selected candidate row if the first key range of the first key value comprises at least one row without a valid key value.

8. A non-transitory computer-readable storage medium encoded with instructions, wherein the instruction when executed comprise:
receiving a first key value to be stored to a database table;
responsive to receiving the first key value, finding a plurality of candidate rows in the database table, wherein no row of the plurality of candidate rows contains a valid key value, and wherein the first key value is capable of being stored in any row of the plurality of candidate rows;
calculating, for each candidate row of the plurality of candidate rows, a corresponding plurality of respective impacts on a plurality of respective current densities of each of other key values that are stored within a first key range of the first key value, wherein the calculating the plurality of respective impacts comprises calculating potential densities of other key ranges minus the plurality of respective current densities of the other key ranges, wherein the first key range and the other key ranges overlap;
for each candidate row of the plurality of candidate rows, calculating a plurality of respective function results result of the corresponding plurality of respective impacts on the plurality of respective current densities;
selecting a candidate row of the plurality of candidate rows with a smallest respective function result of the plurality of function results of the corresponding plurality of respective impacts on the plurality of respective current densities among all function results of the plurality of candidate rows; and
storing the first key value to the selected candidate row, wherein the storing further comprises:
updating a row containing a valid key value with the first key value; and
moving the updated row to the selected candidate row.

9. The non-transitory computer-readable storage medium of claim 8 , wherein the plurality of candidate rows are selected from a group consisting of: all rows without a valid key value within the first key range of the first key value, a sample of all rows without a valid key value within the first key range of the first key value, and all rows without a valid key value that are within a threshold value of the first key range of the first key value, and wherein the calculating the plurality of function results of the plurality of respective impacts on the plurality of respective current densities further comprises calculating a plurality of sums of the plurality of respective impacts on the plurality of respective current densities.

10. The non-transitory computer-readable storage medium of claim 8 , wherein the calculating the corresponding plurality of respective impacts further comprises:
calculating ((a respective last relative record number of the other key ranges minus a respective first relative record number of the other key ranges plus one minus a respective deleted count of the other key ranges, as impacted by potential insertion of the first key value) divided by (a respective key count of the other key ranges)) minus the plurality of current densities of the other key ranges.

11. The non-transitory computer-readable storage medium of claim 8 , further comprising:
if the first key range of the first key value does not have any rows without a valid key value, inserting the first key value to a row without a valid key value that is closest to the first key range.

12. The non-transitory computer-readable storage medium of claim 8 , further comprising:
periodically searching for a found key range with a smallest density and moving an endpoint row of the found key range to a median row without a valid key value within the found key range;
periodically searching for a found key range with a largest deleted count and moving an endpoint row of the found key range to a median row

Assignees

• IBM
• IBM

Inventors

• Konik Rafal P
• Mittelstadt Roger A
• Muras Brian R
• Theuer Mark W

Classifications

• G06F16/23 Primary

  Updating · CPC title

• G06F17/30345 Primary

  Physics · mapped topic

• G06F16/2228 Primary

  Indexing structures · CPC title

• G06F16/245

  Query processing · CPC title

• G06F16/284

  Relational databases · CPC title