ORDER BY random() LIMIT 1 slowness

"Gavin M. Roy" <gmr@justsportsusa.com> writes:

SELECT * FROM poetry ORDER BY random() LIMIT 1;
[ is slow for 35000 rows ]

Yeah. Basically this query is implemented as
(a) select all 35000 rows of "poetry";
(b) compute a random() value for each row;
(c) sort by the random() values;
(d) take the first row, discard the rest.

The good news: this gives you a pretty-durn-random selection. The bad
news: you didn't really care about choosing a random ordering of the
other 34999 rows, but it computed one anyway.

This problem's been discussed before, but I've not seen any really
ideal answer. SQL is not designed to offer unpredictable results ;-)

If you have a reasonably-uniformly-distributed index key on the rows,
you can try something like

select * from poetry where key > (scale * random() + min)
order by key limit 1;

(where scale and min are chosen to make the result cover the range of
index keys). Given an index on "key" this should pick a result quickly
via an indexscan+limit plan. However, if the distribution of keys isn't
real uniform then you won't get real random results --- keys just above
larger gaps will be selected with unfairly high probability. You also
have to know the min and max keys accurately.

I recall some folks have suggested generating an actual random column
(ie, something initialized with "default random()" and suitably indexed)
but this seems like a lot of overhead ... you'd have to be mighty
concerned with the exactness of your random selection to put up with
that, I think.

There are some other suggestions in the archives, IIRC.

regards, tom lane

Gavin,

Assuming that you have a serial column rand on poetry and you did not
delete any row,
here is my suggestion:

CREATE TABLE poetry ( rand SERIAL, ... );

SELECT * FROM poetry WHERE rand = (
SELECT int8( curval( 'poetry_rand_seq') * random()));

JLL

Tom Lane wrote:

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

"Gavin M. Roy" <gmr@justsportsusa.com> writes:

SELECT * FROM poetry ORDER BY random() LIMIT 1;
[ is slow for 35000 rows ]

Yeah. Basically this query is implemented as
(a) select all 35000 rows of "poetry";
(b) compute a random() value for each row;
(c) sort by the random() values;
(d) take the first row, discard the rest.

If you can generate a random value from your application layer you could do

select * from poetry LIMIT 1 OFFSET <random value>

Can offset values be placeholders in prepared queries? If not then this has
that disadvantage.

--
greg

----- Original Message -----
From: "Jean-Luc Lachance" <jllachan@nsd.ca>
Sent: Tuesday, December 17, 2002 5:04 PM

Gavin,

Assuming that you have a serial column rand on poetry and you did not
delete any row,
here is my suggestion:

CREATE TABLE poetry ( rand SERIAL, ... );

SELECT * FROM poetry WHERE rand = (
SELECT int8( curval( 'poetry_rand_seq') * random()));

