Обсуждение: intermittant performance problem

Hello,

I'm looking for some insight on an intermittent PostgreSQL performance
problem that has been very troublesome.  Using PG 8.3.5 on a server
running CentOS 5 2.6.18-8.el5 (Dual Xeon 2.00 GHz, 4 GB RAM, RAID-10
SCSI 600GB array).

The problem in a nutshell is this: on some days, a nightly sampling
process (which reads data from one very large table and writes to
another) runs about 2 orders of magnitude slower and disk IO goes
through the roof.  The sampling process (which starts at 1am and usually
takes ~30 minutes) takes many hours to complete and eventually ends up
interfering with other processes that need to access the database.
Other processes which need to write to the db get backed up and
eventually data gets dropped (ie: in memory queues waiting for db writes
get filled up).

The problem only happens on maybe one or two random days during the
week.  There is generally no other db activity during this time
(pg_stat_activity shows mostly idle connections).  It seems as if db
cache is not being used properly and heavy disk usage results.  Not sure
how to test this assumption.

Details are as follows:

1) The db contains a "raw_data" table which stores on the order of 10-15
million rows per day.  A total of two weeks of data are stored, total
table size is about 40GB (with indices).
2) Every day, a process runs which samples data from the "raw_data"
table and stores it to the "sampled_data" table for long term storage.
The sampling is done across two strata: time of day (time range) and
name of item (text field).  That is, the day is divided into about 5
chunks to ensure that we sample enough data for each chunk of time, for
each item.
3) The sampling process happens in two passes.  The first pass looks at
the data in order to determine the sample size required for each (time
of day, item name).  This consists of running some aggregate queries
over the entire dataset to be sampled (std dev, count, etc).  Sample
sizes are calculated for all items at once for a given chunk of time.
The second pass actually performs random sampling of the data and stores
the samples in the "sampled_data" table.  It is this second pass of the
sampling process that is running about 2 orders of magnitude slower!
4) After the sampling process finishes, the oldest day's worth of data
is deleted from the "raw_data" table.

The sampling query which runs really slow on some days looks something
like this:

INSERT INTO sampled_data
   (item_name, timestmp, ... )
   SELECT item_name, timestmp, ... )
   FROM raw_data
   WHERE timestmp >= ? and timestmp < ?
   AND item_name=?
   AND some_data_field NOTNULL
   ORDER BY random()
   LIMIT ?;

We have done a great deal of PG tuning, including the autovacuum for the
"raw_data" table.  Autovacuum kicks like clockwork every day on that
table after the sampling process finishes (after one day's worth of data
is deleted from "raw_data" table, a roughly 7% change in size).

Changes made to postgresql.conf include:
max_connections = 250
shared_buffers = 1024MB
work_mem = 32MB
maintenance_work_mem = 256MB
max_fsm_pages = 10000000
max_fsm_relations = 30000
checkpoint_segments = 64
checkpoint_timeout = 10min
checkpoint_warning = 1min

Any pointers on how to troubleshoot this?


Mike

On Mon, Mar 9, 2009 at 1:55 PM, Mike Charnoky <noky@nextbus.com> wrote:
> Hello,
>
> I'm looking for some insight on an intermittent PostgreSQL performance
> problem that has been very troublesome.  Using PG 8.3.5 on a server
> running CentOS 5 2.6.18-8.el5 (Dual Xeon 2.00 GHz, 4 GB RAM, RAID-10
> SCSI 600GB array).
>
> The problem in a nutshell is this: on some days, a nightly sampling
> process (which reads data from one very large table and writes to
> another) runs about 2 orders of magnitude slower and disk IO goes
> through the roof.  The sampling process (which starts at 1am and usually
> takes ~30 minutes) takes many hours to complete and eventually ends up
> interfering with other processes that need to access the database.
> Other processes which need to write to the db get backed up and
> eventually data gets dropped (ie: in memory queues waiting for db writes
> get filled up).
>
> The problem only happens on maybe one or two random days during the
> week.  There is generally no other db activity during this time
> (pg_stat_activity shows mostly idle connections).  It seems as if db
> cache is not being used properly and heavy disk usage results.  Not sure
> how to test this assumption.
>
> Details are as follows:
>
> 1) The db contains a "raw_data" table which stores on the order of 10-15
> million rows per day.  A total of two weeks of data are stored, total
> table size is about 40GB (with indices).
> 2) Every day, a process runs which samples data from the "raw_data"
> table and stores it to the "sampled_data" table for long term storage.
> The sampling is done across two strata: time of day (time range) and
> name of item (text field).  That is, the day is divided into about 5
> chunks to ensure that we sample enough data for each chunk of time, for
> each item.
> 3) The sampling process happens in two passes.  The first pass looks at
> the data in order to determine the sample size required for each (time
> of day, item name).  This consists of running some aggregate queries
> over the entire dataset to be sampled (std dev, count, etc).  Sample
> sizes are calculated for all items at once for a given chunk of time.
> The second pass actually performs random sampling of the data and stores
> the samples in the "sampled_data" table.  It is this second pass of the
> sampling process that is running about 2 orders of magnitude slower!
> 4) After the sampling process finishes, the oldest day's worth of data
> is deleted from the "raw_data" table.
>
> The sampling query which runs really slow on some days looks something
> like this:
>
> INSERT INTO sampled_data
>  (item_name, timestmp, ... )
>  SELECT item_name, timestmp, ... )
>  FROM raw_data
>  WHERE timestmp >= ? and timestmp < ?
>  AND item_name=?
>  AND some_data_field NOTNULL
>  ORDER BY random()
>  LIMIT ?;

Have you got any other method for doing the sampling that order by
random()?  order by random() is the most inefficient way you could
possibly do this.  If you know the range of say, ids:

select max(id), min(id) from rawtable where timestmp >= ? and timestmp < ?

to get it.  Then use a random number generator to generate a list of
ids between those two ids, and select x rows from the database.

select * from rawtable where id in (1000 ids be here);

Will be WAY faster than order by random().

> Changes made to postgresql.conf include:
> max_connections = 250
> shared_buffers = 1024MB
> work_mem = 32MB

If you are married to order by random() then you might wanna crank up
work_mem while running that query.  I'd try something in the 128 to
512M range to start with.

> Any pointers on how to troubleshoot this?

Try methods that don't involve order by random().

Mike Charnoky <noky@nextbus.com> writes:
> The sampling query which runs really slow on some days looks something
> like this:

> INSERT INTO sampled_data
>    (item_name, timestmp, ... )
>    SELECT item_name, timestmp, ... )
>    FROM raw_data
>    WHERE timestmp >= ? and timestmp < ?
>    AND item_name=?
>    AND some_data_field NOTNULL
>    ORDER BY random()
>    LIMIT ?;

Hmph, I'd expect that that would run pretty slowly *all* the time :-(.
There's no good way to optimize "ORDER BY random()".  However, it seems
like the first thing you should do is modify the program so that it
issues an EXPLAIN for that right before actually doing the query, and
then you could see if the plan is different on the slow days.

> We have done a great deal of PG tuning, including the autovacuum for the
> "raw_data" table.  Autovacuum kicks like clockwork every day on that
> table after the sampling process finishes (after one day's worth of data
> is deleted from "raw_data" table, a roughly 7% change in size).

Also, are you sure you have ruled out the possibility that the problem
comes from autovac kicking in *while* the update is running?

            regards, tom lane

Yeah, I wish I didn't have to resort to using ORDER BY RANDOM().  I
really wanted to use something like TABLESAMPLE, but that is not
implemented in PostgreSQL.  Unfortunately, I cannot use use the random
sampling technique you mentioned, since I need to select samples across
various strata of the data (in this case, where "item_name=something"),
not just between timestamp ranges.  Guess I'll just have to try kicking
up the work_mem for that query.

Thanks so much for your input.


Mike

Scott Marlowe wrote:
> On Mon, Mar 9, 2009 at 1:55 PM, Mike Charnoky <noky@nextbus.com> wrote:
>> Hello,
>>
>> I'm looking for some insight on an intermittent PostgreSQL performance
>> problem that has been very troublesome.  Using PG 8.3.5 on a server
>> running CentOS 5 2.6.18-8.el5 (Dual Xeon 2.00 GHz, 4 GB RAM, RAID-10
>> SCSI 600GB array).
>>
>> The problem in a nutshell is this: on some days, a nightly sampling
>> process (which reads data from one very large table and writes to
>> another) runs about 2 orders of magnitude slower and disk IO goes
>> through the roof.  The sampling process (which starts at 1am and usually
>> takes ~30 minutes) takes many hours to complete and eventually ends up
>> interfering with other processes that need to access the database.
>> Other processes which need to write to the db get backed up and
>> eventually data gets dropped (ie: in memory queues waiting for db writes
>> get filled up).
>>
>> The problem only happens on maybe one or two random days during the
>> week.  There is generally no other db activity during this time
>> (pg_stat_activity shows mostly idle connections).  It seems as if db
>> cache is not being used properly and heavy disk usage results.  Not sure
>> how to test this assumption.
>>
>> Details are as follows:
>>
>> 1) The db contains a "raw_data" table which stores on the order of 10-15
>> million rows per day.  A total of two weeks of data are stored, total
>> table size is about 40GB (with indices).
>> 2) Every day, a process runs which samples data from the "raw_data"
>> table and stores it to the "sampled_data" table for long term storage.
>> The sampling is done across two strata: time of day (time range) and
>> name of item (text field).  That is, the day is divided into about 5
>> chunks to ensure that we sample enough data for each chunk of time, for
>> each item.
>> 3) The sampling process happens in two passes.  The first pass looks at
>> the data in order to determine the sample size required for each (time
>> of day, item name).  This consists of running some aggregate queries
>> over the entire dataset to be sampled (std dev, count, etc).  Sample
>> sizes are calculated for all items at once for a given chunk of time.
>> The second pass actually performs random sampling of the data and stores
>> the samples in the "sampled_data" table.  It is this second pass of the
>> sampling process that is running about 2 orders of magnitude slower!
>> 4) After the sampling process finishes, the oldest day's worth of data
>> is deleted from the "raw_data" table.
>>
>> The sampling query which runs really slow on some days looks something
>> like this:
>>
>> INSERT INTO sampled_data
>>  (item_name, timestmp, ... )
>>  SELECT item_name, timestmp, ... )
>>  FROM raw_data
>>  WHERE timestmp >= ? and timestmp < ?
>>  AND item_name=?
>>  AND some_data_field NOTNULL
>>  ORDER BY random()
>>  LIMIT ?;
>
> Have you got any other method for doing the sampling that order by
> random()?  order by random() is the most inefficient way you could
> possibly do this.  If you know the range of say, ids:
>
> select max(id), min(id) from rawtable where timestmp >= ? and timestmp < ?
>
> to get it.  Then use a random number generator to generate a list of
> ids between those two ids, and select x rows from the database.
>
> select * from rawtable where id in (1000 ids be here);
>
> Will be WAY faster than order by random().
>
>> Changes made to postgresql.conf include:
>> max_connections = 250
>> shared_buffers = 1024MB
>> work_mem = 32MB
>
> If you are married to order by random() then you might wanna crank up
> work_mem while running that query.  I'd try something in the 128 to
> 512M range to start with.
>
>> Any pointers on how to troubleshoot this?
>
> Try methods that don't involve order by random().
>

The random sampling query is normally pretty snappy.  It usually takes
on the order of 1 second to sample a few thousand rows of data out of a
few million.  The sampling is consistently quick, too.  However, on some
days, the sampling starts off quick, then when the process starts
sampling from a different subset of data (different range of times for
the same day), the sampling query takes a couple minutes.

Regarding the concurrent vacuuming, this is definitely not happening.  I
always check pg_stat_activity whenever the sampling process starts to
lag behind.  I have never seen a vacuum running during this time.

Interesting idea to issue the EXPLAIN first... I will see if I can
instrument the sampling program to do this.

Thanks for your help Tom.


Mike

Tom Lane wrote:
> Mike Charnoky <noky@nextbus.com> writes:
>> The sampling query which runs really slow on some days looks something
>> like this:
>
>> INSERT INTO sampled_data
>>    (item_name, timestmp, ... )
>>    SELECT item_name, timestmp, ... )
>>    FROM raw_data
>>    WHERE timestmp >= ? and timestmp < ?
>>    AND item_name=?
>>    AND some_data_field NOTNULL
>>    ORDER BY random()
>>    LIMIT ?;
>
> Hmph, I'd expect that that would run pretty slowly *all* the time :-(.
> There's no good way to optimize "ORDER BY random()".  However, it seems
> like the first thing you should do is modify the program so that it
> issues an EXPLAIN for that right before actually doing the query, and
> then you could see if the plan is different on the slow days.
>
>> We have done a great deal of PG tuning, including the autovacuum for the
>> "raw_data" table.  Autovacuum kicks like clockwork every day on that
>> table after the sampling process finishes (after one day's worth of data
>> is deleted from "raw_data" table, a roughly 7% change in size).
>
> Also, are you sure you have ruled out the possibility that the problem
> comes from autovac kicking in *while* the update is running?
>
>             regards, tom lane
>

On Mon, Mar 9, 2009 at 8:21 PM, Mike Charnoky <noky@nextbus.com> wrote:
> The random sampling query is normally pretty snappy.  It usually takes on
> the order of 1 second to sample a few thousand rows of data out of a few
> million.  The sampling is consistently quick, too.  However, on some days,
> the sampling starts off quick, then when the process starts sampling from a
> different subset of data (different range of times for the same day), the
> sampling query takes a couple minutes.

Then definitely look at saving explain plans before execution to
compare fast to slow runs.  This definitely sounds like ocassionally
bad query plans to me so far.

> Regarding the concurrent vacuuming, this is definitely not happening.  I
> always check pg_stat_activity whenever the sampling process starts to lag
> behind.  I have never seen a vacuum running during this time.

And if autovac is getting in the ways, try adjusting the various
autovac options. spefically autovacuum_vacuum_cost_delay set to 10 or
20 (mS).

>
> Interesting idea to issue the EXPLAIN first... I will see if I can
> instrument the sampling program to do this.
>
> Thanks for your help Tom.
>
>
> Mike
>
> Tom Lane wrote:
>>
>> Mike Charnoky <noky@nextbus.com> writes:
>>>
>>> The sampling query which runs really slow on some days looks something
>>> like this:
>>
>>> INSERT INTO sampled_data
>>>   (item_name, timestmp, ... )
>>>   SELECT item_name, timestmp, ... )
>>>   FROM raw_data
>>>   WHERE timestmp >= ? and timestmp < ?
>>>   AND item_name=?
>>>   AND some_data_field NOTNULL
>>>   ORDER BY random()
>>>   LIMIT ?;
>>
>> Hmph, I'd expect that that would run pretty slowly *all* the time :-(.
>> There's no good way to optimize "ORDER BY random()".  However, it seems
>> like the first thing you should do is modify the program so that it
>> issues an EXPLAIN for that right before actually doing the query, and
>> then you could see if the plan is different on the slow days.
>>
>>> We have done a great deal of PG tuning, including the autovacuum for the
>>> "raw_data" table.  Autovacuum kicks like clockwork every day on that
>>> table after the sampling process finishes (after one day's worth of data
>>> is deleted from "raw_data" table, a roughly 7% change in size).
>>
>> Also, are you sure you have ruled out the possibility that the problem
>> comes from autovac kicking in *while* the update is running?
>>
>>                        regards, tom lane
>>
>
> --
> Sent via pgsql-general mailing list (pgsql-general@postgresql.org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-general
>



--
When fascism comes to America, it will be the intolerant selling it as
diversity.

Tom Lane <tgl@sss.pgh.pa.us> writes:

> Mike Charnoky <noky@nextbus.com> writes:
>> The sampling query which runs really slow on some days looks something
>> like this:
>
>> INSERT INTO sampled_data
>>    (item_name, timestmp, ... )
>>    SELECT item_name, timestmp, ... )
>>    FROM raw_data
>>    WHERE timestmp >= ? and timestmp < ?
>>    AND item_name=?
>>    AND some_data_field NOTNULL
>>    ORDER BY random()
>>    LIMIT ?;
>
> Hmph, I'd expect that that would run pretty slowly *all* the time :-(.
> There's no good way to optimize "ORDER BY random()".

