Re: Compound keys and foreign constraints

Wes,

it's extremely hard for me to understand what's going on here. My
thoughts are running in circles and everytime I think I can almost grasp
the problem it slips through my fingers again. Maybe I'm just getting
old, or it's the weather?

It looks like you managed to write a query with several closely
interwoven problems contributing to its poor performance.

.) There is a known problem in the optimizer, that it does not account
properly for cache hits in a nested loop with inner index scan. This
has been discussed before, but nobody has sent a patch so far.

.) Each access to messages in the inner scan of the nested loop cannot
return more than one row, because message_key is unique. It may return
no row, however, when the message identified by key doesn't fall into
the given date range, and it does this 97% of time. Using the compound
index is cheaper, because if the index tuple shows that the date doesn't
match, there's no need to fetch the heap tuple. Unfortunately the
planner doesn't believe that this is possible:
/* Don't believe estimates less than 1... */
if (tuples_fetched < 1.0)
tuples_fetched = 1.0;

.) Due to issues with multi-column index correlation the optimizer
tends to prefer indices with lesser columns.

This leads me to one more desparate recommendation:

CREATE INDEX use_me ON messages(message_date, message_key);

.) Selectivity:
> -> Nested Loop (cost=0.00..61907.05 rows=200 width=11)
> (actual time=83.232..32412.459 rows=312741 loops=1)
> -> Index Scan using addresses_i_address on addresses a
> (cost=0.00..3.01 rows=2 width=11)
> (actual time=0.074..0.517 rows=1 loops=1)
> Index Cond: ((address)::text ='...'::text)
> -> Index Scan using message_recipients_i_recipient on message_recipients r
> (cost=0.00..30569.25 rows=30622 width=21)
> (actual time=83.146..31609.149 rows=312741 loops=1)
> Index Cond: ("outer".address_key = r.recipient)

Alvaro has already commented on this 30K estimated vs. 300K actual rows
discrepancy. I'm not sure however that this is curable by increasing
statistics target, because the value to be looked up is not known at
planning time.

.) Join selectivity: Looking at the above plan snippet again, if we
assume that adresses and recipients are joined using a foreign key
relationship, it seems obvious that on the nested loop level there
cannot be less rows expected than on the index scan levels.

I have not checked the code, but there might be some room for
improvement in the planner. Doesn't look like low hanging fruit, though
:-(

.) I'm not sure whether a nested loop is the best join strategy between
messages and recipients. With enough memory a hash or merge join might
be the way to go. But joining tables with 700K and 300K rows is not
cheap and the low estimated row count makes a nested loop look very
attractive. And you cannot simply disable nested loops because it is
really the best method to join addresses and recipients. Maybe you
should run a few tests without the addresses table, comparing
r.recipient to a constant.

>Effective_cache_size is 50000, and sort_mem is 8192. Shared_buffers=16384.

shared_buffers looks ok. Set effective_cache_size to 80% of your
physical memory (or even more if it helps). Try to get a different join
method by gradually increasing sort_mem, for educational purposes even
to unreasonably high values if necessary.

.) There are some strange looking details in your prior messages.

You said this one was chosen by default
-> Nested Loop (cost=0.00..75565.60 rows=1 width=0)

and you had to delete an index to get
-> Nested Loop (cost=0.00..73745.26 rows=11 width=0)

The last one has lower cost. Why wasn't it chosen from the beginning?
Did you VACUUM and/or ANALYSE between test runs?

-> Index Scan using a_i_address on a (cost=0.00..6.00 rows=2 width=11)
(actual time=74.493..75.240 rows=1 loops=1)

75ms is quite slow for a 1 row index scan. Is your machine very busy?

-> Index Scan using a_i_address on a (cost=0.00..6.00 rows=2 width=11)
(actual time=40.610..40.616 rows=1 loops=1)
Still slow.

On Fri, 02 Apr 2004 11:08:21 -0600, <wespvp(at)syntegra(dot)com> wrote:
>db=> explain select [...]

Please always send EXPLAIN ANALYSE output. Only excuse is if a query is
already running for a whole day. Then you may abort it and do a plain
EXPLAIN instead :-)

Under certain circumstances EXPLAIN ANALYSE SELECT count(*) might not
run the same plan as the original query, because it adulterates the
estimated row widths which influence the decision what can be kept in
memory.

I'm willing to investigate a bit more if you send me something to play
with. I'm especially interested in statistics data (output might be
more readable with \x):

SELECT * FROM pg_stats WHERE tablename='...';
SELECT relname, relpages, reltuples FROM pg_class WHERE relname='...';

... and some query plans: EXPLAIN ANALYSE ...

SELECT * FROM messages WHERE date BETWEEN ...

SELECT * FROM message_recipients WHERE recipient='...' -- edi's address

Send it off-list if you feel it is too long for the mailing list. We
can always post a summary later if we find something interesting.

Servus
Manfred