[WIP] Zipfian distribution in pgbench

Hello Alik,

PostgreSQL shows very bad results in YCSB Workload A (50% SELECT and 50%
UPDATE of random row by PK) on benchmarking with big number of clients
using Zipfian distribution. MySQL also has decline but it is not
significant as it is in PostgreSQL. MongoDB does not have decline at
all. And if pgbench would have Zipfian distribution random number
generator, everyone will be able to make research on this topic without
using YCSB.

Your description is not very precise. What version of Postgres is used? If
there is a decline, compared to which version? Is there a link to these
results?

This is the reason why I am currently working on random_zipfian function.

The bottleneck of algorithm that I use is that it calculates zeta
function (it has linear complexity -
https://en.wikipedia.org/wiki/Riemann_zeta_function). It my cause
problems on generating huge amount of big numbers.

Indeed, the function computation is over expensive, and the numerical
precision of the implementation is doubtful.

If there is no better way to compute this function, ISTM that it should be
summed in reverse order to accumulate small values first, from (1/n)^s +
... + (1/2)^ s. As 1/1 == 1, the corresponding term is 1, no point in
calling pow for this one, so it could be:

double ans = 0.0;
for (i = n; i >= 2; i--)
ans += pow(1. / i, theta);
return 1.0 + ans;

That’s why I added caching for zeta value. And it works good for cases
when random_zipfian called with same parameters in script. For example:

That’s why I have a question: should I implement support of caching zeta
values for calls with different parameters, or not?

I do not envision the random_zipfian function to be used widely, but if it
is useful to someone this is fine with me. Could an inexpensive
exponential distribution be used instead for the same benchmarking
purpose?

If the functions when actually used is likely to be called with different
parameters, then some caching beyond the last value would seem in order.
Maybe a small fixed size array?

However, it should be somehow thread safe, which does not seem to be the
case with the current implementation. Maybe a per-thread cache? Or use a
lock only to update a shared cache? At least it should avoid locking to
read values...

P.S. I attaching patch and script - analogue of YCSB Workload A.
Run benchmark with command:
$ pgbench -f ycsb_read_zipf.sql -f ycsb_update_zipf.sql

Given the explanations, the random draw mostly hits values at the
beginning of the interval, so when the number of client goes higher one
just get locking contention on the updated row?

ISTM that also having the tps achieved with a flat distribution would
allow to check this hypothesis.

On scale = 10(1 million rows) it gives following results on machine with
144 cores(with synchronous_commit=off):

nclients tps
1 8842.401870
2 18358.140869
4 45999.378785
8 88713.743199
16 170166.998212
32 290069.221493
64 178128.030553
128 88712.825602
256 38364.937573
512 13512.765878
1000 6188.136736

--
Fabien.
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Fri, Jul 7, 2017 at 3:45 AM, Alik Khilazhev
<a.khilazhev@postgrespro.ru> wrote:

PostgreSQL shows very bad results in YCSB Workload A (50% SELECT and 50% UPDATE of random row by PK) on benchmarking with big number of clients using Zipfian distribution. MySQL also has decline but it is not significant as it is in PostgreSQL. MongoDB does not have decline at all.

How is that possible? In a Zipfian distribution, no matter how big
the table is, almost all of the updates will be concentrated on a
handful of rows - and updates to any given row are necessarily
serialized, or so I would think. Maybe MongoDB can be fast there
since there are no transactions, so it can just lock the row slam in
the new value and unlock the row, all (I suppose) without writing WAL
or doing anything hard. But MySQL is going to have to hold the row
lock until transaction commit just like we do, or so I would think.
Is it just that their row locking is way faster than ours?

I'm more curious about why we're performing badly than I am about a
general-purpose random_zipfian function. :-)

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Fri, Jul 7, 2017 at 5:17 AM, Robert Haas <robertmhaas@gmail.com> wrote:

How is that possible? In a Zipfian distribution, no matter how big
the table is, almost all of the updates will be concentrated on a
handful of rows - and updates to any given row are necessarily
serialized, or so I would think. Maybe MongoDB can be fast there
since there are no transactions, so it can just lock the row slam in
the new value and unlock the row, all (I suppose) without writing WAL
or doing anything hard.

If you're not using the Wired Tiger storage engine, than the locking
is at the document level, which means that a Zipfian distribution is
no worse than any other as far as lock contention goes. That's one
possible explanation. Another is that indexed organized tables
naturally have much better locality, which matters at every level of
the memory hierarchy.