This seems kind of unlikely but does the parameter to the LIMIT vary a lot? If
it's small enough to fit all the chosen records in work_mem then you'll avoid
a disk-sort and do a top-k scan. If it overflows work_mem then it'll fail over
to do a full disk sort of all the records picked from raw_data.

It does seem much more likely that whatever index you have it using on
timestmp or item_name or some_data_field is sometimes being used and sometimes
not. Perhaps it's switching from an index on one of those columns to an index
on some other column and that's what's throwing it off.

--
  Gregory Stark
  EnterpriseDB          http://www.enterprisedb.com
  Get trained by Bruce Momjian - ask me about EnterpriseDB's PostgreSQL training!

Gregory Stark wrote:
> Tom Lane <tgl@sss.pgh.pa.us> writes:
>
>> Mike Charnoky <noky@nextbus.com> writes:
>>> The sampling query which runs really slow on some days looks something
>>> like this:
>>> INSERT INTO sampled_data
>>>    (item_name, timestmp, ... )
>>>    SELECT item_name, timestmp, ... )
>>>    FROM raw_data
>>>    WHERE timestmp >= ? and timestmp < ?
>>>    AND item_name=?
>>>    AND some_data_field NOTNULL
>>>    ORDER BY random()
>>>    LIMIT ?;
>> Hmph, I'd expect that that would run pretty slowly *all* the time :-(.
>> There's no good way to optimize "ORDER BY random()".
>
> This seems kind of unlikely but does the parameter to the LIMIT vary a lot? If
> it's small enough to fit all the chosen records in work_mem then you'll avoid
> a disk-sort and do a top-k scan. If it overflows work_mem then it'll fail over
> to do a full disk sort of all the records picked from raw_data.
>
> It does seem much more likely that whatever index you have it using on
> timestmp or item_name or some_data_field is sometimes being used and sometimes
> not. Perhaps it's switching from an index on one of those columns to an index
> on some other column and that's what's throwing it off.

The parameter used for the LIMIT does not vary too much.  It is
typically a couple thousand records that are selected.

Judging by the disk IO monitoring we have in place, it does seem like a
full disk-sort is being done when the query runs slow.  Would you expect
this action to totally hose overall database performance?

I'm instrumenting the EXPLAIN now, I'll see what this turns up over the
course of the week and will check back if I'm still stumped.  Thanks.


Mike

Scott Marlowe wrote:
> On Mon, Mar 9, 2009 at 8:21 PM, Mike Charnoky <noky@nextbus.com> wrote:
>> The random sampling query is normally pretty snappy.  It usually takes on
>> the order of 1 second to sample a few thousand rows of data out of a few
>> million.  The sampling is consistently quick, too.  However, on some days,
>> the sampling starts off quick, then when the process starts sampling from a
>> different subset of data (different range of times for the same day), the
>> sampling query takes a couple minutes.
>
> Then definitely look at saving explain plans before execution to
> compare fast to slow runs.  This definitely sounds like ocassionally
> bad query plans to me so far.
>
>>
>> Tom Lane wrote:
>>> Mike Charnoky <noky@nextbus.com> writes:
>>>> The sampling query which runs really slow on some days looks something
>>>> like this:
>>>> INSERT INTO sampled_data
>>>>   (item_name, timestmp, ... )
>>>>   SELECT item_name, timestmp, ... )
>>>>   FROM raw_data
>>>>   WHERE timestmp >= ? and timestmp < ?
>>>>   AND item_name=?
>>>>   AND some_data_field NOTNULL
>>>>   ORDER BY random()
>>>>   LIMIT ?;
>>> Hmph, I'd expect that that would run pretty slowly *all* the time :-(.
>>> There's no good way to optimize "ORDER BY random()".  However, it seems
>>> like the first thing you should do is modify the program so that it
>>> issues an EXPLAIN for that right before actually doing the query, and
>>> then you could see if the plan is different on the slow days.

The problem came up over the weekend so I took a look at the info from
EXPLAIN.  The query plans were quite different on the days when the
problem happened.  I began to suspect that autoanalyze was not happening
daily like the autovacuums were, and sure enough it was only running
about every other day.  In fact, I saw that autoanalyze happened once
during the sampling process, and the sampling happened much faster
afterward.

