Thread: Feature suggestion : FAST CLUSTER

    Well, CLUSTER is so slow (and it doesn't cluster the toast tables
associated with the table to be clustered).
    However, when people use CLUSTER they use it to speed up their queries.
    For that the table does not need to be perfectly in-order.

    So, here is a new idea for CLUSTER :

    - choose a chunk size (about 50% of your RAM)
    - setup disk sorts for all indexes
    - seq scan the table :
        - take a chunk of chunk_size
        - sort it (in memory)
        - write it into new table file
        - while we have the data on-hand, also send the indexed columns data
into the corresponding disk-sorts

    - finish the index disk sorts and rebuild indexes

    This does not run a complete sort on the table. It would be about as fast
as your seq scan disk throughput. Obviously, the end result is not as good
as a real CLUSTER since the table will be made up of several ordered
chunks and a range lookup. Therefore, a range lookup on the clustered
columns would need at most N seeks, versus 1 for a really clustered table.
But it only scans the table once and writes it once, even counting index
rebuild.

    I would think that, with this approach, if people can CLUSTER a large
table in 5 minutes instead of hours, they will use it, instead of not
using it. Therefore, even if the resulting table is not as optimal as a
fully clustered table, it will still be much better than the non-clustered
case.

On Tue, May 22, 2007 at 09:29:00AM +0200, PFC wrote:
>     This does not run a complete sort on the table. It would be about as
>     fast  as your seq scan disk throughput. Obviously, the end result is not as
> good  as a real CLUSTER since the table will be made up of several ordered
> chunks and a range lookup. Therefore, a range lookup on the clustered
> columns would need at most N seeks, versus 1 for a really clustered table.
> But it only scans the table once and writes it once, even counting index
> rebuild.

Do you have any data that indicates such an arrangement would be
substantially better than less-clustered data?
--
Jim Nasby                                      decibel@decibel.org
EnterpriseDB      http://enterprisedb.com      512.569.9461 (cell)

On Sun, 27 May 2007 17:53:38 +0200, Jim C. Nasby <decibel@decibel.org>
wrote:

> On Tue, May 22, 2007 at 09:29:00AM +0200, PFC wrote:
>>     This does not run a complete sort on the table. It would be about as
>>     fast  as your seq scan disk throughput. Obviously, the end result is
>> not as
>> good  as a real CLUSTER since the table will be made up of several
>> ordered
>> chunks and a range lookup. Therefore, a range lookup on the clustered
>> columns would need at most N seeks, versus 1 for a really clustered
>> table.
>> But it only scans the table once and writes it once, even counting index
>> rebuild.
>
> Do you have any data that indicates such an arrangement would be
> substantially better than less-clustered data?

    While the little benchmark that will answer your question is running,
I'll add a few comments :

    I have been creating a new benchmark for PostgreSQL and MySQL, that I
will call the Forum Benchmark. It mimics the activity of a forum.
    So far, I have got interesting results about Postgres and InnoDB and will
publish an extensive report with lots of nasty stuff in it, in, say, 2
weeks, since I'm doing this in spare time.

    Anyway, forums like clustered tables, specifically clusteriing posts on
(topic_id, post_id), in order to be able to display a page with one disk
seek, instead of one seek per post.
    PostgreSQL humiliates InnoDB on CPU-bound workloads (about 2x faster
since I run it on dual core ; InnoDB uses only one core). However, InnoDB
can automatically cluster tables without maintenance. This means InnoDB
will, even though it sucks and is awfully bloated, run a lot faster than
postgres if things become IO-bound, ie. if the dataset is larger than RAM.
    Postgres needs to cluster the posts table in order to keep going. CLUSTER
is very slow. I tried inserting into a new posts table, ordering by
(post_id, topic_id), then renaming the new table in place of the old. It
is faster, but still slow when handling lots of data.
    I am trying other approaches, some quite hack-ish, and will report my
findings.

    Regards

On 5/27/07, PFC <lists@peufeu.com> wrote:
>         PostgreSQL humiliates InnoDB on CPU-bound workloads (about 2x faster
> since I run it on dual core ; InnoDB uses only one core). However, InnoDB
> can automatically cluster tables without maintenance.

How does it know what to cluster by? Does it gather statistics about
query patterns on which it can decide an optimal clustering, or does
it merely follow a clustering previously set up by the user?

Alexander.

> How does it know what to cluster by? Does it gather statistics about
> query patterns on which it can decide an optimal clustering, or does
> it merely follow a clustering previously set up by the user?

    Nothing fancy, InnoDB ALWAYS clusters on the primary key, whatever it is.
So, if you can hack your stuff into having a primary key that clusters
nicely, good for you. If not, well...
    So, I used (topic_id, post_id) as the PK, even though it isn't the real
PK (this should be post_id)...

On Sun, 27 May 2007 19:34:30 +0200, PFC <lists@peufeu.com> wrote:

> On Sun, 27 May 2007 17:53:38 +0200, Jim C. Nasby <decibel@decibel.org>
> wrote:
>
>> On Tue, May 22, 2007 at 09:29:00AM +0200, PFC wrote:
>>>     This does not run a complete sort on the table. It would be about as
>>>     fast  as your seq scan disk throughput. Obviously, the end result is
>>> not as
>>> good  as a real CLUSTER since the table will be made up of several
>>> ordered
>>> chunks and a range lookup. Therefore, a range lookup on the clustered
>>> columns would need at most N seeks, versus 1 for a really clustered
>>> table.
>>> But it only scans the table once and writes it once, even counting
>>> index
>>> rebuild.
>>
>> Do you have any data that indicates such an arrangement would be
>> substantially better than less-clustered data?
>
>     While the little benchmark that will answer your question is running,
> I'll add a few comments :

    Alright, so far :

    This is a simulated forum workload, so it's mostly post insertions, some
edits, and some topic deletes.
    It will give results applicable to forums, obviously, but also anything
that wotks on the same schema :
    - topics + posts
    - blog articles + coomments
    - e-commerce site where users can enter their reviews
    So, the new trend being to let the users to participate, this kind of
workload will become more and more relevant for websites.

    So, how to cluster the posts table on (topic_id, post_id) to get all the
posts on the same webpake in 1 seek ?

    I am benchmarking the following :
    - CLUSTER obviously
    - Creating a new table and INSERT .. SELECT ORDER BY topic_id, post_id,
then reindexing etc
    - not doing anything (just vacuuming all tables)
    - not even vacuuming the posts table.

    I al also trying the following more exotic approaches :

    * chunked sort :

    Well, sorting 1GB of data when your work_mem is only 512 MB needs several
passes, hence a lot of disk IO. The more data, the more IO.
    So, instead of doing this, I will :
    - grab about 250 MB of posts from the table
    - sort them by (topic_id, post_id)
    - insert them in a new table
    - repeat
    - then reindex, etc and replace old table with new.
    (reindex is very fast, since the table is nicely defragmented now, I get
full disk speed. However I would like being able to create 2 indexes with
ONE table scan !)
    I'm trying 2 different ways to do that, with plpgsql and cursors.
    It is much faster than sorting the whole data set, because the sorts are
only done in memory (hence the "chunks")
    So far, it seems a database clustered this way is about as fast as using
CLUSTER, but the clustering operation is faster.
    More results in about 3 days when the benchmarks finish.

    * other dumb stuff

    I'll try DELETing the last 250MB of records, stuff them in a temp table,
vacuum, and re-insert them in order.

On May 27, 2007, at 12:34 PM, PFC wrote:
> On Sun, 27 May 2007 17:53:38 +0200, Jim C. Nasby
> <decibel@decibel.org> wrote:
>> On Tue, May 22, 2007 at 09:29:00AM +0200, PFC wrote:
>>>     This does not run a complete sort on the table. It would be
>>> about as
>>>     fast  as your seq scan disk throughput. Obviously, the end
>>> result is not as
>>> good  as a real CLUSTER since the table will be made up of
>>> several ordered
>>> chunks and a range lookup. Therefore, a range lookup on the
>>> clustered
>>> columns would need at most N seeks, versus 1 for a really
>>> clustered table.
>>> But it only scans the table once and writes it once, even
>>> counting index
>>> rebuild.
>>
>> Do you have any data that indicates such an arrangement would be
>> substantially better than less-clustered data?
>     While the little benchmark that will answer your question is
> running, I'll add a few comments :
>
>     I have been creating a new benchmark for PostgreSQL and MySQL,
> that I will call the Forum Benchmark. It mimics the activity of a
> forum.
>     So far, I have got interesting results about Postgres and InnoDB
> and will publish an extensive report with lots of nasty stuff in
> it, in, say, 2 weeks, since I'm doing this in spare time.
>
>     Anyway, forums like clustered tables, specifically clusteriing
> posts on (topic_id, post_id), in order to be able to display a page
> with one disk seek, instead of one seek per post.
>     PostgreSQL humiliates InnoDB on CPU-bound workloads (about 2x
> faster since I run it on dual core ; InnoDB uses only one core).
> However, InnoDB can automatically cluster tables without
> maintenance. This means InnoDB will, even though it sucks and is
> awfully bloated, run a lot faster than postgres if things become IO-
> bound, ie. if the dataset is larger than RAM.
>     Postgres needs to cluster the posts table in order to keep going.
> CLUSTER is very slow. I tried inserting into a new posts table,
> ordering by (post_id, topic_id), then renaming the new table in
> place of the old. It is faster, but still slow when handling lots
> of data.
>     I am trying other approaches, some quite hack-ish, and will report
> my findings.

I assume you meant topic_id, post_id. :)

The problem with your proposal is that it does nothing to ensure that
posts for a topic stay together as soon as the table is large enough
that you can't sort it in a single pass. If you've got a long-running
thread, it's still going to get spread out throughout the table.

What you really want is CLUSTER CONCURRENTLY, which I believe is on
the TODO list. BUT... there's another caveat here: for any post where
the row ends up being larger than 2k, the text is going to get
TOASTed anyway, which means it's going to be in a separate table, in
a different ordering. I don't know of a good way to address that; you
can cluster the toast table, but you'll be clustering on an OID,
which isn't going to help you.
--
Jim Nasby                                            jim@nasby.net
EnterpriseDB      http://enterprisedb.com      512.569.9461 (cell)