I'm more curious about why we're performing badly than I am about a
general-purpose random_zipfian function. :-)

I'm interested in both. I think that a random_zipfian function would
be quite helpful for modeling certain kinds of performance problems,
like CPU cache misses incurred at the page level.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Fri, Jul 7, 2017 at 12:45 AM, Alik Khilazhev
<a.khilazhev@postgrespro.ru> wrote:

On scale = 10(1 million rows) it gives following results on machine with 144 cores(with synchronous_commit=off):
nclients tps
1 8842.401870
2 18358.140869
4 45999.378785
8 88713.743199
16 170166.998212
32 290069.221493
64 178128.030553
128 88712.825602
256 38364.937573
512 13512.765878
1000 6188.136736

Is it possible for you to instrument the number of B-Tree page
accesses using custom instrumentation for pgbench_accounts_pkey?

If that seems like too much work, then it would still be interesting
to see what the B-Tree keyspace looks like before and after varying
the "nclient" count from, say, 32 to 128. Maybe there is a significant
difference in how balanced or skewed it is in each case. Or, the index
could simply be more bloated.

There is a query that I sometimes use, that itself uses pageinspect,
to summarize the keyspace quickly. It shows you the highkey for every
internal page, starting from the root and working down to the lowest
internal page level (the one just before the leaf level -- level 1),
in logical/keyspace order. You can use it to visualize the
distribution of values. It could easily include the leaf level, too,
but that's less interesting and tends to make the query take ages. I
wonder what the query will show here.

Here is the query:

with recursive index_details as (
select
'pgbench_accounts_pkey'::text idx
),
size_in_pages_index as (
select
(pg_relation_size(idx::regclass) / (2^13))::int4 size_pages
from
index_details
),
page_stats as (
select
index_details.*,
stats.*
from
index_details,
size_in_pages_index,
lateral (select i from generate_series(1, size_pages - 1) i) series,
lateral (select * from bt_page_stats(idx, i)) stats),
internal_page_stats as (
select
*
from
page_stats
where
type != 'l'),
meta_stats as (
select
*
from
index_details s,
lateral (select * from bt_metap(s.idx)) meta),
internal_items as (
select
*
from
internal_page_stats
order by
btpo desc),
-- XXX: Note ordering dependency within this CTE, on internal_items
ordered_internal_items(item, blk, level) as (
select
1,
blkno,
btpo
from
internal_items
where
btpo_prev = 0
and btpo = (select level from meta_stats)
union
select
case when level = btpo then o.item + 1 else 1 end,
blkno,
btpo
from
internal_items i,
ordered_internal_items o
where
i.btpo_prev = o.blk or (btpo_prev = 0 and btpo = o.level - 1)
)
select
idx,
btpo as level,
item as l_item,
blkno,
btpo_prev,
btpo_next,
btpo_flags,
type,
live_items,
dead_items,
avg_item_size,
page_size,
free_size,
-- Only non-rightmost pages have high key.
case when btpo_next != 0 then (select data from bt_page_items(idx,
blkno) where itemoffset = 1) end as highkey
from
ordered_internal_items o
join internal_items i on o.blk = i.blkno
order by btpo desc, item;

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Peter Geoghegan wrote:

Here is the query:

with recursive index_details as (
select
'pgbench_accounts_pkey'::text idx
), [...]

Hmm, this seems potentially very useful. Care to upload it to
https://wiki.postgresql.org/wiki/Category:Snippets ?

--
�lvaro Herrera https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Fri, Jul 7, 2017 at 12:59 PM, Alvaro Herrera
<alvherre@2ndquadrant.com> wrote:

Hmm, this seems potentially very useful. Care to upload it to
https://wiki.postgresql.org/wiki/Category:Snippets ?

Sure. I've added it here, under "index maintenance":

https://wiki.postgresql.org/wiki/Index_Maintenance#Summarize_keyspace_of_a_B-Tree_index

It would be a nice additional touch if there was an easy way of taking
the on-disk representation of index tuples (in this case that would be
little-endian signed integers from bt_page_items()), and from that
output actual typed values. Maybe just for a few select datatypes.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Hello, Fabien!

Your description is not very precise. What version of Postgres is used? If there is a decline, compared to which version? Is there a link to these results?

Benchmark have been done in master v10. I am attaching image with results:
.

Indeed, the function computation is over expensive, and the numerical precision of the implementation is doubtful.

If there is no better way to compute this function, ISTM that it should be summed in reverse order to accumulate small values first, from (1/n)^s + ... + (1/2)^ s. As 1/1 == 1, the corresponding term is 1, no point in calling pow for this one, so it could be:

double ans = 0.0;
for (i = n; i >= 2; i--)
ans += pow(1. / i, theta);
return 1.0 + ans;

You are right, it’s better to reverse order.

If the functions when actually used is likely to be called with different parameters, then some caching beyond the last value would seem in order. Maybe a small fixed size array?

However, it should be somehow thread safe, which does not seem to be the case with the current implementation. Maybe a per-thread cache? Or use a lock only to update a shared cache? At least it should avoid locking to read values…

Yea, I forget about thread-safety. I will implement per-thread cache with small fixed array.

Given the explanations, the random draw mostly hits values at the beginning of the interval, so when the number of client goes higher one just get locking contention on the updated row?

Yes, exactly.

ISTM that also having the tps achieved with a flat distribution would allow to check this hypothesis.

On Workload A with uniform distribution PostgreSQL shows better results than MongoDB and MySQL(see attachment). Also you can notice that for small number of clients type of distribution does not affect on tps on MySQL.

And it’s important to mention that postgres run with option synchronous_commit=off, to satisfy durability MongoDB writeConcern=1&journaled=false. In this mode there is possibility to lose all changes in the last second. If we run postgres with max durability MongoDB will lag far behind.
---
Thanks and Regards,
Alik Khilazhev
Postgres Professional:
http://www.postgrespro.com <http://www.postgrespro.com/&gt;
The Russian Postgres Company

On Mon, Jul 10, 2017 at 12:19 PM, Alik Khilazhev <a.khilazhev@postgrespro.ru

wrote:

Hello, Fabien!

Your description is not very precise. What version of Postgres is used? If
there is a decline, compared to which version? Is there a link to these
results?

Benchmark have been done in master v10. I am attaching image with results:
.

It will be interesting to see what the profiling data with perf says about
this for PostgreSQL. Can you try to get the perf report?

--
With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

Hello Alik,

Your description is not very precise. What version of Postgres is used?
If there is a decline, compared to which version? Is there a link to
these results?

Benchmark have been done in master v10. I am attaching image with results:
.

Ok, thanks.

More precision would be helpful, such as the exact pgbench option used (eg
how many client per thread in pgbench, how long does it run, prepared
transactions, ...).

Intuitively, contention should explain a saturation of the tps
performance, because more clients are not effective to improve tps as the
wait for other clients, and the latency would degrade.

But it is unclear to me why the tps would be reduced even with lock
contention, so something seems amiss.

Performance debugging by mail is an uneasy task.

Maybe you could try zipf with unlogged tables, to check whether skipping
the WAL write does something.

Also Amit advice about the perf report looks useful.

Given the explanations, the random draw mostly hits values at the
beginning of the interval, so when the number of client goes higher one
just get locking contention on the updated row?

Yes, exactly.

Ok. The uniform distribution run, if all other parameters are equal, gives
a hint about the potential performance when the performance bottleneck is
hit.

On Workload A with uniform distribution PostgreSQL shows better results
than MongoDB and MySQL(see attachment). Also you can notice that for
small number of clients type of distribution does not affect on tps on
MySQL.

Ok. I assume that you use pgbench for pg and other ad-hoc tools for the
other targets (mysql & mongodb).

--
Fabien.

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 7 Jul 2017, at 21:53, Peter Geoghegan <pg@bowt.ie> wrote:

Is it possible for you to instrument the number of B-Tree page
accesses using custom instrumentation for pgbench_accounts_pkey?

If that seems like too much work, then it would still be interesting
to see what the B-Tree keyspace looks like before and after varying
the "nclient" count from, say, 32 to 128. Maybe there is a significant
difference in how balanced or skewed it is in each case. Or, the index
could simply be more bloated.

There is a query that I sometimes use, that itself uses pageinspect,
to summarize the keyspace quickly. It shows you the highkey for every
internal page, starting from the root and working down to the lowest
internal page level (the one just before the leaf level -- level 1),
in logical/keyspace order. You can use it to visualize the
distribution of values. It could easily include the leaf level, too,
but that's less interesting and tends to make the query take ages. I
wonder what the query will show here.

Here is the query:
…

I am attaching results of query that you sent. It shows that there is nothing have changed after executing tests.

—
Thanks and Regards,
Alik Khilazhev
Postgres Professional:
http://www.postgrespro.com <http://www.postgrespro.com/&gt;
The Russian Postgres Company

Hello!

I want to say that our company is already engaged in the search for the causes of the problem and their solution. And also we have few experimental patches that increases performance for 1000 clients by several times.

In addition, I have fixed threadsafety issues and implemented per-thread cache for zeta values. See attached patch.

On Wed, Jul 12, 2017 at 4:28 AM, Alik Khilazhev
<a.khilazhev@postgrespro.ru> wrote:

I am attaching results of query that you sent. It shows that there is
nothing have changed after executing tests.

But something did change! In the case where performance was good, all
internal pages on the level above the leaf level have exactly 285
items, excluding the rightmost page, which unsurprisingly didn't fill.
However, after increasing client count to get the slow case, the "hot"
part of the keyspace (the leaf pages owned by the first/leftmost
internal page on that level) has 353 items rather than 285.

Now, that might not seem like that much of a difference, but if you
consider how duplicates are handled in the B-Tree code, and how unique
index enforcement works, I think it could be. It could lead to heavy
buffer lock contention, because we sometimes do a lot of work with an
exclusive buffer lock held.

This is something that I go into a lot of detail on in the Wiki page
on Key normalization:
https://wiki.postgresql.org/wiki/Key_normalization#Avoiding_unnecessary_unique_index_enforcement

Now, I'm not saying that I know for sure that that's what it is. It
seems like a good area to investigate, though. Even if it wasn't
buffer lock contention, we're still talking about the difference
between the hot part of the B-Tree being about 353 pages, versus 285.
Buffer lock contention could naturally limit the growth in size to
"only" 353, by slowing everything down.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Wed, Jul 12, 2017 at 12:30 PM, Peter Geoghegan <pg@bowt.ie> wrote:

On Wed, Jul 12, 2017 at 4:28 AM, Alik Khilazhev
<a.khilazhev@postgrespro.ru> wrote:

I am attaching results of query that you sent. It shows that there is
nothing have changed after executing tests.

But something did change! In the case where performance was good, all
internal pages on the level above the leaf level have exactly 285
items, excluding the rightmost page, which unsurprisingly didn't fill.
However, after increasing client count to get the slow case, the "hot"
part of the keyspace (the leaf pages owned by the first/leftmost
internal page on that level) has 353 items rather than 285.

Could you please run the query again for both cases, but this time
change it to get items from the leaf level too, and not just internal
levels? Just remove the "wheretype != 'l' " clause in one of the CTEs.
That should do it.

It's probably the case that the hot part of the B-tree is actually
significantly less than 353 items (or 285 items), and so the "before"
and "after" difference in how many pages are used for the hot part of
the keyspace could be quite a lot larger than my initial estimate. It
could be that the granularity that is shown on the internal pages is
insufficient to see just how bad the problem is.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Peter Geoghegan wrote:

Now, that might not seem like that much of a difference, but if you
consider how duplicates are handled in the B-Tree code, and how unique
index enforcement works, I think it could be. It could lead to heavy
buffer lock contention, because we sometimes do a lot of work with an
exclusive buffer lock held.

Not to mention work done with a "buffer cleanup lock" held -- which is
compounded by the fact that acquiring such a lock is prone to starvation
if there are many scanners of that index. I've seen a case where a very
hot table is scanned so heavily that vacuum is starved for days waiting
to acquire cleanup on a single page (vacuum was only able to finish
because the app using the table was restarted). I'm sure that a uniform
distribution of keys, with a uniform distribution of values scanned,
would give a completely different behavior than a highly skewed
distribution where a single key receives a large fraction of the scans.

--
�lvaro Herrera https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Wed, Jul 12, 2017 at 1:55 PM, Alvaro Herrera
<alvherre@2ndquadrant.com> wrote:

Not to mention work done with a "buffer cleanup lock" held -- which is
compounded by the fact that acquiring such a lock is prone to starvation
if there are many scanners of that index. I've seen a case where a very
hot table is scanned so heavily that vacuum is starved for days waiting
to acquire cleanup on a single page (vacuum was only able to finish
because the app using the table was restarted). I'm sure that a uniform
distribution of keys, with a uniform distribution of values scanned,
would give a completely different behavior than a highly skewed
distribution where a single key receives a large fraction of the scans.

Good point.