We're tuning the autoanalyze parameters so it runs more frequently.  Is
it OK to run ANALYZE manually before I begin the sampling process?  Or
is there a possibility this will collide with an autoanalyze and result
in problems?  I seem to remember this was a problem in the past, though
it may have been before PG8.3...


Mike

Mike Charnoky wrote:
> Scott Marlowe wrote:
>> On Mon, Mar 9, 2009 at 8:21 PM, Mike Charnoky <noky@nextbus.com> wrote:
>>> The random sampling query is normally pretty snappy.  It usually takes on
>>> the order of 1 second to sample a few thousand rows of data out of a few
>>> million.  The sampling is consistently quick, too.  However, on some days,
>>> the sampling starts off quick, then when the process starts sampling from a
>>> different subset of data (different range of times for the same day), the
>>> sampling query takes a couple minutes.
>>
>> Then definitely look at saving explain plans before execution to
>> compare fast to slow runs.  This definitely sounds like ocassionally
>> bad query plans to me so far.
>>>
>>> Tom Lane wrote:
>>>> Mike Charnoky <noky@nextbus.com> writes:
>>>>> The sampling query which runs really slow on some days looks something
>>>>> like this:
>>>>> INSERT INTO sampled_data
>>>>>   (item_name, timestmp, ... )
>>>>>   SELECT item_name, timestmp, ... )
>>>>>   FROM raw_data
>>>>>   WHERE timestmp >= ? and timestmp < ?
>>>>>   AND item_name=?
>>>>>   AND some_data_field NOTNULL
>>>>>   ORDER BY random()
>>>>>   LIMIT ?;
>>>> Hmph, I'd expect that that would run pretty slowly *all* the time :-(.
>>>> There's no good way to optimize "ORDER BY random()".  However, it seems
>>>> like the first thing you should do is modify the program so that it
>>>> issues an EXPLAIN for that right before actually doing the query, and
>>>> then you could see if the plan is different on the slow days.

I'm at the end of my rope here.  Tried the following:

* Manually run ANALYZE on the table before running the sampling query.
This does not help, there are still times when the sampling runs slower
by two orders of magnitude and disk IO is through the roof.
* Bump work_mem for the query to 128MB (up from 32MB).  This did not
help.  Also, no temp files were created in $PG/data/base/pgsql_tmp/, so
work_mem does not seem to be an issue.
* EXPLAINs look nearly identical whether the query runs quickly or slowly

The thing that gets me is, why does this query totally hose the entire
database?  Other clients have a very hard time writing to the db when
this sampling query is running slow, disk IO is maxxed out.  This just
doesn't seem right.  Why would a single pg backend strangle db
performance to such an extent?  Aren't there ways to throttle this back?

Due to the nature of the sampling (need to limit using several
parameters with a WHERE clause), I can't just generate random numbers to
select data that I need.  Looks like I am stuck using ORDER BY RANDOM().
  The only other option at this point seems to be to implement
TABLESAMPLE, probably starting with the academic work that Neil Conway
published (http://neilconway.org/talks/hacking/)


Mike

On Mar 25, 2009, at 5:09 PM, Mike Charnoky wrote:

> Due to the nature of the sampling (need to limit using several
> parameters with a WHERE clause), I can't just generate random
> numbers to select data that I need.  Looks like I am stuck using
> ORDER BY RANDOM().  The only other option at this point seems to be
> to implement TABLESAMPLE, probably starting with the academic work
> that Neil Conway published (http://neilconway.org/talks/hacking/)


I'm not sure I answered to this thread before, but ORDER BY RANDOM is
not the only way to get x random rows out of n rows.
Calculating random numbers isn't particularly cheap, so doing that n
times is going to cost a fair amount of CPU cycles and will require a
sequential scan over the table. If you search the archives you're
bound to stumble on a solution I suggested before that only needs to
call random() x times (instead of n times). It still does a sequential
scan (I think there's currently no way around that unless quasi-random
results are acceptable to you). My solution involves a scrollable
cursor that is used to navigate to x random rows in the (otherwise
unsorted) n rows in the result set.

I tried putting that functionality into a pl/pgsql function, but pl/
pgsql doesn't (yet) support the MOVE FORWARD ALL statement, which you
need to get the upper boundary of the random row number (equals the
number of rows in the result set).
An alternative solution is to wrap your query in SELECT COUNT(*) FROM
(...) AS resultset or something similar, but in that case the query
(which does a seqscan) has to be performed twice! Maybe other PL-
languages fair better there, but from the looks of it not even C-
functions can perform MOVE FORWARD ALL, so I guess they won't.

My last attempt used that approach, but it's obviously not optimal.
I'd much prefer to feed my function a query or a refcursor instead of
a string containing a query. Feeding it a string makes me itch.
Anyway, here's how far I got. It is in a usable state and I'm
interested how it performs on a real data set compared to ordering by
random() or other solutions.



!DSPAM:737,49cb5930129747428277249!



It's at the moment probably more efficient to not use a stored
procedure but query the cursor from your application instead (saves
one of the two seqscans). That has it's own disadvantages of course.
I've used something like that (as a function in our PHP application)
on a medium-sized data set before, and it performed adequately.

Alban Hertroys

--
If you can't see the forest for the trees,
cut the trees and you'll see there is no forest.



!DSPAM:737,49cb5930129747428277249!

On Mar 27, 2009, at 8:38 PM, Mike Charnoky wrote:

> Hi Alban,
>
> I experimented with your sample() solution and was rather baffled by
> the results, as it was actually 2x-3x slower than doing an ORDER BY
> RANDOM() LIMIT n.  I even precalculated the size of the result set,
> so that only one sequential scan was required, but this only helped
> marginally.
>
> I tested on a table with 284 million rows, selecting 10 random
> samples from a subset which contained 25 million rows.  I tried 3
> tests 3 times:
> A: ORDER BY RANDOM() limit 10
> B: SAMPLE(query, 10)
> C: SAMPLE(query, 10, 25million)  (precalculate size)
>
> Here were my results (query times in millisec)
>
> Trial   1        2       3     avg  speedup
> --------------------------------------------
> A.  63705    78561   85252   75839  baseline
> B  196057   200537  220437  205677    -270%
> C. 122356   170480  190829  161221    -210%
>
> Have you done any similar sort of benchmarking?  I'm assuming you're
> getting much better performance...
>
>
> Mike

Hello Mike,

That is not quite the result I expected. I think I have some ideas
what may be causing this to perform so inadequate. Those pretty much
torch this approach though...
I CC-ed the list again so that people can chime in.

I think the base of he problem is that the random records we're trying
to fetch aren't being cached. I can think of a few causes for that.

Firstly, due to using SELECT COUNT(*) to determine the size of the
result set, none of the records therein are actually queried and thus
don't end up in any caches. Some probably do end up in the OS's disk
cache.
My original MOVE FORWARD ALL approach (written in SQL in a PHP
function) probably did cause records to be moved to the caches.
Unfortunately I don't have access to that code anymore (a former
employer), but it's not particularly hard to duplicate.

Secondly, I think your result set is larger than mine was (by a
magnitude of 100 or so if memory serves me correctly), so even if
records were moved to the cache it's quite probable that only a part
of the set remains in cache as it simply won't all fit in there.

And thirdly, as we are fetching random records, random records are
being cached. The chance that we hit them again in a subsequent query
gets smaller with increasing result set size. That explains why
subsequent queries of this kind are not showing any improvement.

So effectively we are requesting random records from disk, using
random seeks through the data files.
If parts of the result set would get cached I think that would result
in a significant speedup of this approach. That probably explains my
own results, which did show a significant improvement (down from
several seconds to something acceptable for a website front page),
provided my theory at point 1 is correct.

Now I don't know how a scrollable cursor fetches rows from a result
set when given a specific row number, but I wouldn't be surprised if
it has to look it up from the start of the result set scrolling
forward. There might be a list of record numbers and pointers to disk,
I don't know the internals of FETCH w.r.p. scrollable cursors, but
that would be up to the highest row number requested at best (if we
fetch rows 10 and 5 in that order, we do know something about row 5 as
we encountered it to get to row 10, but we know nothing about row 11
and up as we haven't encountered those yet). If we would know about
rows beyond that we would also know the number of rows in a given
result set, and I know we don't - that's why we query for it.

This makes looking up random records even worse, as although we do
know their row numbers, we probably can't translate that to a disk
position and need a sequential scan to fetch it.

These are mostly educated guesses of course, I hope someone on the
list can shed some light on these pessimistic looking theories :)

> Alban Hertroys wrote:
>> On Mar 25, 2009, at 5:09 PM, Mike Charnoky wrote:
>>> Due to the nature of the sampling (need to limit using several
>>> parameters with a WHERE clause), I can't just generate random
>>> numbers to select data that I need.  Looks like I am stuck using
>>> ORDER BY RANDOM().  The only other option at this point seems to
>>> be to implement TABLESAMPLE, probably starting with the academic
>>> work that Neil Conway published (http://neilconway.org/talks/hacking/
>>> )
>> I'm not sure I answered to this thread before, but ORDER BY RANDOM
>> is not the only way to get x random rows out of n rows.
>> Calculating random numbers isn't particularly cheap, so doing that
>> n times is going to cost a fair amount of CPU cycles and will
>> require a sequential scan over the table. If you search the
>> archives you're bound to stumble on a solution I suggested before
>> that only needs to call random() x times (instead of n times). It
>> still does a sequential scan (I think there's currently no way
>> around that unless quasi-random results are acceptable to you). My
>> solution involves a scrollable cursor that is used to navigate to x
>> random rows in the (otherwise unsorted) n rows in the result set.
>> I tried putting that functionality into a pl/pgsql function, but pl/
>> pgsql doesn't (yet) support the MOVE FORWARD ALL statement, which
>> you need to get the upper boundary of the random row number (equals
>> the number of rows in the result set).
>> An alternative solution is to wrap your query in SELECT COUNT(*)
>> FROM (...) AS resultset or something similar, but in that case the
>> query (which does a seqscan) has to be performed twice! Maybe other
>> PL-languages fair better there, but from the looks of it not even C-
>> functions can perform MOVE FORWARD ALL, so I guess they won't.
>> My last attempt used that approach, but it's obviously not optimal.
>> I'd much prefer to feed my function a query or a refcursor instead
>> of a string containing a query. Feeding it a string makes me itch.
>> Anyway, here's how far I got. It is in a usable state and I'm
>> interested how it performs on a real data set compared to ordering
>> by random() or other solutions.
>> It's at the moment probably more efficient to not use a stored
>> procedure but query the cursor from your application instead (saves
>> one of the two seqscans). That has it's own disadvantages of
>> course. I've used something like that (as a function in our PHP
>> application) on a medium-sized data set before, and it performed
>> adequately.
>> Alban Hertroys
>> --
>> If you can't see the forest for the trees,
>> cut the trees and you'll see there is no forest.
>>
>
> !DSPAM:3,49cd2b5e129741122515007!
>
>

Alban Hertroys

--
If you can't see the forest for the trees,
cut the trees and you'll see there is no forest.


!DSPAM:737,49ce0228129741639950449!

I think (a part of) Your problem is that order by random() is O(N
logN) complexity, while You are after O(N) .

The solution (in pseudocode)

random_sample(resultset,K):
  result := first K rows from resultset
  resultset.scrollto(K+1)
  p = K+1
  while(resultset.hasMoreRows())
        row = resultset.current()
        resultset.advance()
        if(random() < K/p)
              replace a random element in result with row
        p = p+1
  return result


the invariant being that at each step result contains a random sample
of K elements.

It should be fairly easy to implement in plpgsql.

Greetings
Marcin

On Sun, Mar 29, 2009 at 10:24 AM, marcin mank <marcin.mank@gmail.com> wrote:
> I think (a part of) Your problem is that order by random() is O(N
> logN) complexity, while You are after O(N) .
>
> The solution (in pseudocode)
>

[snip]

OK, I may be guiding You the wrong way

select g,g,g,g from generate_series(1,25000000) as g order by random() limit 10

executes in under thirty seconds, so I don`t think the sort is a problem.

Greetings
Marcin