Обсуждение: a few crazy ideas about hash joins

While investigating some performance problems recently I've had cause
to think about the way PostgreSQL uses hash joins.  So here are a few
thoughts.  Some of these have been brought up before.

1. When the hash is not expected to spill to disk, it preserves the
pathkeys of the outer side of the join.  If the optimizer were allowed
to assume that, it could produce significantly more efficient query
plans in some cases.  The problem is what to do if we start executing
the query and find out that we have more stuff to hash than we expect,
such that we need multiple batches?  Now the results won't be sorted.
I think we could handle this as follows: Don't count on the hash join
to preserve pathkeys unless it helps, and only rely on it when it
seems as if the hash table will still fit even if it turns out to be,
say, three times as big as expected.  But if you are counting on the
hash join to preserve pathkeys, then pass that information to the
executor.  When the executor is asked to perform a hash join, it will
first hash the inner side of the relation.  At that point, we know
whether we've succesfully gotten everything into a single batch, or
not.  If we have, perform the join normally.  If the worst has
happened and we've gone multi-batch, then perform the join and sort
the output before returning it.  The performance will suck, but at
least you'll get the right answer.

Previous in-passing reference to this idea here:
http://archives.postgresql.org/pgsql-hackers/2008-09/msg00806.php

2. Consider building the hash table lazily.  I often see query planner
pick a hash join over a nested inner indexscan because it thinks that
it'll save enough time making hash probes rather than index probes to
justify the time spent building the hash table up front.  But
sometimes the relation that's being hashed has a couple thousand rows,
only a tiny fraction of which will ever be retrieved from the hash
table.  We can predict when this is going to happen because n_distinct
for the outer column will be much less than the size of the inner rel.In that case, we could consider starting with an
emptyhash table
 
that effectively acts as a cache.  Each time a value is probed, we
look it up in the hash table.  If there's no entry, we use an index
scan to find the matching rows and insert them into the hash table.
Negative results must also be cached.

3. Avoid building the exact same hash table twice in the same query.
This happens more often you'd think.  For example, a table may have
two columns creator_id and last_updater_id which both reference person
(id).  If you're considering a hash join between paths A and B, you
could conceivably check whether what is essentially a duplicate of B
has already been hashed somewhere within path A.  If so, you can reuse
that same hash table at zero startup-cost.

4. As previously discussed, avoid hashing for distinct and then
hashing the results for a hash join on the same column with the same
operators.

http://archives.postgresql.org/message-id/4136ffa0902191346g62081081v8607f0b92c206f0a@mail.gmail.com

Thoughts on the value and/or complexity of implementation of any of these?

...Robert

Robert Haas wrote:
> While investigating some performance problems recently I've had cause
> to think about the way PostgreSQL uses hash joins.  So here are a few
> thoughts.  Some of these have been brought up before.
> 
> 1. When the hash is not expected to spill to disk, it preserves the
> pathkeys of the outer side of the join.  If the optimizer were allowed
> to assume that, it could produce significantly more efficient query
> plans in some cases.  The problem is what to do if we start executing
> the query and find out that we have more stuff to hash than we expect,
> such that we need multiple batches?  Now the results won't be sorted.
> I think we could handle this as follows: Don't count on the hash join
> to preserve pathkeys unless it helps, and only rely on it when it
> seems as if the hash table will still fit even if it turns out to be,
> say, three times as big as expected.  But if you are counting on the
> hash join to preserve pathkeys, then pass that information to the
> executor.  When the executor is asked to perform a hash join, it will
> first hash the inner side of the relation.  At that point, we know
> whether we've succesfully gotten everything into a single batch, or
> not.  If we have, perform the join normally.  If the worst has
> happened and we've gone multi-batch, then perform the join and sort
> the output before returning it.  The performance will suck, but at
> least you'll get the right answer.
> 
> Previous in-passing reference to this idea here:
> http://archives.postgresql.org/pgsql-hackers/2008-09/msg00806.php

Hmm, instead of a sorting the output if the worst happens, a final merge 
step as in a merge sort would be enough.

> 2. Consider building the hash table lazily.  I often see query planner
> pick a hash join over a nested inner indexscan because it thinks that
> it'll save enough time making hash probes rather than index probes to
> justify the time spent building the hash table up front.  But
> sometimes the relation that's being hashed has a couple thousand rows,
> only a tiny fraction of which will ever be retrieved from the hash
> table.  We can predict when this is going to happen because n_distinct
> for the outer column will be much less than the size of the inner rel.
>  In that case, we could consider starting with an empty hash table
> that effectively acts as a cache.  Each time a value is probed, we
> look it up in the hash table.  If there's no entry, we use an index
> scan to find the matching rows and insert them into the hash table.
> Negative results must also be cached.

Yeah, that would be quite nice. One problem is that our ndistinct 
estimates are not very accurate.

> 3. Avoid building the exact same hash table twice in the same query.
> This happens more often you'd think.  For example, a table may have
> two columns creator_id and last_updater_id which both reference person
> (id).  If you're considering a hash join between paths A and B, you
> could conceivably check whether what is essentially a duplicate of B
> has already been hashed somewhere within path A.  If so, you can reuse
> that same hash table at zero startup-cost.

That seems like a quite simple thing to do. But would it work for a 
multi-batch hash table?

> 4. As previously discussed, avoid hashing for distinct and then
> hashing the results for a hash join on the same column with the same
> operators.

This seems essentially an extension of idea 3.

--   Heikki Linnakangas  EnterpriseDB   http://www.enterprisedb.com

On Fri, Apr 3, 2009 at 1:48 AM, Heikki Linnakangas
<heikki.linnakangas@enterprisedb.com> wrote:
> Robert Haas wrote:
>>
>> While investigating some performance problems recently I've had cause
>> to think about the way PostgreSQL uses hash joins.  So here are a few
>> thoughts.  Some of these have been brought up before.
>>
>> 1. When the hash is not expected to spill to disk, it preserves the
>> pathkeys of the outer side of the join.  If the optimizer were allowed
>> to assume that, it could produce significantly more efficient query
>> plans in some cases.  The problem is what to do if we start executing
>> the query and find out that we have more stuff to hash than we expect,
>> such that we need multiple batches?  Now the results won't be sorted.
>> I think we could handle this as follows: Don't count on the hash join
>> to preserve pathkeys unless it helps, and only rely on it when it
>> seems as if the hash table will still fit even if it turns out to be,
>> say, three times as big as expected.  But if you are counting on the
>> hash join to preserve pathkeys, then pass that information to the
>> executor.  When the executor is asked to perform a hash join, it will
>> first hash the inner side of the relation.  At that point, we know
>> whether we've succesfully gotten everything into a single batch, or
>> not.  If we have, perform the join normally.  If the worst has
>> happened and we've gone multi-batch, then perform the join and sort
>> the output before returning it.  The performance will suck, but at
>> least you'll get the right answer.
>>
>> Previous in-passing reference to this idea here:
>> http://archives.postgresql.org/pgsql-hackers/2008-09/msg00806.php
>
> Hmm, instead of a sorting the output if the worst happens, a final merge
> step as in a merge sort would be enough.

Yeah - good point.

>> 2. Consider building the hash table lazily.  I often see query planner
>> pick a hash join over a nested inner indexscan because it thinks that
>> it'll save enough time making hash probes rather than index probes to
>> justify the time spent building the hash table up front.  But
>> sometimes the relation that's being hashed has a couple thousand rows,
>> only a tiny fraction of which will ever be retrieved from the hash
>> table.  We can predict when this is going to happen because n_distinct
>> for the outer column will be much less than the size of the inner rel.
>>  In that case, we could consider starting with an empty hash table
>> that effectively acts as a cache.  Each time a value is probed, we
>> look it up in the hash table.  If there's no entry, we use an index
>> scan to find the matching rows and insert them into the hash table.
>> Negative results must also be cached.
>
> Yeah, that would be quite nice. One problem is that our ndistinct estimates
> are not very accurate.

Well, the right solution to that problem is to fix our ndistinct estimates.  :-)

>> 3. Avoid building the exact same hash table twice in the same query.
>> This happens more often you'd think.  For example, a table may have
>> two columns creator_id and last_updater_id which both reference person
>> (id).  If you're considering a hash join between paths A and B, you
>> could conceivably check whether what is essentially a duplicate of B
>> has already been hashed somewhere within path A.  If so, you can reuse
>> that same hash table at zero startup-cost.
>
> That seems like a quite simple thing to do. But would it work for a
> multi-batch hash table?

I think not.

>> 4. As previously discussed, avoid hashing for distinct and then
>> hashing the results for a hash join on the same column with the same
>> operators.
>
> This seems essentially an extension of idea 3.

In theory, yes, but in practice, this case is easy to detect for an
arbitrary inner rel, and the other case is not.

Off to JDCon...

...Robert

On Fri, Apr 03, 2009 at 08:03:33AM -0400, Robert Haas wrote:
> On Fri, Apr 3, 2009 at 1:48 AM, Heikki Linnakangas
> <heikki.linnakangas@enterprisedb.com> wrote:
> > Robert Haas wrote:
> >>
> >> While investigating some performance problems recently I've had cause
> >> to think about the way PostgreSQL uses hash joins. ?So here are a few
> >> thoughts. ?Some of these have been brought up before.
> >>
> >> 1. When the hash is not expected to spill to disk, it preserves the
> >> pathkeys of the outer side of the join. ?If the optimizer were allowed
> >> to assume that, it could produce significantly more efficient query
> >> plans in some cases. ?The problem is what to do if we start executing
> >> the query and find out that we have more stuff to hash than we expect,
> >> such that we need multiple batches? ?Now the results won't be sorted.
> >> I think we could handle this as follows: Don't count on the hash join
> >> to preserve pathkeys unless it helps, and only rely on it when it
> >> seems as if the hash table will still fit even if it turns out to be,
> >> say, three times as big as expected. ?But if you are counting on the
> >> hash join to preserve pathkeys, then pass that information to the
> >> executor. ?When the executor is asked to perform a hash join, it will
> >> first hash the inner side of the relation. ?At that point, we know
> >> whether we've succesfully gotten everything into a single batch, or
> >> not. ?If we have, perform the join normally. ?If the worst has
> >> happened and we've gone multi-batch, then perform the join and sort
> >> the output before returning it. ?The performance will suck, but at
> >> least you'll get the right answer.
> >>
> >> Previous in-passing reference to this idea here:
> >> http://archives.postgresql.org/pgsql-hackers/2008-09/msg00806.php
> >
> > Hmm, instead of a sorting the output if the worst happens, a final merge
> > step as in a merge sort would be enough.
> 
> Yeah - good point.
> 
> >> 2. Consider building the hash table lazily. ?I often see query planner
> >> pick a hash join over a nested inner indexscan because it thinks that
> >> it'll save enough time making hash probes rather than index probes to
> >> justify the time spent building the hash table up front. ?But
> >> sometimes the relation that's being hashed has a couple thousand rows,
> >> only a tiny fraction of which will ever be retrieved from the hash
> >> table. ?We can predict when this is going to happen because n_distinct
> >> for the outer column will be much less than the size of the inner rel.
> >> ?In that case, we could consider starting with an empty hash table
> >> that effectively acts as a cache. ?Each time a value is probed, we
> >> look it up in the hash table. ?If there's no entry, we use an index
> >> scan to find the matching rows and insert them into the hash table.
> >> Negative results must also be cached.
> >
> > Yeah, that would be quite nice. One problem is that our ndistinct estimates
> > are not very accurate.
> 
> Well, the right solution to that problem is to fix our ndistinct estimates.  :-)

Also, as seen in the hash index build performance patch, it would be better
to set the initial hash size bigger than needed to avoid the inter-page
shuffle if the guess is wrong.

Ken

> While investigating some performance problems recently I've had cause
> to think about the way PostgreSQL uses hash joins.  So here are a few
> thoughts.  Some of these have been brought up before.
>
> 1. When the hash is not expected to spill to disk, it preserves the
> pathkeys of the outer side of the join.  If the optimizer were allowed
> to assume that, it could produce significantly more efficient query
> plans in some cases.

This is definitely possible, but you will have to dynamically modify the
execution path if the hash join ends up to be more than one batch.

> 3. Avoid building the exact same hash table twice in the same query.
> This happens more often you'd think.  For example, a table may have
> two columns creator_id and last_updater_id which both reference person
> (id).  If you're considering a hash join between paths A and B, you
> could conceivably check whether what is essentially a duplicate of B
> has already been hashed somewhere within path A.  If so, you can reuse
> that same hash table at zero startup-cost.
> 4. As previously discussed, avoid hashing for distinct and then
> hashing the results for a hash join on the same column with the same
> operators.
>
> Thoughts on the value and/or complexity of implementation of any of
these?

I would be interested in working with you on any of these changes to
hash join if you decide to pursue them.   I am especially interested in
looking at the hash aggregation code and potentially improving its
efficiency.

We have implemented a multi-way hash join (can join more than 2 tables
at a time) which may help with cases #3 and #4.  Performance results
look very good, and we are planning on building a patch for this over
the summer.

--
Ramon Lawrence

On Fri, Apr 3, 2009 at 11:24 AM, Lawrence, Ramon <ramon.lawrence@ubc.ca> wrote:
> I would be interested in working with you on any of these changes to
> hash join if you decide to pursue them.   I am especially interested in
> looking at the hash aggregation code and potentially improving its
> efficiency.

Wow, that would be great!

> We have implemented a multi-way hash join (can join more than 2 tables
> at a time) which may help with cases #3 and #4.  Performance results
> look very good, and we are planning on building a patch for this over
> the summer.

I'd be interested in hearing you cope with this on the planner end of things.

...Robert

On Thu, 2009-04-02 at 22:08 -0400, Robert Haas wrote:

> 3. Avoid building the exact same hash table twice in the same query.
> This happens more often you'd think.  For example, a table may have
> two columns creator_id and last_updater_id which both reference person
> (id).  If you're considering a hash join between paths A and B, you
> could conceivably check whether what is essentially a duplicate of B
> has already been hashed somewhere within path A.  If so, you can reuse
> that same hash table at zero startup-cost.

This is also interesting because there is potential to save memory
through that approach, which allows us to allocate work_mem higher and
avoid multi-batch altogether.

I would be especially interested in using a shared memory hash table
that *all* backends can use - if the table is mostly read-only, as
dimension tables often are in data warehouse applications. That would
give zero startup cost and significantly reduced memory.

-- Simon Riggs           www.2ndQuadrant.comPostgreSQL Training, Services and Support

>> 1. When the hash is not expected to spill to disk, it preserves the
>> pathkeys of the outer side of the join.  If the optimizer were allowed
>> to assume that, it could produce significantly more efficient query
>> plans in some cases.
>
> This is definitely possible, but you will have to dynamically modify the
> execution path if the hash join ends up to be more than one batch.

Yeah, this item seems to be another case where having a "conditional"
branch in the plan would be valuable. What's interesting is that it's
branching based on whether the hash has spilled into batches rather
than whether the number of rows is greater or less than some breakeven
point. It looks like these branche nodes are going to need to know
more than just the generic plan parameters. They're going to need to
know about specifics like "sort has spilled to disk" or "hash has
spilled into batches" etc.


I like the idea of coalescing hash tables. I'm not sure the order in
which the planner decides on things is conducive to being able to make
good decisions about it though. Even if we did it afterwards without
adjusting the planner it might still be worthwhile though.

Incidentally a similar optimization is possible for materialize or
even sorts. They may not come up nearly so often since you would
normally want to go around adding indexes if you're repeatedly sorting
on the same columns. Biut it might not be any harder to get them all
in one swoop.

--
greg

On Fri, Apr 3, 2009 at 5:41 PM, Simon Riggs <simon@2ndquadrant.com> wrote:
>
> I would be especially interested in using a shared memory hash table
> that *all* backends can use - if the table is mostly read-only, as
> dimension tables often are in data warehouse applications. That would
> give zero startup cost and significantly reduced memory.

I think that's a non-starter due to visibility issues and handling
inserts and updates. Even just reusing a hash from one execution in a
later execution of the same plan would be tricky since we would have
to expire it if the snapshot changes.

Alternately, you could say that what you describe is addressed by hash
indexes. The fact that they're not great performers compared to
in-memory hashes comes down to dealing with updates and vaccum which
is pretty much the same issue.

Hm.  I wonder if we need a whole class of index algorithms to deal
specifically with read-only tables. A hash table on a read-only table
could spend a lot of time to generate a perfect or near-perfect hash
function and then pack the hash table very densely without any bucket
chains. That might make it a big winner over a dynamic structure which
has to deal with handling inserts and so on. I'm assuming that if you
mark the table read-write it just marks the index invalid and you have
to rebuild it later once you've marked the table read-only again.

-- 
greg

On Fri, 2009-04-03 at 18:03 +0100, Greg Stark wrote:

> I wonder if we need a whole class of index algorithms to deal
> specifically with read-only tables

I think we can drop the word "index" from the sentence as well.

"Read-only" isn't an isolated case. Often you find many read-only tables
alongside rapidly changing tables. So even the busiest of databases can
benefit from read-only optimisations. So I want MVCC *and* read only,
not MVCC everywhere (or MVCC nowhere if customer changes horses to get
read-only benefits elsewhere).

Having changes to those tables cause much heavier additional work is OK,
if judged on a cost/benefit basis. So the case I care about ought to be
called "read-mostly" but we're talking write:read ratios of millions:1.

-- Simon Riggs           www.2ndQuadrant.comPostgreSQL Training, Services and Support

Simon Riggs <simon@2ndQuadrant.com> wrote: 
> "Read-only" isn't an isolated case. Often you find many read-only
tables
> alongside rapidly changing tables. So even the busiest of databases
can
> benefit from read-only optimisations.
> Having changes to those tables cause much heavier additional work is
OK,
> if judged on a cost/benefit basis. So the case I care about ought to
be
> called "read-mostly" but we're talking write:read ratios of
millions:1.
We have tables which are frequently JOINed to other tables in complex
SELECT statements, but which are only modified as part of a software
release.  It would be OK with us if switching between modifiable or
not actually took as much time as, for example, a CLUSTER command if
it gave us a performance benefit when used in these complex queries
when in read-only mode.
-Kevin

> > I would be especially interested in using a shared memory hash table
> > that *all* backends can use - if the table is mostly read-only, as
> > dimension tables often are in data warehouse applications. That
would
> > give zero startup cost and significantly reduced memory.
>
> I think that's a non-starter due to visibility issues and handling
> inserts and updates. Even just reusing a hash from one execution in a
> later execution of the same plan would be tricky since we would have
> to expire it if the snapshot changes.

If your data set is nearly read-only, materialized views would be a
better way to go and would require no hash join changes.

The idea of perfect hash functions for dimension tables is very
interesting.  If the data set is near static, it is possible to compute
them once in a few minutes time for a million tuple table and then
re-use them until they change.  The research has shown it is possible,
but I do not know if anyone has actually implemented it in a real DBMS.
An implementation could be something to try if there is interest.

--
Ramon Lawrence

On Fri, Apr 3, 2009 at 12:55 PM, Greg Stark <stark@enterprisedb.com> wrote:
>>> 1. When the hash is not expected to spill to disk, it preserves the
>>> pathkeys of the outer side of the join.  If the optimizer were allowed
>>> to assume that, it could produce significantly more efficient query
>>> plans in some cases.
>>
>> This is definitely possible, but you will have to dynamically modify the
>> execution path if the hash join ends up to be more than one batch.
>
> Yeah, this item seems to be another case where having a "conditional"
> branch in the plan would be valuable. What's interesting is that it's
> branching based on whether the hash has spilled into batches rather
> than whether the number of rows is greater or less than some breakeven
> point. It looks like these branche nodes are going to need to know
> more than just the generic plan parameters. They're going to need to
> know about specifics like "sort has spilled to disk" or "hash has
> spilled into batches" etc.

In this particular case, the operation that has to be performed is
more specific than "sort", it's "merge this set of sorted tapes".  So
it's more subtle than just inserting a sort node.

> I like the idea of coalescing hash tables. I'm not sure the order in
> which the planner decides on things is conducive to being able to make
> good decisions about it though. Even if we did it afterwards without
> adjusting the planner it might still be worthwhile though.

I don't see why hash_inner_and_outer can't walk the outer path looking
for suitable hashes to reuse.  I think the question is how aggressive
we want to be in performing that search.  If we limit the search to
hashes on base tables without restriction conditions, we'll probably
catch most of the interesting cases, but obviously not all of them.
If we look for hashes on baserels with restriction conditions or
hashes on joinrels, etc., we might pick up a few more cases, but at
the expense of increased planning time.

The advantage of searching in the executor, I suppose, is that the
checks don't have to be as cheap, since you're only checking the plan
that has already won, rather than lots and lots of potential plans.
On the other hand, your costing will be less accurate, which could
lead to bad decisions elsewhere.

> Incidentally a similar optimization is possible for materialize or
> even sorts. They may not come up nearly so often since you would
> normally want to go around adding indexes if you're repeatedly sorting
> on the same columns. Biut it might not be any harder to get them all
> in one swoop.

At least in my experience, sort and materialize nodes are pretty rare,
so I'm not sure it would be worth the time it would take to search for
them.  In most cases it seems to be cheaper to hash the inner and
outer paths than to sort even one of them and then merge-join the
result.  When I do get these sorts of paths, they tend to be in
larger, more complex queries where there's less chance of useful
reuse.  But my experience might not be representative...

...Robert

Robert Haas <robertmhaas@gmail.com> writes:
> I don't see why hash_inner_and_outer can't walk the outer path looking
> for suitable hashes to reuse.  I think the question is how aggressive
> we want to be in performing that search.

Correct, but you've got the details all wrong.  The real problem is that
the planner might discard a join path hash(A,B) at level 2 because it
loses compared to, say, merge(A,B).  But when we get to level three,
perhaps hash(hash(A,B),C) would've been the best plan due to synergy
of the two hashes.  We'll never find that out unless we keep the
"inferior" hash path around.  We can certainly do that; the question
is what's it going to cost us to allow more paths to survive to the
next join level.  (And I'm afraid the answer may be "plenty"; it's a
combinatorial explosion we're looking at here.)

>> Incidentally a similar optimization is possible for materialize or
>> even sorts.

The planner already goes to great lengths to avoid extra sorts for
multiple levels of mergejoin ... that's what all the "pathkey" thrashing
is about.  It's pretty expensive.
        regards, tom lane

On Fri, Apr 3, 2009 at 4:29 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Robert Haas <robertmhaas@gmail.com> writes:
>> I don't see why hash_inner_and_outer can't walk the outer path looking
>> for suitable hashes to reuse.  I think the question is how aggressive
>> we want to be in performing that search.
>
> Correct, but you've got the details all wrong.  The real problem is that
> the planner might discard a join path hash(A,B) at level 2 because it
> loses compared to, say, merge(A,B).  But when we get to level three,
> perhaps hash(hash(A,B),C) would've been the best plan due to synergy
> of the two hashes.  We'll never find that out unless we keep the
> "inferior" hash path around.  We can certainly do that; the question
> is what's it going to cost us to allow more paths to survive to the
> next join level.  (And I'm afraid the answer may be "plenty"; it's a
> combinatorial explosion we're looking at here.)

That would be crazy.  I think doing it the way I suggested is correct,
just not guaranteed to catch every case.  The reality is that even if
we took Greg Stark's suggestion of detecting this situation only in
the executor, we'd still get some benefit out of this.  If we take my
intermediate approach, we'll catch more cases where this is a win.
What you're suggesting here would catch every conceivable case, but at
the expense of what I'm sure would be an unacceptable increase in
planning time for very limit benefit.

...Robert

Robert Haas <robertmhaas@gmail.com> writes:
> On Fri, Apr 3, 2009 at 4:29 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Correct, but you've got the details all wrong. �The real problem is that
>> the planner might discard a join path hash(A,B) at level 2 because it
>> loses compared to, say, merge(A,B). �But when we get to level three,
>> perhaps hash(hash(A,B),C) would've been the best plan due to synergy
>> of the two hashes. �We'll never find that out unless we keep the
>> "inferior" hash path around. �We can certainly do that; the question
>> is what's it going to cost us to allow more paths to survive to the
>> next join level. �(And I'm afraid the answer may be "plenty"; it's a
>> combinatorial explosion we're looking at here.)

> That would be crazy.  I think doing it the way I suggested is correct,
> just not guaranteed to catch every case.  The reality is that even if
> we took Greg Stark's suggestion of detecting this situation only in
> the executor, we'd still get some benefit out of this.  If we take my
> intermediate approach, we'll catch more cases where this is a win.
> What you're suggesting here would catch every conceivable case, but at
> the expense of what I'm sure would be an unacceptable increase in
> planning time for very limit benefit.

Maybe, maybe not.  I've seen plenty of plans that have several
mergejoins stacked up on top of each other with no intervening sorts.
There is 0 chance that the planner would have produced that if it
thought that it had to re-sort at each level; something else would have
looked cheaper.  I think that your proposals will end up getting very
little of the possible benefit, because the planner will fail to choose
plan trees in which the optimization can be exploited.
        regards, tom lane

On 3 Apr 2009, at 19:44, Lawrence, Ramon wrote:

>>> I would be especially interested in using a shared memory hash table
>>> that *all* backends can use - if the table is mostly read-only, as
>>> dimension tables often are in data warehouse applications. That
> would
>>> give zero startup cost and significantly reduced memory.
>>
>> I think that's a non-starter due to visibility issues and handling
>> inserts and updates. Even just reusing a hash from one execution in a
>> later execution of the same plan would be tricky since we would have
>> to expire it if the snapshot changes.
>
> If your data set is nearly read-only, materialized views would be a
> better way to go and would require no hash join changes.

I think what he means is that some of the tables in join are  
effectively read-only. So materialized views are nono here. Unless you  
mean just a partial ones.
I have to say, that frankly I got same problem, and plausibly my  
schemas could benefit from changes discussed here.

Hi,

Le 3 avr. 09 à 22:29, Tom Lane a écrit :
> Correct, but you've got the details all wrong.  The real problem is
> that
> the planner might discard a join path hash(A,B) at level 2 because it
> loses compared to, say, merge(A,B).  But when we get to level three,
> perhaps hash(hash(A,B),C) would've been the best plan due to synergy
> of the two hashes.  We'll never find that out unless we keep the
> "inferior" hash path around.  We can certainly do that; the question
> is what's it going to cost us to allow more paths to survive to the
> next join level.  (And I'm afraid the answer may be "plenty"; it's a
> combinatorial explosion we're looking at here.)

I remember having done some board game simulation project at school,
using alpha-beta algorithms with cuts, and as an optimisation a
minimax too. Those are heuristics, but that you can decide to run on
the full set of possible trees when you want a global optimum rather
than a local one.

Now, I don't know the specifics of the planner code, but would it be
possible to use a minimax kind of heuristic? Then a planner effort GUC
would allow users to choose whether they want to risk the "plenty"
combinatorial explosion in some requests.

It could be that the planner already is smarter than this of course,
and I can't even say I'd be surprised about it, but still trying...
--
dim

http://en.wikipedia.org/wiki/Minimax

On Fri, Apr 3, 2009 at 5:10 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Robert Haas <robertmhaas@gmail.com> writes:
>> On Fri, Apr 3, 2009 at 4:29 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>>> Correct, but you've got the details all wrong.  The real problem is that
>>> the planner might discard a join path hash(A,B) at level 2 because it
>>> loses compared to, say, merge(A,B).  But when we get to level three,
>>> perhaps hash(hash(A,B),C) would've been the best plan due to synergy
>>> of the two hashes.  We'll never find that out unless we keep the
>>> "inferior" hash path around.  We can certainly do that; the question
>>> is what's it going to cost us to allow more paths to survive to the
>>> next join level.  (And I'm afraid the answer may be "plenty"; it's a
>>> combinatorial explosion we're looking at here.)
>
>> That would be crazy.  I think doing it the way I suggested is correct,
>> just not guaranteed to catch every case.  The reality is that even if
>> we took Greg Stark's suggestion of detecting this situation only in
>> the executor, we'd still get some benefit out of this.  If we take my
>> intermediate approach, we'll catch more cases where this is a win.
>> What you're suggesting here would catch every conceivable case, but at
>> the expense of what I'm sure would be an unacceptable increase in
>> planning time for very limit benefit.
>
> Maybe, maybe not.  I've seen plenty of plans that have several
> mergejoins stacked up on top of each other with no intervening sorts.
> There is 0 chance that the planner would have produced that if it
> thought that it had to re-sort at each level; something else would have
> looked cheaper.  I think that your proposals will end up getting very
> little of the possible benefit, because the planner will fail to choose
> plan trees in which the optimization can be exploited.

Well, I'm all ears if you have suggestions for improvement.  For
sorts, we use PathKeys to represent the ordering of each path and keep
the paths for each set of pathkeys.  By analogy, we could maintain a
list of PathHash structures for each path representing the tables that
had already been hashed.  add_path() would then have to consider both
the PathHash structures and the PathKey structures before concluding
that a path was definitely worse than some path previously found.  At
each level of the join tree, we'd need to truncate PathHash structures
that provably have no further use (e.g. on a base table that does not
appear again above the level of the join already planned) to avoid
keeping around paths that appeared to be better only because we didn't
know that the paths they have hashed are worthless in practice.  Maybe
that wouldn't even be that expensive, actually, because there will be
lots of cases where you know the relevant table doesn't appear
elsewhere in the query and not save any extra paths.  But I think we'd
have to write the code and benchmark it to really know.

I guess the reason I'm not too worked up about this is because my
experience is that the planner nearly always prefers hash joins on
small tables, even when an index is present - the queries I'm worried
about optimizing don't need any additional encouragement to use hash
joins; they're doing it already.  But certainly it doesn't hurt to see
how many cases we can pick up.

...Robert

Are there any TODOs here?

---------------------------------------------------------------------------

Robert Haas wrote:
> On Fri, Apr 3, 2009 at 5:10 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> > Robert Haas <robertmhaas@gmail.com> writes:
> >> On Fri, Apr 3, 2009 at 4:29 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> >>> Correct, but you've got the details all wrong. ?The real problem is that
> >>> the planner might discard a join path hash(A,B) at level 2 because it
> >>> loses compared to, say, merge(A,B). ?But when we get to level three,
> >>> perhaps hash(hash(A,B),C) would've been the best plan due to synergy
> >>> of the two hashes. ?We'll never find that out unless we keep the
> >>> "inferior" hash path around. ?We can certainly do that; the question
> >>> is what's it going to cost us to allow more paths to survive to the
> >>> next join level. ?(And I'm afraid the answer may be "plenty"; it's a
> >>> combinatorial explosion we're looking at here.)
> >
> >> That would be crazy. ?I think doing it the way I suggested is correct,
> >> just not guaranteed to catch every case. ?The reality is that even if
> >> we took Greg Stark's suggestion of detecting this situation only in
> >> the executor, we'd still get some benefit out of this. ?If we take my
> >> intermediate approach, we'll catch more cases where this is a win.
> >> What you're suggesting here would catch every conceivable case, but at
> >> the expense of what I'm sure would be an unacceptable increase in
> >> planning time for very limit benefit.
> >
> > Maybe, maybe not. ?I've seen plenty of plans that have several
> > mergejoins stacked up on top of each other with no intervening sorts.
> > There is 0 chance that the planner would have produced that if it
> > thought that it had to re-sort at each level; something else would have
> > looked cheaper. ?I think that your proposals will end up getting very
> > little of the possible benefit, because the planner will fail to choose
> > plan trees in which the optimization can be exploited.
> 
> Well, I'm all ears if you have suggestions for improvement.  For
> sorts, we use PathKeys to represent the ordering of each path and keep
> the paths for each set of pathkeys.  By analogy, we could maintain a
> list of PathHash structures for each path representing the tables that
> had already been hashed.  add_path() would then have to consider both
> the PathHash structures and the PathKey structures before concluding
> that a path was definitely worse than some path previously found.  At
> each level of the join tree, we'd need to truncate PathHash structures
> that provably have no further use (e.g. on a base table that does not
> appear again above the level of the join already planned) to avoid
> keeping around paths that appeared to be better only because we didn't
> know that the paths they have hashed are worthless in practice.  Maybe
> that wouldn't even be that expensive, actually, because there will be
> lots of cases where you know the relevant table doesn't appear
> elsewhere in the query and not save any extra paths.  But I think we'd
> have to write the code and benchmark it to really know.
> 
> I guess the reason I'm not too worked up about this is because my
> experience is that the planner nearly always prefers hash joins on
> small tables, even when an index is present - the queries I'm worried
> about optimizing don't need any additional encouragement to use hash
> joins; they're doing it already.  But certainly it doesn't hurt to see
> how many cases we can pick up.
> 
> ...Robert
> 
> -- 
> Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-hackers

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + If your life is a hard drive, Christ can be your backup. +

On Tue, Apr 7, 2009 at 9:55 AM, Bruce Momjian <bruce@momjian.us> wrote:
> Are there any TODOs here?

I'd say that all of the items listed in my original email could be
TODOs.  I'm planning to work on as many of them as I have time for.
Ramon Lawrence is also working on some related ideas, as discussed
upthread.  AFAICS no one has expressed the idea that anything that's
been talked about is a bad idea, so it's just a question of finding
enough round tuits.

...Robert

Robert Haas wrote:
> On Tue, Apr 7, 2009 at 9:55 AM, Bruce Momjian <bruce@momjian.us> wrote:
> > Are there any TODOs here?
> 
> I'd say that all of the items listed in my original email could be
> TODOs.  I'm planning to work on as many of them as I have time for.
> Ramon Lawrence is also working on some related ideas, as discussed
> upthread.  AFAICS no one has expressed the idea that anything that's
> been talked about is a bad idea, so it's just a question of finding
> enough round tuits.

OK, would you please add them to the Index/Hash section of the TODO
list;  I am afraid I will not do the justice.

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + If your life is a hard drive, Christ can be your backup. +

On Tue, Apr 7, 2009 at 5:11 PM, Bruce Momjian <bruce@momjian.us> wrote:
> Robert Haas wrote:
>> On Tue, Apr 7, 2009 at 9:55 AM, Bruce Momjian <bruce@momjian.us> wrote:
>> > Are there any TODOs here?
>>
>> I'd say that all of the items listed in my original email could be
>> TODOs.  I'm planning to work on as many of them as I have time for.
>> Ramon Lawrence is also working on some related ideas, as discussed
>> upthread.  AFAICS no one has expressed the idea that anything that's
>> been talked about is a bad idea, so it's just a question of finding
>> enough round tuits.
>
> OK, would you please add them to the Index/Hash section of the TODO
> list;  I am afraid I will not do the justice.

I think perhaps Optimizer / Executor would be more appropriate, since
these are not about hash indices but rather about hash joins.  I will
look at doing that.

Also I think the last item under Index / Hash is actually NOT done,
and belongs in the main index section rather than Index / Hash.

The first item in the Index / Hash section doesn't really look like a
TODO, or at the very least it's unclear what the action item is
supposed to be.

...Robert

Robert Haas wrote:
> On Tue, Apr 7, 2009 at 5:11 PM, Bruce Momjian <bruce@momjian.us> wrote:
> > Robert Haas wrote:
> >> On Tue, Apr 7, 2009 at 9:55 AM, Bruce Momjian <bruce@momjian.us> wrote:
> >> > Are there any TODOs here?
> >>
> >> I'd say that all of the items listed in my original email could be
> >> TODOs. ?I'm planning to work on as many of them as I have time for.
> >> Ramon Lawrence is also working on some related ideas, as discussed
> >> upthread. ?AFAICS no one has expressed the idea that anything that's
> >> been talked about is a bad idea, so it's just a question of finding
> >> enough round tuits.
> >
> > OK, would you please add them to the Index/Hash section of the TODO
> > list; ?I am afraid I will not do the justice.
> 
> I think perhaps Optimizer / Executor would be more appropriate, since
> these are not about hash indices but rather about hash joins.  I will
> look at doing that.

Yes, please.

> Also I think the last item under Index / Hash is actually NOT done,
> and belongs in the main index section rather than Index / Hash.

Yep, I didn't realize that editing "Index" also does the subsections,
while editing the subsections doesn't edit the upper level.

> The first item in the Index / Hash section doesn't really look like a
> TODO, or at the very least it's unclear what the action item is
> supposed to be.

Yep, remove, thanks.

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + If your life is a hard drive, Christ can be your backup. +

On 2009-04-03, Simon Riggs <simon@2ndQuadrant.com> wrote:
>
> On Fri, 2009-04-03 at 18:03 +0100, Greg Stark wrote:
>
>> I wonder if we need a whole class of index algorithms to deal
>> specifically with read-only tables
>
> I think we can drop the word "index" from the sentence as well.
>
> "Read-only" isn't an isolated case. Often you find many read-only tables
> alongside rapidly changing tables. So even the busiest of databases can
> benefit from read-only optimisations. So I want MVCC *and* read only,
> not MVCC everywhere (or MVCC nowhere if customer changes horses to get
> read-only benefits elsewhere).
>
> Having changes to those tables cause much heavier additional work is OK,
> if judged on a cost/benefit basis. So the case I care about ought to be
> called "read-mostly" but we're talking write:read ratios of millions:1.

For the record and in case anyone gets interested in following up the
idea of "read only" tables, see also:

http://thread.gmane.org/gmane.comp.db.postgresql.devel.general/76366

On Tue, Apr 7, 2009 at 5:57 PM, Bruce Momjian <bruce@momjian.us> wrote:
>> I think perhaps Optimizer / Executor would be more appropriate, since
>> these are not about hash indices but rather about hash joins.  I will
>> look at doing that.
>
> Yes, please.

Done.  See what you think...

>> Also I think the last item under Index / Hash is actually NOT done,
>> and belongs in the main index section rather than Index / Hash.
>
> Yep, I didn't realize that editing "Index" also does the subsections,
> while editing the subsections doesn't edit the upper level.

Heh.  I'd write some webapps to do some of these things, but I haven't
been able to interest anyone in providing me with a
postgresql.org-based hosting arrangement.

>> The first item in the Index / Hash section doesn't really look like a
>> TODO, or at the very least it's unclear what the action item is
>> supposed to be.
>
> Yep, remove, thanks.

...Robert