> I don't have a huge amount of experience with this in pg, but one of
> tricks we do in the ISAM world is a 'reverse date' system, so that you
> can scan forwards on the key to pick up datetimes in descending order.
> This is often a win because the o/s cache may assume read/forwards
> giving you more cache hits.   There are a few different ways to do
> but imagine:

I've been thinking more about this and there is even a more optimal way
of doing this if you are willing to beat on your data a bit.  It
involves the use of sequences.  Lets revisit your id/timestamp query
combination for a message board.  The assumption is you are using
integer keys for all tables.  You probably have something like:

create table messages
    user_id     int4 references users,
    topic_id      int4 references topics,
    message_id    serial,
    message_time  timestamp default now(),

The following suggestion works in two principles: one is that instead of
using timestamps for ordering, integers are quicker, and sequences have
a built in ability for reverse-ordering.

Lets define:
create sequence message_seq increment -1 start 2147483647 minvalue 0
maxvalue 2147483647;

now we define our table:
create table messages
    user_id      int4 references users,
    topic_id     int4 references topics,
    message_id   int4 default nextval('message_seq') primary key,
    message_time timestamp default now(),

create index user_message_idx on messages(user_id, message_id);
-- optional
cluster user_message_idx messages;

Since the sequence is in descending order, we don't have to do any
tricks to logically reverse order the table.

-- return last k posts made by user u in descending order;

select * from messages where user_id = u order by user_id, message_id
limit k;

-- return last k posts on a topic
create index topic_message_idx on messages(topic_id, user_id);
select * from messages where topic_id = t order by topic_id, message_id

a side benefit of clustering is that there is little penalty for
increasing k because of read ahead optimization whereas in normal
scenarios your read time scales with k (forcing small values for k).  If
we tended to pull up messages by topic more frequently than user, we
would cluster on topic_message_idx instead.  (if we couldn't decide, we
might cluster on message_id or not at all).

The crucial point is that we are making this one index run really fast
at the expense of other operations.  The other major point is we can use
a sequence in place of a timestamp for ordering.  Using int4 vs.
timestamp is a minor efficiency win, if you are worried about > 4B rows,
then stick with timestamp.

This all boils down to a central unifying principle: organize your
indices around your expected access patterns to the data.  Sorry if I'm
bleating on and on about this...I just think there is plenty of
optimization room left in there :)


---------------------------(end of broadcast)---------------------------
TIP 9: the planner will ignore your desire to choose an index scan if your
      joining column's datatypes do not match

Reply via email to