pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Tom Lane <tgl@sss.pgh.pa.us>
To: rj@last.fm
Cc: PgSQL Performance ML <pgsql-performance@postgresql.org>
Subject: Re: Selecting random rows efficiently
Date: Sat, 30 Aug 2003 10:47:42 -0400
Message-ID: <23400.1062254862@sss.pgh.pa.us> (raw)
In-Reply-To: <200308301425.51127.rj@last.fm>
References: <Pine.BSF.4.44.0308300905390.829-100000@torgo.978.org>
	<200308301425.51127.rj@last.fm>

Richard Jones <rj@last.fm> writes:
>>> i have a table of around 3 million rows from which i regularly (twice a
>>> second at the moment) need to select a random row from

> i was hoping there was some trickery with sequences that would allow me to 
> easily pick a random valid sequence number..?

There is no magic bullet here, but if you expect that requirement to
persist then it is worth your trouble to expend effort on a real
solution.  A real solution in my mind would look like

1. Add a column "random_id float8 default random()".  The idea here
   is that you assign a random ID to each row as it is created.

2. Add an index on the above column.

3. Your query now looks like

	SELECT * FROM table WHERE random_id >= random()
	ORDER BY random_id LIMIT 1;

This gives you a plan on the order of

 Limit  (cost=0.00..0.17 rows=1 width=8)
   ->  Index Scan using fooi on foo  (cost=0.00..57.00 rows=334 width=8)
         Filter: (random_id >= random())

which is fast and gives a genuinely random result row.  At least up
until you have enough rows that there start being duplicate random_ids,
which AFAIK would be 2 billion rows with a decent random()
implementation.  If you're concerned about that, you could periodically
re-randomize with
	UPDATE table SET random_id = random();
so that any rows that were "hidden" because they had a duplicate
random_id have another shot at being choosable.  But with only a few mil
rows I don't think you need to worry.

			regards, tom lane



view thread (10+ messages)  latest in thread

Message-ID: <23400.1062254862@sss.pgh.pa.us>
Permalink:  ../23400.1062254862@sss.pgh.pa.us/
Also on:    postgresql.org/message-id/23400.1062254862@sss.pgh.pa.us

 · 

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients from your mail client; the link fills in
  the headers below: reply via email
  Some clients, webmail especially, drop In-Reply-To and References from
  a link, and the reply then starts a new thread: use the mbox below.

  To: pgsql-performance@postgresql.org
  Cc: tgl@sss.pgh.pa.us, rj@last.fm
  Subject: Re: Selecting random rows efficiently
  In-Reply-To: <23400.1062254862@sss.pgh.pa.us>
  References: <Pine.BSF.4.44.0308300905390.829-100000@torgo.978.org> <200308301425.51127.rj@last.fm> <23400.1062254862@sss.pgh.pa.us>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox