X-Original-To: pgsql-performance-postgresql.org@localhost.postgresql.org Received: from localhost (unknown [64.117.224.130]) by svr1.postgresql.org (Postfix) with ESMTP id 542ABD1B8CB for ; Sat, 30 Aug 2003 14:47:55 +0000 (GMT) Received: from svr1.postgresql.org ([64.117.224.193]) by localhost (neptune.hub.org [64.117.224.130]) (amavisd-new, port 10024) with ESMTP id 37218-08 for ; Sat, 30 Aug 2003 11:47:46 -0300 (ADT) Received: from sss.pgh.pa.us (unknown [192.204.191.242]) by svr1.postgresql.org (Postfix) with ESMTP id 714F2D1B8B2 for ; Sat, 30 Aug 2003 11:47:44 -0300 (ADT) Received: from sss2.sss.pgh.pa.us (tgl@localhost [127.0.0.1]) by sss.pgh.pa.us (8.12.9/8.12.9) with ESMTP id h7UElgjX023401; Sat, 30 Aug 2003 10:47:42 -0400 (EDT) To: rj@last.fm Cc: PgSQL Performance ML Subject: Re: Selecting random rows efficiently In-reply-to: <200308301425.51127.rj@last.fm> References: <200308301425.51127.rj@last.fm> Comments: In-reply-to Richard Jones message dated "Sat, 30 Aug 2003 14:25:51 -0000" Date: Sat, 30 Aug 2003 10:47:42 -0400 Message-ID: <23400.1062254862@sss.pgh.pa.us> From: Tom Lane X-Virus-Scanned: by amavisd-new at postgresql.org X-Archive-Number: 200308/532 X-Sequence-Number: 3348 Richard Jones 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