Mmmm... It usually doesn't work for me. Isn't currval (NOTE: with two r's)
bound to session and has no meaning before the first call to nextval()?
7.2.1 says the following; has it changed in 7.3(.*)?

---------------------------- cut here ------------------------------
tir=> create sequence test_seq;
CREATE
tir=> select currval('test_seq');
ERROR: test_seq.currval is not yet defined in this session
tir=> select nextval('test_seq');
nextval
---------
1
(1 row)

tir=> select currval('test_seq');
currval
---------
1
(1 row)
---------------------------- cut here ------------------------------

G.
--
while (!asleep()) sheep++;

---------------------------- cut here ------------------------------

=?iso-8859-1?Q?SZUCS_G=E1bor?= <surrano@mailbox.hu> writes:

CREATE TABLE poetry ( rand SERIAL, ... );

SELECT * FROM poetry WHERE rand = (
SELECT int8( curval( 'poetry_rand_seq') * random()));

Mmmm... It usually doesn't work for me.

Yeah ... better would be

SELECT * FROM poetry WHERE rand = (
SELECT int8( (select last_value from poetry_rand_seq) * random()));

Personally though, I'd skip the sequence entirely and do

create table poetry (...,
rand float8 default random());
create index on poetry.rand

select * from poetry where rand > random() order by rand limit 1;

A difficulty with either of these approaches is that the system won't
optimize comparisons involving random() into indexscans. To get around
that, you'd have to hide the random() call inside a user-defined
function that is (bogusly) marked cachable (or in 7.3, "stable" would be
the best choice). At the moment I think it'd also work to stick the
random() call inside a subselect, but the UDF approach is less likely to
get broken by future changes.

regards, tom lane

Gabor,

You are right about the missing 'r', but I think you missed my point.
You should modify your table so that it has a serial field and reload
it.

JLL

P.S. I run 7.2 so ALTER TABLE ADD rand SERIAL; does not work, but it may
work under 7.3

SZUCS Gábor wrote:

Dear Jean-Luc,

I don't think my simplified example missed any of your solution's features.
The essence, in my eyes, is that it has nothing to do with tables. It's only
related to sequences.

In short, you _cannot_ use currval() in any single _session_ until you use
nextval() in the same session, even if you created the sequence in the very
same session. Using a serial field in a table or using the sequence directly
is indifferent.

Or I'm missing something here.

As for Tom's solution:

----- Original Message -----
From: "Tom Lane" <tgl@sss.pgh.pa.us>
Sent: Wednesday, December 18, 2002 4:56 PM

Personally though, I'd skip the sequence entirely and do

create table poetry (...,
rand float8 default random());
create index on poetry.rand

select * from poetry where rand > random() order by rand limit 1;

I'm not sure it's as flat as a random number should be. I have some relation
to mathematics but can't see it clearly right now. I fear it's more likely a
normal distribution, not linear (or whatsits called). But if I needed
something like this, I'd be happy with this solution anyway.

G.
--
while (!asleep()) sheep++;

---------------------------- cut here ------------------------------
----- Original Message -----
From: "Jean-Luc Lachance" <jllachan@nsd.ca>
Sent: Wednesday, December 18, 2002 5:55 PM

Gabor,

You are right about the missing 'r', but I think you missed my point.
You should modify your table so that it has a serial field and reload
it.

JLL

P.S. I run 7.2 so ALTER TABLE ADD rand SERIAL; does not work, but it may
work under 7.3

OK Gabor,

I'm the one who misunderstood.

To me, it seem to be a bug (or at least a mis-feature) that one cannot
call currval() before calling nextval().

Does anyone know why it should be like this?

JLL

SZUCS Gábor wrote:

On Wed, Dec 18, 2002 at 02:09:42PM -0500, Jean-Luc Lachance wrote:

OK Gabor,

I'm the one who misunderstood.

To me, it seem to be a bug (or at least a mis-feature) that one cannot
call currval() before calling nextval().

Does anyone know why it should be like this?

It doesn't make sense to call currval() if you haven't called nextval()
before. The meaning of currval() is "the value that was last assigned
to you". If you haven't called nextval(), there isn't a value assigned
to you.

If you want to know what was the last value the sequence gave to anyway,
SELECT last_value FROM sequence. But be aware that this is
non-transaction safe, non-isolatable, non-anything.

--
Alvaro Herrera (<alvherre[a]dcc.uchile.cl>)
"Entristecido, Wutra
echa a Freyr a rodar
y a nosotros al mar" (cancion de Las Barreras)

Alvara,

But instead of returning an error, currval() should return last_value if
nextval() was not called (with all the caveat of couse). I think it
would be more usefull that way.

JLL

Alvaro Herrera wrote:

On Wed, 18 Dec 2002, Jean-Luc Lachance wrote:

OK Gabor,

I'm the one who misunderstood.

To me, it seem to be a bug (or at least a mis-feature) that one cannot
call currval() before calling nextval().

Does anyone know why it should be like this?

First, read this page:

http://developer.postgresql.org/docs/postgres/functions-sequence.html

which answers a bit of that question.

the real issue with sequences is that in order to be transactionally safe,
they have to live outside of all transactions.

The purpose of the sequence manipulation functions is to interact with
sequence's in ways that ensure that the same sequence number is never used
by two different transactions. Let me illustrate with a pair of
concurrent transactions, A and B:

A: begin;
B: begin;
A: select currval('seq'); <- client stores this value
B: select currval('seq'); <- ditto
A: insert into table (name, id) values ('john',idnum);
B: insert into table (name, id) values ('sue',idnum);
A: commit;
B: commit;

See the problem with the above? It's why you can't use currval to get the
sequence number if you haven't called nextval, setval, or some other
fuction that has changed the sequence, and why using it will cause an
error. Let's fix the above queries:

(seq=20)

A: begin;
B: begin;
A: select nextval('seq'); <- client doesn't store this (but could)
B: select nextval('seq'); <- client stores 22
A: insert into table (name, id) values ('john',currval('seq'));
B: insert into table (name, id) values ('sue',idnum);
A: commit;
B: commit;

All is well.

Note that if A: were to roll back, B would still complete, but we would
have a hole in our sequence for number 21. this is normal. The price we
pay for having sequences be safe in transactions is that they live outside
of transactions, and the functions that provide the interface are what are
transactionally aware.

On Wed, 18 Dec 2002, Jean-Luc Lachance wrote:

Alvara,

But instead of returning an error, currval() should return last_value if
nextval() was not called (with all the caveat of couse). I think it
would be more usefull that way.

no, that would be like walking around with a gun pointed at your foot, to
quote Tom Lane.

See my post on transactions and such. Remember that everything in
Postgresql is designed to make transactions safe. currval working without
a nextval or setval before it is dangerous in the exterme to transactions.

Scott,

I understand it all.

If a programmer understand that currval() return the last_(used)_value
and did not himself call nextval() he should be aware of the caveat.

I did not want to make a big fuss of it. I will just use select
last_value myself since I am already aware of the caveat. :)

JLL

"scott.marlowe" wrote:

But the problem is that we'd immediately be innundated on the
pgsql-general list by people who were using currval() in an unsafe way but
didn't know it until they went into production and watched their
application develop serious issues. I.e. they have a right to expect the
sequence functions to operate in a transaction safe manner. It's not
something that is likely to ever change, which is, imnsho, a good thing.

On Wed, 18 Dec 2002, Jean-Luc Lachance wrote:

Hi,
If you need the last gobal value of the sequence just query the
sequence directly.

select last_value, increment_by from xyz_seq;
last_value | increment_by
------------+--------------
355 | 1
(1 row)
or just

select last_value from xyz_seq;
last_value
------------
355
(1 row)

I think that sequences are great in postgresql after going from oracle
to mysql to postgresql.

Regards,
Simon

scott.marlowe wrote:

Have another suggestion then -- add lastval().

We would have:

nextval() transaction safe
currval() transaction safe (nextval() must be called first)
lastval() transaction unsafe

JLL

"scott.marlowe" wrote: