pg.ddx.io pgsql-committers@postgresql.org mailing list archive
help / color / mirror / Atom feedpgbouncer - pgbouncer: v1.3.1rc1
14+ messages / 7 participants
[nested] [flat]
* pgbouncer - pgbouncer: v1.3.1rc1
@ 2009-06-26 11:28 User Mkz <mkz@pgfoundry.org>
0 siblings, 0 replies; 14+ messages in thread
From: mkz@pgfoundry.org @ 2009-06-26 11:28 UTC (permalink / raw)
To: pgsql-committers
Log Message:
-----------
v1.3.1rc1
Modified Files:
--------------
pgbouncer:
NEWS (r1.36 -> r1.37)
(http://cvs.pgfoundry.org/cgi-bin/cvsweb.cgi/pgbouncer/pgbouncer/NEWS?r1=1.36&r2=1.37)
configure.ac (r1.54 -> r1.55)
(http://cvs.pgfoundry.org/cgi-bin/cvsweb.cgi/pgbouncer/pgbouncer/configure.ac?r1=1.54&r2=1.55)
pgbouncer/debian:
changelog (r1.19 -> r1.20)
(http://cvs.pgfoundry.org/cgi-bin/cvsweb.cgi/pgbouncer/pgbouncer/debian/changelog?r1=1.19&r2=1.20)
^ permalink raw reply [nested|flat] 14+ messages in thread
* pgsql: Add template for adaptive radix tree
@ 2024-03-07 05:49 John Naylor <john.naylor@postgresql.org>
0 siblings, 2 replies; 14+ messages in thread
From: John Naylor @ 2024-03-07 05:49 UTC (permalink / raw)
To: pgsql-committers@lists.postgresql.org
Add template for adaptive radix tree
This implements a radix tree data structure based on the design in
"The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases"
by Viktor Leis, Alfons Kemper, and ThomasNeumann, 2013. The main
technique that makes it adaptive is using several different node types,
each with a different capacity of elements, and a different algorithm
for accessing them. The nodes start small and grow/shrink as needed.
The main advantage over hash tables is efficient sorted iteration and
better memory locality when successive keys are lexicographically
close together. The implementation currently assumes 64-bit integer
keys, and traversing the tree is in general slower than a linear
probing hash table, so this is not a general-purpose associative array.
The paper describes two other techniques not implemented here,
namely "path compression" and "lazy expansion". These can further
reduce memory usage and speed up traversal, but the former would add
significant complexity and the latter requires storing the full key
with the value. We do trivially compress the path when leading bytes
of the key are zeros, however.
For value storage, we use "combined pointer/value slots", as
recommended in the paper. Values of size equal or smaller than the the
platform's pointer type are stored in the array of child pointers in
the last level node, while larger values are each stored in a separate
allocation. This is for now fixed at compile time, but it would be
fairly trivial to allow determining at runtime how variable-length
values are stored.
One innovation in our implementation compared to the ART paper is
decoupling the notion of node "size class" from "kind". The size
classes within a given node kind have the same underlying type, but
a variable capacity for children, so we can introduce additional node
sizes with little additional code.
To enable different use cases to specialize for different value types
and for shared/local memory, we use macro-templatized code generation
in the same manner as simplehash.h and sort_template.h.
Future commits will use this infrastructure for storing TIDs.
Patch by Masahiko Sawada and John Naylor, but a substantial amount of
credit is due to Andres Freund, whose proof-of-concept was a valuable
source of coding idioms and awareness of performance pitfalls, and
who reviewed earlier versions.
Discussion: https://postgr.es/m/CAD21AoAfOZvmfR0j8VmZorZjL7RhTiQdVttNuC4W-Shdc2a-AA%40mail.gmail.com
Branch
------
master
Details
-------
https://git.postgresql.org/pg/commitdiff/ee1b30f128d8f63a5184d2bcf1c48a3efc3fcbf9
Modified Files
--------------
src/backend/utils/mmgr/dsa.c | 13 +
src/include/lib/radixtree.h | 3009 ++++++++++++++++++++
src/include/utils/dsa.h | 1 +
src/test/modules/Makefile | 1 +
src/test/modules/meson.build | 1 +
src/test/modules/test_radixtree/.gitignore | 4 +
src/test/modules/test_radixtree/Makefile | 23 +
.../test_radixtree/expected/test_radixtree.out | 41 +
src/test/modules/test_radixtree/meson.build | 34 +
.../modules/test_radixtree/sql/test_radixtree.sql | 7 +
.../modules/test_radixtree/test_radixtree--1.0.sql | 8 +
src/test/modules/test_radixtree/test_radixtree.c | 473 +++
.../modules/test_radixtree/test_radixtree.control | 4 +
src/tools/pgindent/typedefs.list | 1 +
14 files changed, 3620 insertions(+)
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: pgsql: Add template for adaptive radix tree
@ 2024-03-07 06:08 Tom Lane <tgl@sss.pgh.pa.us>
parent: John Naylor <john.naylor@postgresql.org>
1 sibling, 1 reply; 14+ messages in thread
From: Tom Lane @ 2024-03-07 06:08 UTC (permalink / raw)
To: John Naylor <john.naylor@postgresql.org>; +Cc: pgsql-committers@lists.postgresql.org
John Naylor <john.naylor@postgresql.org> writes:
> This implements a radix tree data structure based on the design in
> "The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases"
> by Viktor Leis, Alfons Kemper, and ThomasNeumann, 2013.
Hm ... do we know that this is not patent-encumbered technology?
Commits citing such specific prior art make me nervous.
regards, tom lane
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: pgsql: Add template for adaptive radix tree
@ 2024-03-07 06:14 John Naylor <johncnaylorls@gmail.com>
parent: Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 14+ messages in thread
From: John Naylor @ 2024-03-07 06:14 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: John Naylor <john.naylor@postgresql.org>; pgsql-committers@lists.postgresql.org
On Thu, Mar 7, 2024 at 1:08 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> John Naylor <john.naylor@postgresql.org> writes:
> > This implements a radix tree data structure based on the design in
> > "The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases"
> > by Viktor Leis, Alfons Kemper, and ThomasNeumann, 2013.
>
> Hm ... do we know that this is not patent-encumbered technology?
> Commits citing such specific prior art make me nervous.
There are several open source implementations in a variety of
languages, so I assumed not.
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: pgsql: Add template for adaptive radix tree
@ 2024-03-07 06:32 Tom Lane <tgl@sss.pgh.pa.us>
parent: John Naylor <johncnaylorls@gmail.com>
0 siblings, 1 reply; 14+ messages in thread
From: Tom Lane @ 2024-03-07 06:32 UTC (permalink / raw)
To: John Naylor <johncnaylorls@gmail.com>; +Cc: John Naylor <john.naylor@postgresql.org>; pgsql-committers@lists.postgresql.org
John Naylor <johncnaylorls@gmail.com> writes:
> On Thu, Mar 7, 2024 at 1:08 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Hm ... do we know that this is not patent-encumbered technology?
>> Commits citing such specific prior art make me nervous.
> There are several open source implementations in a variety of
> languages, so I assumed not.
Are any of those implementations used in places that might
entice a patent troll to come after them?
(If you think Postgres isn't an inviting target for patent
trolls, you're wrong. We've avoided getting sued so far,
but man this topic scares me.)
regards, tom lane
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: pgsql: Add template for adaptive radix tree
@ 2024-03-07 06:59 John Naylor <johncnaylorls@gmail.com>
parent: Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 14+ messages in thread
From: John Naylor @ 2024-03-07 06:59 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: John Naylor <john.naylor@postgresql.org>; pgsql-committers@lists.postgresql.org
On Thu, Mar 7, 2024 at 1:32 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> John Naylor <johncnaylorls@gmail.com> writes:
> > On Thu, Mar 7, 2024 at 1:08 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> >> Hm ... do we know that this is not patent-encumbered technology?
> >> Commits citing such specific prior art make me nervous.
>
> > There are several open source implementations in a variety of
> > languages, so I assumed not.
>
> Are any of those implementations used in places that might
> entice a patent troll to come after them?
>
> (If you think Postgres isn't an inviting target for patent
> trolls, you're wrong. We've avoided getting sued so far,
> but man this topic scares me.)
Understandably so. FWIW, the use case proposed by the authors was for
secondary indexes within in-memory databases, not as a type of
associative array. I'm unable to find patents for the thing itself,
but IANAL. I believe I've been in contact with some of the same
authors about a different subject, and they seemed open to people
trying to implement their ideas (it was a different paper, to be sure,
and unfortunately I no longer email account).
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: pgsql: Add template for adaptive radix tree
@ 2024-03-07 09:36 Alvaro Herrera <alvherre@alvh.no-ip.org>
parent: John Naylor <johncnaylorls@gmail.com>
0 siblings, 1 reply; 14+ messages in thread
From: Alvaro Herrera @ 2024-03-07 09:36 UTC (permalink / raw)
To: John Naylor <johncnaylorls@gmail.com>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; John Naylor <john.naylor@postgresql.org>; pgsql-committers@lists.postgresql.org
On 2024-Mar-07, John Naylor wrote:
> Understandably so. FWIW, the use case proposed by the authors was for
> secondary indexes within in-memory databases, not as a type of
> associative array. I'm unable to find patents for the thing itself,
> but IANAL. I believe I've been in contact with some of the same
> authors about a different subject, and they seemed open to people
> trying to implement their ideas (it was a different paper, to be sure,
> and unfortunately I no longer email account).
Well, surely we can email them. Their profiles show they're still
active.
https://db.in.tum.de/people/sites/kemper/?lang=en
https://db.in.tum.de/people/sites/neumann/?lang=en
https://db.in.tum.de/people/sites/leis/?lang=en
--
Álvaro Herrera 48°01'N 7°57'E — https://www.EnterpriseDB.com/
"Pido que me den el Nobel por razones humanitarias" (Nicanor Parra)
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: pgsql: Add template for adaptive radix tree
@ 2024-03-07 09:47 John Naylor <johncnaylorls@gmail.com>
parent: Alvaro Herrera <alvherre@alvh.no-ip.org>
0 siblings, 1 reply; 14+ messages in thread
From: John Naylor @ 2024-03-07 09:47 UTC (permalink / raw)
To: Alvaro Herrera <alvherre@alvh.no-ip.org>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; John Naylor <john.naylor@postgresql.org>; pgsql-committers@lists.postgresql.org
On Thu, Mar 7, 2024 at 4:36 PM Alvaro Herrera <alvherre@alvh.no-ip.org> wrote:
>
> Well, surely we can email them. Their profiles show they're still
> active.
> https://db.in.tum.de/people/sites/kemper/?lang=en
> https://db.in.tum.de/people/sites/neumann/?lang=en
> https://db.in.tum.de/people/sites/leis/?lang=en
I thought the same, and have sent them a message after completing some
research into remaining buildfarm failures.
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: pgsql: Add template for adaptive radix tree
@ 2024-03-07 19:09 Andrew Dunstan <andrew@dunslane.net>
parent: John Naylor <john.naylor@postgresql.org>
1 sibling, 0 replies; 14+ messages in thread
From: Andrew Dunstan @ 2024-03-07 19:09 UTC (permalink / raw)
To: John Naylor <john.naylor@postgresql.org>; pgsql-committers@lists.postgresql.org
On 2024-03-07 Th 00:49, John Naylor wrote:
> Add template for adaptive radix tree
drongo and fairywren don't like this, See e.g.
<https://buildfarm.postgresql.org/cgi-bin/show_log.pl?nm=drongo&dt=2024-03-07%2016%3A51%3A00;
cheers
andrew
--
Andrew Dunstan
EDB: https://www.enterprisedb.com
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: pgsql: Add template for adaptive radix tree
@ 2024-03-08 00:47 John Naylor <johncnaylorls@gmail.com>
parent: John Naylor <johncnaylorls@gmail.com>
0 siblings, 1 reply; 14+ messages in thread
From: John Naylor @ 2024-03-08 00:47 UTC (permalink / raw)
To: Alvaro Herrera <alvherre@alvh.no-ip.org>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; John Naylor <john.naylor@postgresql.org>; pgsql-committers@lists.postgresql.org
On Thu, Mar 7, 2024 at 4:47 PM John Naylor <johncnaylorls@gmail.com> wrote:
>
> On Thu, Mar 7, 2024 at 4:36 PM Alvaro Herrera <alvherre@alvh.no-ip.org> wrote:
> >
> > Well, surely we can email them. Their profiles show they're still
> > active.
> > https://db.in.tum.de/people/sites/kemper/?lang=en
> > https://db.in.tum.de/people/sites/neumann/?lang=en
> > https://db.in.tum.de/people/sites/leis/?lang=en
>
> I thought the same, and have sent them a message after completing some
> research into remaining buildfarm failures.
The authors have confirmed they did not patent adaptive radix tree.
Now, after I get some coffee I'll look into the Windows failures.
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: pgsql: Add template for adaptive radix tree
@ 2024-03-08 03:29 David Rowley <dgrowleyml@gmail.com>
parent: John Naylor <johncnaylorls@gmail.com>
0 siblings, 1 reply; 14+ messages in thread
From: David Rowley @ 2024-03-08 03:29 UTC (permalink / raw)
To: John Naylor <johncnaylorls@gmail.com>; +Cc: Alvaro Herrera <alvherre@alvh.no-ip.org>; Tom Lane <tgl@sss.pgh.pa.us>; John Naylor <john.naylor@postgresql.org>; pgsql-committers@lists.postgresql.org
On Fri, 8 Mar 2024 at 13:48, John Naylor <johncnaylorls@gmail.com> wrote:
> Now, after I get some coffee I'll look into the Windows failures.
I had a look at this and the attached fixes the broken build on MSVC for me.
I didn't take the time to fully understand it, but I did also try
PGDLLEXPORT and that *didn't* fix it. My guess is it's because these
are function pointer variables rather than functions.
git grep -E "PGDLLIMPORT.*\("
does not show anything else that does this for function pointers.
I did try commenting out "#define TRY_POPCNT_FAST 1" and the build still works.
That was the extent of my research.
David
Attachments:
fix_popcount64_link_issue_on_windows.patch (text/plain, 622B) download
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index 799f70d052..46bf4f0103 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -300,8 +300,8 @@ pg_ceil_log2_64(uint64 num)
#ifdef TRY_POPCNT_FAST
/* Attempt to use the POPCNT instruction, but perform a runtime check first */
-extern int (*pg_popcount32) (uint32 word);
-extern int (*pg_popcount64) (uint64 word);
+extern PGDLLIMPORT int (*pg_popcount32) (uint32 word);
+extern PGDLLIMPORT int (*pg_popcount64) (uint64 word);
#else
/* Use a portable implementation -- no need for a function pointer. */
* Re: pgsql: Add template for adaptive radix tree
@ 2024-03-08 03:37 John Naylor <johncnaylorls@gmail.com>
parent: David Rowley <dgrowleyml@gmail.com>
0 siblings, 1 reply; 14+ messages in thread
From: John Naylor @ 2024-03-08 03:37 UTC (permalink / raw)
To: David Rowley <dgrowleyml@gmail.com>; +Cc: Alvaro Herrera <alvherre@alvh.no-ip.org>; Tom Lane <tgl@sss.pgh.pa.us>; John Naylor <john.naylor@postgresql.org>; pgsql-committers@lists.postgresql.org
On Fri, Mar 8, 2024 at 10:29 AM David Rowley <dgrowleyml@gmail.com> wrote:
>
> On Fri, 8 Mar 2024 at 13:48, John Naylor <johncnaylorls@gmail.com> wrote:
> > Now, after I get some coffee I'll look into the Windows failures.
>
> I had a look at this and the attached fixes the broken build on MSVC for me.
>
> I didn't take the time to fully understand it, but I did also try
> PGDLLEXPORT and that *didn't* fix it. My guess is it's because these
> are function pointer variables rather than functions.
Thanks, I was getting close to committing a hackish workaround -- this
seems better!
^ permalink raw reply [nested|flat] 14+ messages in thread
* Re: pgsql: Add template for adaptive radix tree
@ 2024-03-08 03:42 David Rowley <dgrowleyml@gmail.com>
parent: John Naylor <johncnaylorls@gmail.com>
0 siblings, 1 reply; 14+ messages in thread
From: David Rowley @ 2024-03-08 03:42 UTC (permalink / raw)
To: John Naylor <johncnaylorls@gmail.com>; +Cc: Alvaro Herrera <alvherre@alvh.no-ip.org>; Tom Lane <tgl@sss.pgh.pa.us>; John Naylor <john.naylor@postgresql.org>; pgsql-committers@lists.postgresql.org
On Fri, 8 Mar 2024 at 16:37, John Naylor <johncnaylorls@gmail.com> wrote:
> Thanks, I was getting close to committing a hackish workaround -- this
> seems better!
ok cool. I also noticed a typo. Maybe worth fixing that at the same time?
Attached.
David
Attachments:
typo_fix.patch (text/plain, 529B) download
diff --git a/src/test/modules/test_radixtree/test_radixtree.c b/src/test/modules/test_radixtree/test_radixtree.c
index 8010e0a1f1..d301c60d00 100644
--- a/src/test/modules/test_radixtree/test_radixtree.c
+++ b/src/test/modules/test_radixtree/test_radixtree.c
@@ -1,7 +1,7 @@
/*--------------------------------------------------------------------------
*
* test_radixtree.c
- * Test module for adapive radix tree.
+ * Test module for adaptive radix tree.
*
* Copyright (c) 2024, PostgreSQL Global Development Group
*
* Re: pgsql: Add template for adaptive radix tree
@ 2024-03-08 04:13 John Naylor <johncnaylorls@gmail.com>
parent: David Rowley <dgrowleyml@gmail.com>
0 siblings, 0 replies; 14+ messages in thread
From: John Naylor @ 2024-03-08 04:13 UTC (permalink / raw)
To: David Rowley <dgrowleyml@gmail.com>; +Cc: Alvaro Herrera <alvherre@alvh.no-ip.org>; Tom Lane <tgl@sss.pgh.pa.us>; John Naylor <john.naylor@postgresql.org>; pgsql-committers@lists.postgresql.org
On Fri, Mar 8, 2024 at 10:43 AM David Rowley <dgrowleyml@gmail.com> wrote:
>
> On Fri, 8 Mar 2024 at 16:37, John Naylor <johncnaylorls@gmail.com> wrote:
> > Thanks, I was getting close to committing a hackish workaround -- this
> > seems better!
>
> ok cool. I also noticed a typo. Maybe worth fixing that at the same time?
>
> Attached.
Done, thanks! As I mentioned, I was very close, and in fact
accidentally committed both, so egg on my face :-( -- but have
reverted the first one.
^ permalink raw reply [nested|flat] 14+ messages in thread
end of thread, other threads:[~2024-03-08 04:13 UTC | newest]
Thread overview: 14+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2009-06-26 11:28 pgbouncer - pgbouncer: v1.3.1rc1 User Mkz <mkz@pgfoundry.org>
2024-03-07 05:49 pgsql: Add template for adaptive radix tree John Naylor <john.naylor@postgresql.org>
2024-03-07 06:08 ` Re: pgsql: Add template for adaptive radix tree Tom Lane <tgl@sss.pgh.pa.us>
2024-03-07 06:14 ` Re: pgsql: Add template for adaptive radix tree John Naylor <johncnaylorls@gmail.com>
2024-03-07 06:32 ` Re: pgsql: Add template for adaptive radix tree Tom Lane <tgl@sss.pgh.pa.us>
2024-03-07 06:59 ` Re: pgsql: Add template for adaptive radix tree John Naylor <johncnaylorls@gmail.com>
2024-03-07 09:36 ` Re: pgsql: Add template for adaptive radix tree Alvaro Herrera <alvherre@alvh.no-ip.org>
2024-03-07 09:47 ` Re: pgsql: Add template for adaptive radix tree John Naylor <johncnaylorls@gmail.com>
2024-03-08 00:47 ` Re: pgsql: Add template for adaptive radix tree John Naylor <johncnaylorls@gmail.com>
2024-03-08 03:29 ` Re: pgsql: Add template for adaptive radix tree David Rowley <dgrowleyml@gmail.com>
2024-03-08 03:37 ` Re: pgsql: Add template for adaptive radix tree John Naylor <johncnaylorls@gmail.com>
2024-03-08 03:42 ` Re: pgsql: Add template for adaptive radix tree David Rowley <dgrowleyml@gmail.com>
2024-03-08 04:13 ` Re: pgsql: Add template for adaptive radix tree John Naylor <johncnaylorls@gmail.com>
2024-03-07 19:09 ` Re: pgsql: Add template for adaptive radix tree Andrew Dunstan <andrew@dunslane.net>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox