Re: 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(at)anarazel(dot)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(at)anarazel(dot)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(at)anarazel(dot)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(at)anarazel(dot)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(at)anarazel(dot)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(dot)Grittner(at)wicourts(dot)gov> writes:

> Andres Freund <andres(at)anarazel(dot)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(at)enterprisedb(dot)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

On 06/03/2009 07:05 PM, Kevin Grittner wrote:
> Andres Freund<andres(at)anarazel(dot)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

On 06/03/2009 08:57 PM, Gregory Stark wrote:
> "Kevin Grittner"<Kevin(dot)Grittner(at)wicourts(dot)gov> writes:
>> Andres Freund<andres(at)anarazel(dot)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

Hi,

On 06/03/2009 06:42 PM, Tom Lane wrote:
> Andres Freund<andres(at)anarazel(dot)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(at)anarazel(dot)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(at)anarazel(dot)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(at)anarazel(dot)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(at)anarazel(dot)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