Re: [WIP] [B-Tree] Retail IndexTuple deletion

On Sun, Jun 17, 2018 at 9:39 PM, Andrey V. Lepikhov
<a.lepikhov@postgrespro.ru> wrote:
> I have written a code for quick indextuple deletion from an relation by heap
> tuple TID. The code relate to "Retail IndexTuple deletion" enhancement of
> btree index on postgresql wiki [1].

I knew that somebody would eventually read that Wiki page.  :-)

> Now, index relation cleaning performs by vacuum which scan all index
> relation for dead entries sequentially, tuple-by-tuple. This simplistic and
> safe method can be significantly surpasses in the cases, than a number of
> dead entries is not large by retail deletions which uses index scans for
> search dead entries.

I assume that the lazy vacuum bulk delete thing is much faster for the
situation where you have many dead tuples in the index. However,
allowing a B-Tree index to accumulate so much bloat in the first place
often has consequences that cannot be reversed with anything less than
a REINDEX. It's true that "prevention is better than cure" for all
types of bloat. However, this could perhaps be as much as 100x more
important for B-Tree bloat, since we cannot place new tuples in any
place that is convenient. It's very different to bloat in the heap,
even at a high level.

> The code demands hold DEAD tuple storage until scan key will be created. In
> this version I add 'target_index_deletion_factor' option. If it more than 0,
> heap_page_prune() uses ItemIdMarkDead() instead of ItemIdSetDead() function
> for set DEAD flag and hold the tuple storage.

Makes sense.

> Next step is developing background worker which will collect pairs (tid,
> scankey) of DEAD tuples from heap_page_prune() function.

Makes sense.

> | n | t1, s  | t2, s  | speedup |
> |---|---------------------------|
> | 0 | 0.00003| 0.4476 | 1748.4  |
> | 1 | 0.00006| 0.5367 | 855.99  |
> | 2 | 0.0004 | 0.9804 | 233.99  |
> | 3 | 0.0048 | 1.6493 | 34.576  |
> | 4 | 0.5600 | 2.4854 | 4.4382  |
> | 5 | 3.3300 | 3.9555 | 1.2012  |
> | 6 | 17.700 | 5.6000 | 0.3164  |
> |---|---------------------------|
> in the table, t1 - measured execution time of lazy_vacuum_index() function
> by Quick-Vacuum strategy; t2 - measured execution time of
> lazy_vacuum_index() function by Lazy-Vacuum strategy;

The speedup looks promising. However, the real benefit should be in
query performance, especially when we have heavy contention. Very
eager retail index tuple deletion could help a lot there. It already
makes sense to make autovacuum extremely aggressive in this case, to
the point when it's running almost constantly. A more targeted cleanup
process that can run much faster could do the same job, but be much
more eager, and so be much more effective at *preventing* bloating of
the key space [1][2].

> Note, guaranteed allowable time of index scans (used for quick deletion)
> will be achieved by storing equal-key index tuples in physical TID order [2]
> with patch [3].

I now have greater motivation to develop that patch into a real project.

I bet that my heap-tid-sort patch will allow you to refine your
interface when there are many logical duplicates: You can create one
explicit scan key, but have a list of heap TIDs that need to be killed
within the range of matching index tuples. That could be a lot more
efficient in the event of many non-HOT updates, where most index tuple
values won't actually change. You can sort the list of heap TIDs that
you want to kill once, and then "merge" it with the tuples at the leaf
level as they are matched/killed. It should be safe to avoid
rechecking anything other than the heap TID values.

[1] http://pgeoghegan.blogspot.com/2017/07/postgresql-index-bloat-microscope.html
[2] https://www.postgresql.org/message-id/CAH2-Wzmf6intNY1ggiNzOziiO5Eq=DsXfeptODGxO=2j-i1NGQ@mail.gmail.com
-- 
Peter Geoghegan