Horton

Re: pgbench - add pseudo-random permutation function

Dean Rasheed <dean.a.rasheed@gmail.com>

View thread
From: Dean Rasheed <dean.a.rasheed@gmail.com>
To: Bruce Momjian <bruce@momjian.us>
Cc: Fabien COELHO <coelho@cri.ensmp.fr>, Alvaro Herrera <alvherre@2ndquadrant.com>, David Steele <david@pgmasters.net>, Peter Eisentraut <peter.eisentraut@2ndquadrant.com>, Tomas Vondra <tomas.vondra@2ndquadrant.com>, Thomas Munro <thomas.munro@gmail.com>, Hironobu SUZUKI <hironobu@interdb.jp>, PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Date: 2021-03-11T16:31:44Z
Lists: pgsql-hackers

Commits

Same data as JSON: GET /api/v1/messages/:b64id/commits the thread's linked commits as JSON, with link sources. API reference →

  1. pgbench: Function to generate random permutations.

  2. Add basic support for using the POPCNT and SSE4.2s LZCNT opcodes

  3. Further improve code for probing the availability of ARM CRC instructions.

Attachments

On Thu, 11 Mar 2021 at 00:58, Bruce Momjian <bruce@momjian.us> wrote:
>
> Maybe Dean Rasheed can help because of his math background --- CC'ing him.
>

Reading the thread I can see how such a function might be useful to
scatter non-uniformly random values.

The implementation looks plausible too, though it adds quite a large
amount of new code. The main thing that concerns me is justifying the
code. With this kind of thing, it's all too easy to overlook corner
cases and end up with trivial sequences in certain special cases. I'd
feel better about that if we were implementing a standard algorithm
with known pedigree.

Thinking about the use case for this, it seems that it's basically
designed to turn a set of non-uniform random numbers (produced by
random_exponential() et al.) into another set of non-uniform random
numbers, where the non-uniformity is scattered so that the more/less
common values aren't all clumped together.

I'm wondering if that's something that can't be done more simply by
passing the non-uniform random numbers through the uniform random
number generator to scatter them uniformly across some range -- e.g.,
given an integer n, return the n'th value from the sequence produced
by random(), starting from some initial seed -- i.e., implement
nth_random(lb, ub, seed, n). That would actually be pretty
straightforward to implement using O(log(n)) time to execute (see the
attached python example), though it wouldn't generate a permutation,
so it'd need a bit of thought to see if it met the requirements.

Regards,
Dean