> I assume you meant topic_id, post_id. :)

    Um, yes ;)

> The problem with your proposal is that it does nothing to ensure that
> posts for a topic stay together as soon as the table is large enough
> that you can't sort it in a single pass. If you've got a long-running
> thread, it's still going to get spread out throughout the table.

    I completely agree with you.
    However, you have to consider the use cases for clustered tables.

    Suppose you want to cluster on (A,B). A can be topic, category, month,
store, whatever ; B can be post_id, product_id, etc.

    Now consider these cases :

1- Fully clustered table and defragmented file, TOAST table also in the
same order as the main table.
CLUSTER does not do the second part, but [INSERT INTO new_table SELECT *
 FROM old_table ORDER BY a,b] also fills the TOAST table in the right order.

2- Totally unclustered

3- InnoDB which is an index-table ie. a BTree with data in the leafs ;
this means clustering is automatic

4- My partial cluster proposal, ie. the table and its TOAST table have
been clustered in chunks, say, of 500 MB.

    * You always want to get ALL records with a specific value of A.

In this case, a fully clustered table will obviously be the best choice :
1 seek, then seq scan, Bitmap Index Scan rules.
You might think that the InnoDB case would perform the same.
However, after some time the table and files on disk will be very
fragmented, and btree pages with the same value of A will be everywhere,
as they have been splitted and joined by insertions and deletions, so your
theoretical sequential scan might well translate into 1 seek per page.
Obviously since all the rows in the page will be of interest to you, this
is still better than 1 seek per row, but well, you get the idea.

    * You want records with a specific value of A, and B inside a range

    Example :
    - topic_id = X AND post_id between start_of_page and end_of_page
    - get the sales record for january grouped by store
    - get the first 10 comments of a blog post
    - etc
    I would bet that this use case happens much more often than the previous
one.

In this case, a fully clustered table will obviously, again, be the best
choice.
Randomly "organized" table will cost 1 seek per row, ie. buy more RAM or
get fired.
InnoDB will not work that bad, the number of seeks will be (number of rows
wanted) / (rows per page)

    However, how would the chunked clustered case work ?

    In the worst case, if the table has been sorted in N "chunks", you'll
need N seeks.
    However, since people generally cluster their stuff on some sort of
temporal related column (posts and comments are sorted by insertion time)
you can safely bet that most of the rows you want will end up in the same
chunk, or in maybe 2-3 chunks, reducing the number of seeks to something
between 1 and the number of chunks.

    The fact is, sometimes people don't use CLUSTER when it would really help
because it takes too long.

    Suppose you have a 3GB table, and your work_mem is 512MB.

    CLUSTER will take forever.
    A hypothetical new implementation of CLUSTER which would do an on-disk
sort would create several sort bins, then combine them.
    A chunked cluster like I'm proposing would be several times faster since
it would roughly operate at the raw disk IO speed (Postgres sorting is so
fast when in RAM...)

    So, having a full and chunked cluster would allow users to run the full
cluster maybe once a month, and the chunked cluster maybe once every few
days.
    And the chunked CLUSTER would find most of the rows already in order, so
its end result would be very close to a full CLUSTER, with a fraction of
the runtime.

    An added bonus is for index rebuild.
    Instead of first, clustering the table, then rebuilding the indexes, this
could be done :

    - initialize sort buffers for the index builds
    - loop :
        - grab 500 MB of data from the table
        - sort it
        - insert it into new table
        - while data is still in RAM, extract the indexed columns and shove them
into each index's sort buffer
        - repeat until all data is processed

    - now, you have all indexed columns ready to be used, without need to
rescan the table ! index rebuild will be much faster.

    I see VACUUM FULL is scheduled for a reimplementation in a future version.
    This could be the way : with the same code path, this could do VACUUM
FULL, CLUSTER, and chunked CLUSTER, just by changing if/how the sort step
is done, giving the user a nice performance / maintenance time tradeoff.
    Getting this in maybe, 8.5 is better than CLUSTER CONCURRENTLY in 8.10 I
would dare say.
    And the original table can still be read from.

    Benchmarks are running. I will back this with figures in a few days.

    Anoher thing to do for CLUSTER would be to cluster only the tail of the
table.

    Have a nice day !


>
> What you really want is CLUSTER CONCURRENTLY, which I believe is on the
> TODO list. BUT... there's another caveat here: for any post where the
> row ends up being larger than 2k, the text is going to get TOASTed
> anyway, which means it's going to be in a separate table, in a different
> ordering. I don't know of a good way to address that; you can cluster
> the toast table, but you'll be clustering on an OID, which isn't going
> to help you.
> --
> Jim Nasby                                            jim@nasby.net
> EnterpriseDB      http://enterprisedb.com      512.569.9461 (cell)
>
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 9: In versions below 8.0, the planner will ignore your desire to
>        choose an index scan if your joining column's datatypes do not
>        match