Обсуждение: pgsql: Add TIDStore, to store sets of TIDs (ItemPointerData) efficientl

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

TIDStore is a data structure designed to efficiently store large sets
of TIDs. For TID storage, it employs a radix tree, where the key is
a block number, and the value is a bitmap representing offset
numbers. The TIDStore can be created on a DSA area and used by
multiple backend processes simultaneously.

There are potential future users such as tidbitmap.c, though it's very
likely the interface will need to evolve as we come to understand the
needs of different kinds of users. For example, we can support
updating the offset bitmap of existing values.

Currently, the TIDStore is not used for anything yet, aside from the
test code. But an upcoming patch will use it.

This includes a unit test module, in src/test/modules/test_tidstore.

Co-authored-by: John Naylor
Discussion: https://postgr.es/m/CAD21AoAfOZvmfR0j8VmZorZjL7RhTiQdVttNuC4W-Shdc2a-AA%40mail.gmail.com

Branch
------
master

Details
-------
https://git.postgresql.org/pg/commitdiff/30e144287a72529c9cd9fd6b07fe96eb8a1e270e

Modified Files
--------------
src/backend/access/common/Makefile                 |   1 +
src/backend/access/common/meson.build              |   1 +
src/backend/access/common/tidstore.c               | 463 +++++++++++++++++++++
src/include/access/tidstore.h                      |  49 +++
src/test/modules/Makefile                          |   1 +
src/test/modules/meson.build                       |   1 +
src/test/modules/test_tidstore/.gitignore          |   4 +
src/test/modules/test_tidstore/Makefile            |  23 +
.../test_tidstore/expected/test_tidstore.out       |  97 +++++
src/test/modules/test_tidstore/meson.build         |  33 ++
.../modules/test_tidstore/sql/test_tidstore.sql    |  65 +++
.../modules/test_tidstore/test_tidstore--1.0.sql   |  27 ++
src/test/modules/test_tidstore/test_tidstore.c     | 317 ++++++++++++++
.../modules/test_tidstore/test_tidstore.control    |   4 +
src/tools/pgindent/typedefs.list                   |   5 +
15 files changed, 1091 insertions(+)

On Thu, 21 Mar 2024 at 14:10, Masahiko Sawada <msawada@postgresql.org> wrote:
>
> Add TIDStore, to store sets of TIDs (ItemPointerData) efficiently.

> src/backend/access/common/tidstore.c               | 463 +++++++++++++++++++++

I was looking at this code and I saw the following:

/* choose the maxBlockSize to be no larger than 1/16 of max_bytes */
while (16 * maxBlockSize > max_bytes * 1024L)
    maxBlockSize >>= 1;

I saw the "* 1024L" and was confused by it.  "max_bytes * 1024L"
converts the number of bytes into "millibytes" ([1]), which I don't
think is correct.

Either "max_bytes" is a bad name for this variable or the * 1024L
should be removed.

David

[1] https://www.convertunits.com/info/millibyte

On Tue, Mar 26, 2024 at 7:16 AM David Rowley <dgrowleyml@gmail.com> wrote:
>
> On Thu, 21 Mar 2024 at 14:10, Masahiko Sawada <msawada@postgresql.org> wrote:
> >
> > Add TIDStore, to store sets of TIDs (ItemPointerData) efficiently.
>
> > src/backend/access/common/tidstore.c               | 463 +++++++++++++++++++++
>
> I was looking at this code and I saw the following:
>
> /* choose the maxBlockSize to be no larger than 1/16 of max_bytes */
> while (16 * maxBlockSize > max_bytes * 1024L)
>     maxBlockSize >>= 1;
>
> I saw the "* 1024L" and was confused by it.  "max_bytes * 1024L"
> converts the number of bytes into "millibytes" ([1]), which I don't
> think is correct.
>
> Either "max_bytes" is a bad name for this variable or the * 1024L
> should be removed.
>

Right. We discussed it on the original thread too[1]. Since we're
going to change the create API of TidStore, I'm going to fix it along
with the API changes[2]. Even if we don't make the API change, I'll
fix it individually.

Regards,

[1] https://www.postgresql.org/message-id/CANWCAZZTE-14ofsucofTuhFsfuDGBNf%3DNZb22TMYT8bxA41oQQ%40mail.gmail.com
[2] https://www.postgresql.org/message-id/CAD21AoAxXGf7FbuA9jvx%2BXUFrEJUz9JNOmkxF8SLppOOOvhBtg%40mail.gmail.com
Please see v79-0003-Rethink-create-and-attach-APIs-of-shared-TidStor.patch.

--
Masahiko Sawada
Amazon Web Services: https://aws.amazon.com

On Tue, Mar 26, 2024 at 9:36 AM Masahiko Sawada <sawada.mshk@gmail.com> wrote:
>
> On Tue, Mar 26, 2024 at 7:16 AM David Rowley <dgrowleyml@gmail.com> wrote:
> >
> > Either "max_bytes" is a bad name for this variable or the * 1024L
> > should be removed.
> >
>
> Right. We discussed it on the original thread too[1]. Since we're
> going to change the create API of TidStore, I'm going to fix it along
> with the API changes[2]. Even if we don't make the API change, I'll
> fix it individually.

v79 still has the offending multiplier, btw. Those two things are
unrelated anyway, so I don't see a reason to hold off making this
small fix.

On Tue, Mar 26, 2024 at 12:22 PM John Naylor <johncnaylorls@gmail.com> wrote:
>
> On Tue, Mar 26, 2024 at 9:36 AM Masahiko Sawada <sawada.mshk@gmail.com> wrote:
> >
> > On Tue, Mar 26, 2024 at 7:16 AM David Rowley <dgrowleyml@gmail.com> wrote:
> > >
> > > Either "max_bytes" is a bad name for this variable or the * 1024L
> > > should be removed.
> > >
> >
> > Right. We discussed it on the original thread too[1]. Since we're
> > going to change the create API of TidStore, I'm going to fix it along
> > with the API changes[2]. Even if we don't make the API change, I'll
> > fix it individually.
>
> v79 still has the offending multiplier, btw. Those two things are
> unrelated anyway, so I don't see a reason to hold off making this
> small fix.

Okay, I'll fix them shortly.

Regards,

--
Masahiko Sawada
Amazon Web Services: https://aws.amazon.com