I'd be interested in seeing the difference it makes if Postgres is
built with the call to _bt_check_unique() commented out within
nbtinsert.c. The UPDATE query doesn't ever change indexed columns, so
there should be no real need for the checking it does in this case.
We're seeing a lot of duplicates in at least part of the keyspace, and
yet the queries themselves should be as HOT-safe as possible.

Another possibly weird thing that I noticed is latency standard
deviation. This is from Alik's response to my request to run that SQL
query:

latency average = 1.375 ms
tps = 93085.250384 (including connections establishing)
tps = 93125.724773 (excluding connections establishing)
SQL script 1: /home/nglukhov/ycsb_read_zipf.sql
- weight: 1 (targets 50.0% of total)
- 2782999 transactions (49.8% of total, tps = 46364.447705)
- latency average = 0.131 ms
- latency stddev = 0.087 ms
SQL script 2: /home/nglukhov/ycsb_update_zipf.sql
- weight: 1 (targets 50.0% of total)
- 2780197 transactions (49.8% of total, tps = 46317.766703)
- latency average = 2.630 ms
- latency stddev = 14.092 ms

This is from the 128 client case -- the slow case.

Notice that the standard deviation is very high for
ycsb_update_zipf.sql. I wonder if this degrades because of some kind
of feedback loop, that reaches a kind of tipping point at higher
client counts.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Wed, Jul 12, 2017 at 2:17 PM, Peter Geoghegan <pg@bowt.ie> wrote:

I'd be interested in seeing the difference it makes if Postgres is
built with the call to _bt_check_unique() commented out within
nbtinsert.c.

Actually, I mean that I wonder how much of a difference it would make
if this entire block was commented out within _bt_doinsert():

if (checkUnique != UNIQUE_CHECK_NO)
{
...
}

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 13 Jul 2017, at 00:20, Peter Geoghegan <pg@bowt.ie> wrote:

Actually, I mean that I wonder how much of a difference it would make
if this entire block was commented out within _bt_doinsert():

if (checkUnique != UNIQUE_CHECK_NO)
{
…
}

I am attaching results of test for 32 and 128 clients for original and patched(_bt_doinsert) variants.
—
Thanks and Regards,
Alik Khilazhev
Postgres Professional:
http://www.postgrespro.com <http://www.postgrespro.com/&gt;
The Russian Postgres Company

Hello Alik,

A few comments about the patch v2.

Patch applies and compiles.

Documentation says that the closer theta is from 0 the flatter the distribution
but the implementation requires at least 1, including strange error messages:

zipfian parameter must be greater than 1.000000 (not 1.000000)

Could theta be allowed between 0 & 1 ? I've tried forcing with theta = 0.1
and it worked well, so I'm not sure that I understand the restriction.
I also tried with theta=0.001 but it seemed less good.

I have also tried to check the distribution wrt the explanations, with the
attached scripts, n=100, theta=1.000001/1.5/3.0: It does not seem to work,
there is repeatable +15% bias on i=3 and repeatable -3% to -30% bias for
values in i=10-100, this for different values of theta (1.000001,1.5,
3.0).

If you try the script, beware to set parameters (theta, n) consistently.

About the code:

Remove spaces and tabs at end of lines or on empty lines.

zipfn: I would suggest to move the pg_erand48 out and pass the result
instead of passing the thread. the erand call would move to getZipfianRand.

I'm wondering whether the "nearest" hack could be removed so as to simplify
the cache functions code...

Avoid editing lines without changes (spacesn/tabs?)
   -  thread->logfile = NULL; /* filled in later */
   +  thread->logfile = NULL; /* filled in later */

The documentation explaining the intuitive distribution talks about a N
but does not provide any hint about its value depending on the parameters.

There is an useless empty lien before "</para>" after that.

--
Fabien.

On Thu, Jul 13, 2017 at 4:38 AM, Alik Khilazhev
<a.khilazhev@postgrespro.ru> wrote:

I am attaching results of test for 32 and 128 clients for original and
patched(_bt_doinsert) variants.

Thanks.

The number of leaf pages at the left hand side of the leaf level seems
to be ~50 less than the unpatched 128 client case was the first time
around, which seems like a significant difference. I wonder why. Maybe
autovacuum ran at the right/wrong time this time around?

Did you happen to record TPS for this most recent set of tests?

I notice one possibly interesting thing from these new numbers: the 32
client case is slightly more bloated when unique index enforcement is
removed.

--
Peter Geoghegan

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers