Re: slow join on postgresql6.5

At 12:49 PM 3/30/00 -0500, Bernard Adrian Frankpitt wrote:

Implementing the change is probably not as bad as it seems, access
methods are beautifully self-contained in Postgres. The changes are
quite fundamental though, and you sure would want to get it right. You
would also want to retain the current behavior for users who do lots of
updates.

Again, if you read my post carefully I was simply pointing out that
RI semantics will degrade rapidly (for some tables) once the index
is unusable because a full table scan will be necessary (where at
worst Oracle, say, would read the entire index to get the necessary
information, which for some tables won't be nearly as bad as going
to the actual table). I was trying to point out that the degradation
may be more spectacular than, say, with Oracle because PG always
needs to go to the table rather than simply use the data in the
index.

And that it is worth documenting. And that after I do MATCH PARTIAL
semantics for 7.1 I'll try to find time to do some documenting of
RI, including information on "gotchas" such as this one.

(people are likely to be mystified if setting the first column of
a foreign key to NULL makes PG go away for a long time while
setting it to a non-NULL value doesn't, which is exactly what will
happen for SOME large tables if MATCH PARTIAL and MATCH <unspecified>
is used)

- Don Baccus, Portland OR <dhogaza@pacifier.com>
Nature photos, on-line guides, Pacific Northwest
Rare Bird Alert Service and other goodies at
http://donb.photo.net.

-----Original Message-----
From: majordomo-owner@hub.org [mailto:majordomo-owner@hub.org]On Behalf
Of Don Baccus

Whatever ... in this particular case - referential integrity
with MATCH <unspecified> and MATCH PARTIAL and multi-column
foreign keys - performance will likely drop spectacularly once the
leading column is NULL, while (say) with Oracle you'd expect much
less of a performance hit.

As for NULL,it seems possible to look up NULL keys in a btree index
because NULL == NULL for btree indexes.
I've wondered why PostgreSQL's planner/executor never looks up
indexes for queries using 'IS NULL'.

Regards.

Hiroshi Inoue
Inoue@tpf.co.jp

At 07:05 PM 3/31/00 +0900, Hiroshi Inoue wrote:

-----Original Message-----
From: majordomo-owner@hub.org [mailto:majordomo-owner@hub.org]On Behalf
Of Don Baccus

Whatever ... in this particular case - referential integrity
with MATCH <unspecified> and MATCH PARTIAL and multi-column
foreign keys - performance will likely drop spectacularly once the
leading column is NULL, while (say) with Oracle you'd expect much
less of a performance hit.

As for NULL,it seems possible to look up NULL keys in a btree index
because NULL == NULL for btree indexes.
I've wondered why PostgreSQL's planner/executor never looks up
indexes for queries using 'IS NULL'.

Unfortunately for the RI MATCH PARTIAL case, NULL is a "wildcard".

This doesn't affect the validity of your observation in the general
case, though.

- Don Baccus, Portland OR <dhogaza@pacifier.com>
Nature photos, on-line guides, Pacific Northwest
Rare Bird Alert Service and other goodies at
http://donb.photo.net.

-----Original Message-----
From: Don Baccus [mailto:dhogaza@pacifier.com]
Sent: Friday, March 31, 2000 11:34 PM

At 07:05 PM 3/31/00 +0900, Hiroshi Inoue wrote:

-----Original Message-----
From: majordomo-owner@hub.org [mailto:majordomo-owner@hub.org]On Behalf
Of Don Baccus

Whatever ... in this particular case - referential integrity
with MATCH <unspecified> and MATCH PARTIAL and multi-column
foreign keys - performance will likely drop spectacularly once the
leading column is NULL, while (say) with Oracle you'd expect much
less of a performance hit.

As for NULL,it seems possible to look up NULL keys in a btree index
because NULL == NULL for btree indexes.
I've wondered why PostgreSQL's planner/executor never looks up
indexes for queries using 'IS NULL'.

Unfortunately for the RI MATCH PARTIAL case, NULL is a "wildcard".

Oops I misunderstood NULL.

Hmm,is the following TODO worth the work ?
* Use index to restrict rows returned by multi-key index when used with
non-consecutive keys or OR clauses, so fewer heap accesses.

Probably this is for the case like
SELECT .. FROM .. WHERE key1 = val1 and key3 = val3;
,where (key1,key2,key3) is a multi-column index.
Currently index scan doesn't take 'key3=val3' into account because
(key1,key3) isn't consecutive.
The TODO may include the case
SELECT .. FROM .. WHERE key2 = val2;
Though we have to scan the index entirely,access to the main table
is needed only when key2 = val2. If (key2 = val2) is sufficiently
restrictive,
the scan would be faster than simple sequential scan.

Comments ?

Regards.

Hiroshi Inoue
Inoue@tpf.co.jp

As for NULL,it seems possible to look up NULL keys in a btree index
because NULL == NULL for btree indexes.
I've wondered why PostgreSQL's planner/executor never looks up
indexes for queries using 'IS NULL'.

Unfortunately for the RI MATCH PARTIAL case, NULL is a "wildcard".

Oops I misunderstood NULL.

Hmm,is the following TODO worth the work ?
* Use index to restrict rows returned by multi-key index when used with
non-consecutive keys or OR clauses, so fewer heap accesses.

This is a Vadim item.

-- 
  Bruce Momjian                        |  http://www.op.net/~candle
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

Thank you all very much for the help. The post really solved my problem.
Your help is greatly appreciated.

Wenjin Zheng
Bioinformatic Analyst
Biosource Technologies, Inc.
3333 Vaca Valley Parkway
Vacaville, CA 95688
(707)469-2353
email: wenjin.zheng@lsbc.com

-----Original Message-----
From: Tom Lane [mailto:tgl@sss.pgh.pa.us]
Sent: Thursday, March 30, 2000 8:11 AM
To: Don Baccus
Cc: Wenjin Zheng; pgsql-hackers@postgresql.org
Subject: Re: [HACKERS] slow join on postgresql6.5

Don Baccus <dhogaza@pacifier.com> writes:

This is an example where commercial systems that have indices
synchronized with data such that queries referencing only the
fields in indices can win big vs. PG in SOME (not all) cases.
In particular, when the indices are to a table that has a bunch
of other, perhaps long, columns. PG has to read the table and
drag all that dead weight around to do RI referential checking
and semantic actions.

Keep in mind, though, that once we have TOAST the long columns are
likely to get pushed out to a secondary table, so that the amount
of data you have to read is reduced (as long as you don't touch
any of the long columns, of course).

The main reason that Postgres indexes can't be used without also
consulting the main table is that we do not store transaction status
information in index entries, only in real tuples. After finding
an index entry we must still consult the referenced tuple to see
if it's been deleted, or even committed yet. I believe this is a
pretty good tradeoff. If we kept a copy of the status info in the
index, then UPDATE and DELETE would get hugely slower and more
complex, since they'd have to be able to find and mark all the
index entries pointing at a tuple as well as the tuple itself.
The extra info would also increase the size of index entries,
which is bad because the point of an index is that reading it
takes less disk traffic than reading the underlying table.
(BTW, to return to the original thread, one of the biggest reasons
that indexes with many columns are a loser is that they're so big.)

I suppose that keeping tuple status in index entries could be a win
on nearly-read-only tables, but I think that on average it'd be
a performance loser.

regards, tom lane