The Curse of Deleted Key Placeholders

This week, Patrice Perrot from PROGINOV joins Paul Koufalis to talk about deleted key placeholders.

After a massive data purge, you run idxcompact, right? You want to remove all those deleted key placeholders polluting your index.

Guess what? Idxcompact doesn't remove those placeholders the way you think it does.

What is a Deleted Key Placeholder?

From the Progress Documentation:

When a record is deleted, if there is a unique index, a delete place holder is put in the place of the RECID for the deleted record until the transaction commits. This is done so that another transaction running at the same time cannot add the same unique entry, which would thereby prevent the deleting transaction from rolling back.

Translated, this means that the entry in the unique index still exists after deletion. It will be read (and ignored) in subsequent queries using that index, and you may do many more index reads than necessary when querying the table.

Why Does It Matter?

When querying the table using the index in question, the placeholders will be read along with the valid index keys. For example, if you have a table with 100M records and you delete 90M records, a subsequent "FOR EACH TABLE..." will still require more than 100M index reads to extract the remaining 10M records. 

Here's a simple real-world example of a relatively small table (about 6,000 records) that has hundreds of records created and deleted every day. Notice the index reads are more than double the record reads.

How Can You Check Your DB?

First, compare table reads to index reads, as in the example above, and take note of tables that have high index:record read ratios. These are your candidates.

Second, run an index block report on the suspected indexes and extract the "Number of entries" column from the leaf blocks (leaf blocks contain ROWIDs of records):

Finally, count the total number of entries in the leaf blocks and compare it to the number of records in the table, per DB Analysis. 

If the number of leaf entries is greater than the number of records, then you have deleted key placeholders!

CAREFUL: if the number of leaf entries is less than the number of records, then you are the victim of an unfortunate Progress bug. Sorry!

Unfortunately, even this method is not 100%. Index leaf blocks that have only deleted key placeholders are ignored by the index block report, but are still in the index tree and will be read when querying the associated table. 

How Are These Placeholders Removed?

That's the problem. They are not removed except in very specific circumstances.

What the documentation says is that when the index block is modified as part of a normal day-to-day operation occurring after the deletion, the placeholders are removed before the block is written to disk. This does not seem to occur in practice.

We also expect the idxcompact utility to remove these placeholders, as documented, but that doesn't always happen either. 

Index blocks with a mix of valid entries and placeholders, that are already filled more than the target fill percentage, are simply ignored by idxcompact.

 The only time these placeholders are consistently removed are:

1. During idxcompact, if the index block fill percentage is below the target threshold.
2. Insertion of new index entries force a block split, which leads to option A: the two new blocks end up being filled at roughly 50%, and they will be cleaned in subsequent idxcompact runs if the target fill rate is greater than 50%.
3. Insertion of a new record in the table, which triggers the removal of a block with 100% deleted key placeholders. That block is removed from the index B-tree and placed on the free chain.
4. During idxmove, only valid entries are moved to the new area, effectively eliminating the placeholders. BUT...
   • no create/update/delete operations are allowed on the table during the tablemove
   • the move is processed as one transaction, creating a huge volume of AI and BI notes (up to 10X the size of the index)
   • idxmove is based on the primary index of the table, so you will have a percent utilization on the moved index between 50% and 100%

What Can You Do About It?

Practically, there is nothing we can do about it. There are some crazy solutions to force a block split, but you probably don't want to use these in a production database. 

There is one thing you can do: vote for this enhancement request, which will improve the idxcompact process to scan and clean all placeholders from all blocks. You will need to login with your free ProgressID to vote.