Обсуждение: Plan time Improvement - 64bit bitmapset

Hi,

While analyzing some complex query and switching away from using the
materialized views to their underlying ones I got interested in the long
plan times (minutes and up) and did some profiling work.

The queries are high dimensional star-schema-alike queries 
(unfortunately quite private (health) data and a schema I may not make 
public).

Using oprofile and
"valgrind --tool=callgrind --dump-instr=yes --collect-jumps=yes
--simulate-cache=yes --simulate-hwpref=yes" I found that one of the 
bitmapset functions are near the top of the profile.

When switching bitmapword and companions in bitmap.h to u64 and s64 
respectively I get an improvement up to 15% in queries with 16+ joins. 
The more joins the bigger the win.

In the very simple (structurally) query with 16 joins the improvement is 
around 1-2%.
With the most complex query I tested (the nr. of participating relations 
is hard to count because of many views) I get an improvement up to 15%.
I did not test with bigger/more complex queries because it got too slow 
to get sufficiently thorough results.

When playing around with join_collapse_limit, from_collapse_limit, geqo, 
geqo_threshold I found that unless the settings are set to really low 
values I can find performance improvements for most combinations.

I could not find any regression in the queries we use - and I can't see 
where there would be a significant overhead.

Unfortunately the more interesting trace seems to be the valgrind one - 
which with these options currently only "kcachegrind" can read. I could 
not get a usable text export out of the latter.

Linked are two overview pictures before (32bit.png) and after 
(64bit.png) the switch to using 64bit bitmapsets from the backend 
evaluating a complex query once:

http://anarazel.de/pg/32bit_bitmapsets.png
http://anarazel.de/pg/64bit_bitmapsets.png

That seems like an easy change - is there a reason not to do this if the 
arch is a 64bit one?

Can anybody else with complex queries test my results? (I can provide a 
patch if wanted).

Andres

PS: If kcachegrind users want to see the trace, speak up...

Andres Freund <andres@anarazel.de> writes:
> When switching bitmapword and companions in bitmap.h to u64 and s64 
> respectively I get an improvement up to 15% in queries with 16+ joins. 

I find this *really* hard to believe, because I've never seen the bitmap
support operations show up noticeably at all in profiles.  What sort of
queries are you testing?
        regards, tom lane

Hi,

On 06/03/2009 06:21 PM, Tom Lane wrote:
> Andres Freund<andres@anarazel.de>  writes:
>> When switching bitmapword and companions in bitmap.h to u64 and s64
>> respectively I get an improvement up to 15% in queries with 16+ joins.
> I find this *really* hard to believe, because I've never seen the bitmap
> support operations show up noticeably at all in profiles.  What sort of
> queries are you testing?
Many left joins from one base relation to additional dimensions. All the 
dimensions are relatively complex views consisting out of multiple joins 
or subselects.
Some correlated subqueries and some [NOT] EXISTS() are also included in 
some of the queries.


I tested by compiling with 64bit bitmaps and without by repeatedly just 
changing those three definitions. I don't see how I could get false 
results with that?

I guess the biggest advantage comes from less cache trashing?

Andres

Andres Freund <andres@anarazel.de> writes:
> On 06/03/2009 06:21 PM, Tom Lane wrote:
>> I find this *really* hard to believe, because I've never seen the bitmap
>> support operations show up noticeably at all in profiles.  What sort of
>> queries are you testing?

> Many left joins from one base relation to additional dimensions. All the 
> dimensions are relatively complex views consisting out of multiple joins 
> or subselects.
> Some correlated subqueries and some [NOT] EXISTS() are also included in 
> some of the queries.

Hmmm, could you provide a complete test case?  I'm thinking the behavior
might indicate some other performance issue, ie an unreasonable number
of bitmapset calls in some particular planning path.

