Horton

Re: [PoC] Improve dead tuple storage for lazy vacuum

John Naylor <john.naylor@enterprisedb.com>

View thread View on postgr.es
From: John Naylor <john.naylor@enterprisedb.com>
To: Masahiko Sawada <sawada.mshk@gmail.com>
Cc: Nathan Bossart <nathandbossart@gmail.com>, Andres Freund <andres@anarazel.de>, Matthias van de Meent <boekewurm+postgres@gmail.com>, Yura Sokolov <y.sokolov@postgrespro.ru>, PostgreSQL-development <pgsql-hackers@postgresql.org>
Date: 2022-10-27T03:21:40Z
Lists: pgsql-hackers 
On Thu, Oct 27, 2022 at 9:11 AM Masahiko Sawada <sawada.mshk@gmail.com>
wrote:
>
> True. I'm going to start with 6 bytes and will consider reducing it to
> 5 bytes.

Okay, let's plan on 6 for now, so we have the worst-case sizes up front. As
discussed, I will attempt the size class decoupling after v8 and see how it
goes.

> Encoding the kind in a pointer tag could be tricky given DSA

If it turns out to be unworkable, that's life. If it's just tricky, that
can certainly be put off for future work. I hope to at least test it out
with local memory.

> support so currently I'm thinking to pack the node kind and node
> capacity classes to uint8.

That won't work, if we need 128 for capacity, leaving no bits left. I want
the capacity to be a number we can directly compare with the count (we
won't ever need to store 256 because that node will never grow). Also,
further to my last message, we need to access the kind quickly, without
more cycles.

> I've made some progress on investigating DSA support. I've written
> draft patch for that and regression tests passed. I'll share it as a
> separate patch for discussion with v8 radix tree patch.

Great!

> While implementing DSA support, I realized that we may not need to use
> pointer tagging to distinguish between backend-local address or
> dsa_pointer. In order to get a backend-local address from dsa_pointer,
> we need to pass dsa_area like:

I was not clear -- when I see how much code changes to accommodate DSA
pointers, I imagine I will pretty much know the places that would be
affected by tagging the pointer with the node kind.

Speaking of tests, there is currently no Meson support, but tests pass
because this library is not used anywhere in the backend yet, and
apparently the CI Meson builds don't know to run the regression test? That
will need to be done too. However, it's okay to keep the benchmarking
module in autoconf, since it won't be committed.

> > +static inline void
> > +chunk_children_array_copy(uint8 *src_chunks, rt_node **src_children,
> > +             uint8 *dst_chunks, rt_node **dst_children, int count)
> > +{
> > + memcpy(dst_chunks, src_chunks, sizeof(uint8) * count);
> > + memcpy(dst_children, src_children, sizeof(rt_node *) * count);
> > +}
> >
> > gcc generates better code with something like this (but not hard-coded)
at the top:
> >
> >     if (count > 4)
> >         pg_unreachable();

Actually it just now occurred to me there's a bigger issue here: *We* know
this code can only get here iff count==4, so why doesn't the compiler know
that? I believe it boils down to

static rt_node_kind_info_elem rt_node_kind_info[RT_NODE_KIND_COUNT] = {

In the assembly, I see it checks if there is room in the node by doing a
runtime lookup in this array, which is not constant. This might not be
important just yet, because I want to base the check on the proposed node
capacity instead, but I mention it as a reminder to us to make sure we take
all opportunities for the compiler to propagate constants.

--
John Naylor
EDB: http://www.enterprisedb.com

Commits

  1. radixtree: Fix SIGSEGV at update of embeddable value to non-embeddable.

  2. Get rid of anonymous struct

  3. Teach radix tree to embed values at runtime

  4. Teach TID store to skip bitmap for small numbers of offsets

  5. Use bump context for TID bitmaps stored by vacuum

  6. Fix alignment of stack variable

  7. Use TidStore for dead tuple TIDs storage during lazy vacuum.

  8. Rethink create and attach APIs of shared TidStore.

  9. Fix inconsistent function prototypes with function definitions.

  10. Fix a calculation in TidStoreCreate().

  11. Fix potential integer handling issue in radixtree.h.

  12. Add TIDStore, to store sets of TIDs (ItemPointerData) efficiently.

  13. Fix link error for test_radixtree module on Windows

  14. Blind attempt to fix ODR violations

  15. Fix incorrect format specifier for int64

  16. Fix redefinition of typedefs

  17. Add template for adaptive radix tree

  18. Fix signedness error in 9f225e992 for gcc

  19. Introduce helper SIMD functions for small byte arrays

  20. Optimize vacuuming of relations with no indexes.

  21. Add bound check before bsearch() for performance

  22. Allocate consecutive blocks during parallel seqscans