There used to be some performance issues in this area back when we
represented sets of relids as integer Lists :-(, but the change to
bitmap sets pretty much stomped that.  I'm just really surprised that
there would be anything measurable from changing the word width.
        regards, tom lane

On 06/03/2009 06:42 PM, Tom Lane wrote:
> Andres Freund<andres@anarazel.de>  writes:
>> On 06/03/2009 06:21 PM, Tom Lane wrote:
>>> I find this *really* hard to believe, because I've never seen the bitmap
>>> support operations show up noticeably at all in profiles.  What sort of
>>> queries are you testing?
>
>> Many left joins from one base relation to additional dimensions. All the
>> dimensions are relatively complex views consisting out of multiple joins
>> or subselects.
>> Some correlated subqueries and some [NOT] EXISTS() are also included in
>> some of the queries.
> Hmmm, could you provide a complete test case?  I'm thinking the behavior
> might indicate some other performance issue, ie an unreasonable number
> of bitmapset calls in some particular planning path.
Uh. I will try, but probably it is not easy. (Once more a 
datawarehouse-ish example database would be useful).

The graph linked in the former email includes all callers with relevant 
amount of calls (generate_join_implied_equalities, join_is_legal, 
have_join_order_restriction are in this order the by far most costly).

I put up the raw profile data at:
http://anarazel.de/pg/32bit_bitmaps.out.gz
http://anarazel.de/pg/64bit_bitmaps.out.gz
As I said, unfortunately only kcachegrind seems to be able to load the 
data - it is included in most linux distros though.

> There used to be some performance issues in this area back when we
> represented sets of relids as integer Lists :-(, but the change to
> bitmap sets pretty much stomped that.  I'm just really surprised that
> there would be anything measurable from changing the word width.
Well, the number of memory accesses is halved and I think that bitwise 
NOT and AND take the same amount of cycles whether they are operating on 
32 or 64bit. That would explain some difference.

Andres

Andres Freund <andres@anarazel.de> wrote: 
> long plan times (minutes and up)
Wow.  I thought I had some pretty complex queries, including some
which join using several views, each of which has several joins; but
I've never gone to multiple seconds on plan time (much less multiple
minutes!) without very high statistics targets and many indexes on the
tables.  Any rough estimates on those?
If you think your patch could have a significant impact on a query
with a 260 ms plan time, I could give it a try.
-Kevin

"Kevin Grittner" <Kevin.Grittner@wicourts.gov> writes:

> Andres Freund <andres@anarazel.de> wrote: 
>  
>> long plan times (minutes and up)
>  
> Wow.  I thought I had some pretty complex queries, including some
> which join using several views, each of which has several joins; but
> I've never gone to multiple seconds on plan time (much less multiple
> minutes!) without very high statistics targets and many indexes on the
> tables.  Any rough estimates on those?

My money's still on very large statistics targets. If you have a lot of
columns and 1,000-element arrays for each column that can get big pretty
quickly.

But that doesn't explain the bitmap ops being important. Hm. Actually having a
lot of columns and then joining a lot of tables could mean having fairly large
bitmapsets.



--  Gregory Stark EnterpriseDB          http://www.enterprisedb.com Ask me about EnterpriseDB's 24x7 Postgres support!

Gregory Stark <stark@enterprisedb.com> writes:
> But that doesn't explain the bitmap ops being important. Hm. Actually
> having a lot of columns and then joining a lot of tables could mean
> having fairly large bitmapsets.

Yeah, but then you have a lot of *other* expensive operations too,
such as the aforementioned statistics-pushing.  It's still pretty
mystifying why bitmapsets would be eating a noticeable fraction
of the total.
        regards, tom lane

Gregory Stark <stark@enterprisedb.com> wrote: 
> My money's still on very large statistics targets. If you have a lot
> of columns and 1,000-element arrays for each column that can get big
> pretty quickly.
I'm finding that even the ones that had a plan time in the range of
260 ms go down to 15 ms to 85 ms once the statistics are cached.  I
wonder if the long run time is because it's having to read statistics
multiple times because they don't fit in cache?  Like with really wide
values?  Would the wider bitmap type help with that situation in any
way?
-Kevin

On Wed, Jun 3, 2009 at 3:18 PM, Kevin Grittner
<Kevin.Grittner@wicourts.gov> wrote:
> Gregory Stark <stark@enterprisedb.com> wrote:
>
>> My money's still on very large statistics targets. If you have a lot
>> of columns and 1,000-element arrays for each column that can get big
>> pretty quickly.
>
> I'm finding that even the ones that had a plan time in the range of
> 260 ms go down to 15 ms to 85 ms once the statistics are cached.  I
> wonder if the long run time is because it's having to read statistics
> multiple times because they don't fit in cache?  Like with really wide
> values?  Would the wider bitmap type help with that situation in any
> way?
>
> -Kevin

I had some performance results back when we were last looking at
default_statistics_target that indicated that the time to repeatedly
decompress a toasted statistics array contributed significantly to the
total planning time, but my suggestion to disable compression for
pg_statistic was summarily poo-poohed for reasons that still aren't
quite clear to me.  When you say, "don't fit in cache", exactly what
cache are you talking about?  It seems to me that the statistics
should be far smaller than the underlying tables, so if even your
statistics don't fit in shared buffers (let alone main memory), it
doesn't really matter how long your query takes to plan because it
will probably take literally forever to execute.  How many tables
would you have to be joining to get a GB of statistics, even with dst
= 1000?  A few hundred?

...Robert

Robert Haas <robertmhaas@gmail.com> wrote: 
> When you say, "don't fit in cache", exactly what
> cache are you talking about?  It seems to me that the statistics
> should be far smaller than the underlying tables, so if even your
> statistics don't fit in shared buffers (let alone main memory), it
> doesn't really matter how long your query takes to plan because it
> will probably take literally forever to execute.  How many tables
> would you have to be joining to get a GB of statistics, even with
> dst = 1000?  A few hundred?
Since he can't share the schema, and hasn't even given much of a hint,
I don't know whether one (or more) of the columns is a bytea filled
with 100 MB values; and I don't remember any description of the
hardware environment either.  Since the behavior seems so
out-of-the-ordinary, I was casting about for possible extraordinary
characteristics of his environment which might cause it.  I'm probably
way off base....
-Kevin

"Kevin Grittner" <Kevin.Grittner@wicourts.gov> writes:
> Since he can't share the schema, and hasn't even given much of a hint,
> I don't know whether one (or more) of the columns is a bytea filled
> with 100 MB values; and I don't remember any description of the
> hardware environment either.  Since the behavior seems so
> out-of-the-ordinary, I was casting about for possible extraordinary
> characteristics of his environment which might cause it.  I'm probably
> way off base....

There's a hard-wired restriction in analyze.c that makes it discard data
values wider than 1KB on-sight.  So no such value will ever be found in
a statistics array.  You could still have a few meg in a pg_statistics
row, I suppose, but not a really horrendous amount.
        regards, tom lane

Robert Haas <robertmhaas@gmail.com> writes:
> On Wed, Jun 3, 2009 at 3:18 PM, Kevin Grittner
> <Kevin.Grittner@wicourts.gov> wrote:
>> I'm finding that even the ones that had a plan time in the range of
>> 260 ms go down to 15 ms to 85 ms once the statistics are cached.

> I had some performance results back when we were last looking at
> default_statistics_target that indicated that the time to repeatedly
> decompress a toasted statistics array contributed significantly to the
> total planning time, but my suggestion to disable compression for
> pg_statistic was summarily poo-poohed for reasons that still aren't
> quite clear to me.

Well, smaller is better.  Kevin's example demonstrates that it's good
to have the stats sucked into cache.  If they were uncompressed then
less of them would fit in however much cache space you have, and
whatever CPU savings you get would be lost to more I/O to read in
stats entries.

Of course, this all depends on total database size vs total RAM,
but that's how I'd interpret the observation.  PG is still mostly
optimized for databases bigger than RAM, so this decision still
makes sense.

(I think you could try marking the columns of pg_statistic as "don't
compress" if you have a DB you want to optimize for all-in-memory
behavior.)
        regards, tom lane

On 06/03/2009 07:05 PM, Kevin Grittner wrote:
> Andres Freund<andres@anarazel.de>  wrote:
>
>> long plan times (minutes and up)
>
> Wow.  I thought I had some pretty complex queries, including some
> which join using several views, each of which has several joins; but
> I've never gone to multiple seconds on plan time (much less multiple
> minutes!) without very high statistics targets and many indexes on the
> tables.  Any rough estimates on those?
Statistics target is 250. Lowering to 10 lowers the query plan time 
somewhat but not significantly and increases query runtime significantly.

Real dataset is a bit less than 1.5TB without materialized views and a 
bit over 3 with.
Production machine (old) is a 2xDualcore Xeon 5150, 32gig ram.

Test Dataset is about 15GB. Core2 Duo 2.4Ghz, 4GB ram.

Example query (from which the traces are) on the test dataset (I cant 
simply do a full analyze on the real data):
Stat target 10: 22283.187ms PREPARE
Stat target 1000: 23986.504ms PREPARE

So, no really interesting difference.

For the timings I always PREPARE'ed the query multiple times in a 
transaction to make sure there are no caching effects - a small drop but 
nothing significant.


On the average its about
> If you think your patch could have a significant impact on a query
> with a 260 ms plan time, I could give it a try.From what I have seen so far I doubt that it will have a really 
measurable effect on relatively short planning times- if you want to try 
its a very simple change:

Just change all 32 into the 64 bit equivalents in include/nodes/bitmapset.h:
#define BITS_PER_BITMAPWORD 32
typedef uint32 bitmapword;            /* must be an unsigned type */
typedef int32 signedbitmapword; /* must be the matching signed type */


Andres

Doesn't that still add up to 3GB for a table's stats in the worst  
case? 1kb * 1,000 buckets * 1,500 attributes * 2 (histogram + mfv)

Except you can't actually get 1500 toast pointers on a page. I suppose  
with games with nulls you could make this worst case happen though.

It does seem like it ought to be possible to truncate strings in the  
histogram since any string between the actual values us equally good.

-- 
Greg


On 3 Jun 2009, at 22:11, Tom Lane <tgl@sss.pgh.pa.us> wrote:

> "Kevin Grittner" <Kevin.Grittner@wicourts.gov> writes:
>> Since he can't share the schema, and hasn't even given much of a  
>> hint,
>> I don't know whether one (or more) of the columns is a bytea filled
>> with 100 MB values; and I don't remember any description of the
>> hardware environment either.  Since the behavior seems so
>> out-of-the-ordinary, I was casting about for possible extraordinary
>> characteristics of his environment which might cause it.  I'm  
>> probably
>> way off base....
>
> There's a hard-wired restriction in analyze.c that makes it discard  
> data
> values wider than 1KB on-sight.  So no such value will ever be found  
> in
> a statistics array.  You could still have a few meg in a pg_statistics
> row, I suppose, but not a really horrendous amount.
>
>            regards, tom lane

Greg Stark <greg.stark@enterprisedb.com> writes:
> It does seem like it ought to be possible to truncate strings in the  
> histogram since any string between the actual values us equally good.

Yeah, that was the justification for dropping the wide values ---
that and the theory that they'd be unlikely to be most-common values.
        regards, tom lane

On 06/03/2009 08:57 PM, Gregory Stark wrote:
> "Kevin Grittner"<Kevin.Grittner@wicourts.gov>  writes:
>> Andres Freund<andres@anarazel.de>  wrote:
>>> long plan times (minutes and up)
>> Wow.  I thought I had some pretty complex queries, including some
>> which join using several views, each of which has several joins;
>> but I've never gone to multiple seconds on plan time (much less
>> multiple minutes!) without very high statistics targets and many
>> indexes on the tables.  Any rough estimates on those?
> My money's still on very large statistics targets. If you have a lot
> of columns and 1,000-element arrays for each column that can get big
> pretty quickly.
Only a relatively small difference (stat target 10; 1000): 22283.187
23986.504

> But that doesn't explain the bitmap ops being important. Hm. Actually
> having a lot of columns and then joining a lot of tables could mean
> having fairly large bitmapsets.
Some of the views have a large amount of columns (200-400) - none of the 
actual tables has many columns though (10 user columns is the biggest I 
think).
110 tables containing real data.

The queries include the same tables quite often.

Andres

On 06/03/2009 10:42 PM, Kevin Grittner wrote:
> Robert Haas<robertmhaas@gmail.com>  wrote:
>
>> When you say, "don't fit in cache", exactly what
>> cache are you talking about?  It seems to me that the statistics
>> should be far smaller than the underlying tables, so if even your
>> statistics don't fit in shared buffers (let alone main memory), it
>> doesn't really matter how long your query takes to plan because it
>> will probably take literally forever to execute.  How many tables
>> would you have to be joining to get a GB of statistics, even with
>> dst = 1000?  A few hundred?
The whole pgstat.stat is around 500k on the test database - seems to be 
relatively reasonable.

> Since he can't share the schema, and hasn't even given much of a hint,
The schema isnt the most clear one - the original developers are long 
gone and I only somewhat recently jumped the wagon.
If what I have gathered is correct the biggest reason for implementing 
materialized views was plan and not execution time.

The schema is a rather normalized DW snowflake-alike schema - with the 
abnormality that most of the time a single dimension is actually 
multidimensional, i.e. there are multiple different joins to it needed.

The relatively high degree of normalizations introduces a rather big 
amount of joins for each additional dimension...

I find it hard to give a short overview over a relative complex schema 
without showing it - but thats not up to my choice.

> I don't know whether one (or more) of the columns is a bytea filled
> with 100 MB values; and I don't remember any description of the
> hardware environment either.  Since the behavior seems so
> out-of-the-ordinary, I was casting about for possible extraordinary
> characteristics of his environment which might cause it.  I'm probably
> way off base....
I would love to find such a issue, but I fear there is none. The problem 
exists on different machines, different pg versions, different settings...

Please keep in mind that when using the system "normally" the 
materialized views are used and the query plans stay around 1-2s. Which 
is quite okay for reporting queries I think.
Only that the materialized views start to take too much space...

Andres

On Wed, Jun 3, 2009 at 5:24 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Robert Haas <robertmhaas@gmail.com> writes:
>> On Wed, Jun 3, 2009 at 3:18 PM, Kevin Grittner
>> <Kevin.Grittner@wicourts.gov> wrote:
>>> I'm finding that even the ones that had a plan time in the range of
>>> 260 ms go down to 15 ms to 85 ms once the statistics are cached.
>
>> I had some performance results back when we were last looking at
>> default_statistics_target that indicated that the time to repeatedly
>> decompress a toasted statistics array contributed significantly to the
>> total planning time, but my suggestion to disable compression for
>> pg_statistic was summarily poo-poohed for reasons that still aren't
>> quite clear to me.
>
> Well, smaller is better.  Kevin's example demonstrates that it's good
> to have the stats sucked into cache.  If they were uncompressed then
> less of them would fit in however much cache space you have, and
> whatever CPU savings you get would be lost to more I/O to read in
> stats entries.

Smaller-but-compressed isn't better if the limiting factor is CPU
rather than I/O, which I suspect is nearly always the case for
pg_statistic.  I would be very surprised to find out that anyone has a
database where query planning regularly results in disk access.  Sure,
there are cold-cache effects at system startup, and maybe for rarely
used tables whose pg_statistic entries have been paged out to make
room for more heavily used data, but it doesn't make any sense to me
to optimize for those cases at the expense of the common case where
you are constantly executing new and different queries.  In that case,
fast access to the statistics tuples means "I don't need to decompress
this", not "I don't need to read this in from disk".

It wouldn't be so bad if memory-resident tuples, once decompressed,
stayed decompressed at least for the duration of the current query
planning cycle.  But it seemed to me when I looked at this a while
back that every call to eqjoinsel() and the various other functions
that look at statistics to do their thing appears to decompress the
tuple all over again.  That leads to a huge slowdown in query planning
beginning, for the example Greg Stark constructed, right around a
statistics target of 90.

http://archives.postgresql.org/pgsql-hackers/2008-12/msg00386.php

The exact point where you hit the slowdown will presumably vary with
the size of the relevant columns, but it's surely going to affect a
lot more people now that we've made the default target 10x larger.

> Of course, this all depends on total database size vs total RAM,
> but that's how I'd interpret the observation.  PG is still mostly
> optimized for databases bigger than RAM, so this decision still
> makes sense.
>
> (I think you could try marking the columns of pg_statistic as "don't
> compress" if you have a DB you want to optimize for all-in-memory
> behavior.)

If you set allow_system_table_mods...

...Robert

Hi,

On 06/03/2009 06:42 PM, Tom Lane wrote:
> Andres Freund<andres@anarazel.de>  writes:
>> On 06/03/2009 06:21 PM, Tom Lane wrote:
>>> I find this *really* hard to believe, because I've never seen the bitmap
>>> support operations show up noticeably at all in profiles.  What sort of
>>> queries are you testing?
>> Many left joins from one base relation to additional dimensions. All the
>> dimensions are relatively complex views consisting out of multiple joins
>> or subselects.
>> Some correlated subqueries and some [NOT] EXISTS() are also included in
>> some of the queries.
> Hmmm, could you provide a complete test case?  I'm thinking the behavior
> might indicate some other performance issue, ie an unreasonable number
> of bitmapset calls in some particular planning path.
Ok. I tried to reproduce it using only pg_catalog and suceeded to some
degree:
- The query is pointless, pointless, pointless
- The effect is only around 5-10% instead of the 15-20% I have measured
(fewer tables involved - fewer cache misses?)
- The query is crazy, but so is the one on the schema in question
- I could get more consistent results with geqo disabled, but the
results are in the same ballpark whether enabled or not
- Sometimes adding a single join more/less dropped the planning time to
a fraction - strange.
- The same with changing {join,from}_collapse_limit - sometimes changing
it yields plan times different by orders of magnitudes in both directions.

On the real data its naturally not only one view but multiple ones...
And there are fewer views involved, but they are more complex (including
EXISTS(), and some subqueries).

Plan time (averaged) without change:
cnt: 40 (4 times per session)
avg: 4572ms

Plan time (averaged) with change:
cnt: 40 (4 times per session)
avg: 4236ms

~7% difference. Same with higher number of repetitions and with most
other planner settings I tried

Now thats not a lot of change, but again, this is smaller than with the
original queries.

Does that help?

Andres

Andres Freund <andres@anarazel.de> writes:

> Plan time (averaged) without change:
> cnt: 40 (4 times per session)
> avg: 4572ms
>
> Plan time (averaged) with change:
> cnt: 40 (4 times per session)
> avg: 4236ms
>
> ~7% difference. Same with higher number of repetitions and with most other
> planner settings I tried

What are you comparing here?

Hi,

On 06/10/2009 01:38 PM, Gregory Stark wrote:
> Andres Freund<andres@anarazel.de>  writes:
>
>> Plan time (averaged) without change:
>> cnt: 40 (4 times per session)
>> avg: 4572ms
>>
>> Plan time (averaged) with change:
>> cnt: 40 (4 times per session)
>> avg: 4236ms
>>
>> ~7% difference. Same with higher number of repetitions and with most other
>> planner settings I tried
>
> What are you comparing here?
32bit and 64bit bitmapsets with the attached query. 32beeing the default 
and the slower one.

Does that answer the question?


Andres

Andres Freund <andres@anarazel.de> wrote:
> - Sometimes adding a single join more/less dropped the planning time
> to a fraction - strange.
> - The same with changing {join,from}_collapse_limit - sometimes
> changing it yields plan times different by orders of magnitudes in
> both directions.
That seems like the place to spend the time looking, rather than
nibbling away at the run times by a few percent after letting them
jump by orders of magnitude.
-Kevin

Hi,

On 06/10/2009 06:01 PM, Kevin Grittner wrote:
> Andres Freund<andres@anarazel.de>  wrote:
>> - Sometimes adding a single join more/less dropped the planning time
>> to a fraction - strange.
>> - The same with changing {join,from}_collapse_limit - sometimes
>> changing it yields plan times different by orders of magnitudes in
>> both directions.
> That seems like the place to spend the time looking, rather than
> nibbling away at the run times by a few percent after letting them
> jump by orders of magnitude.
Yes. I noticed this while looking for reasons. And I will continue to do 
so...

Andres