You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@couchdb.apache.org by mi...@free.fr on 2010/06/28 15:29:17 UTC
selecting a random subset of a view
Hello couchers,
how would you do to select a random subset of a view result (a simple view with map only).
Example (I don't write the full view response array for clarity)
When called normally, my view returns :
{
...
rows: [
{id: aa1},
{id: aa2},
{id: aa3},
{id: aa4},
{id: aa5},
{id: aa6},
{id: aa7},
{id: aa8},
{id: aa9}
]
}
And I want only three of those rows, randomly chosen. So I launch the magic "get three random rows" feature, and it gives me :
{
...
rows: [
{id: aa5},
{id: aa3},
{id: aa6}
]
}
The second time I launch the same magic "get three random rows" I got:
{
...
rows: [
{id: aa7},
{id: aa1},
{id: aa5}
]
}
Thanks for your advices
Mickael
Re: selecting a random subset of a view
Posted by David Caylor <dc...@fh.org>.
I think it would be great if views supported random queries, maybe by adding
a query argument, but truly random results are rarely necessary in practice.
For example, in generating a play list what you really need is sufficient
unpredictability that play lists yield gratifying results for repeated
playing over time.
You could get this by using Sabastian's suggestion, and request the
documents one at a time. On the client side, generate a random hash and use
that as your startkey. If you get no result get the first document in the
view so that it is sure to spread your results evenly over the whole list
(loop the list). This works well if you need one document at a time.
If you want to retrieve several documents at a time, I'd consider
periodically regenerating a UUID you are using for sorting. For a play
list, I'd probably do this when I update the document with statistics, so
for example when a song is played I'd update its record with a "last played"
timestamp, number of plays, and anything else of interest that says this
song was played, and update it with a newly generated UUID string in a sort
field, which I'd use as the key in the view. Then I'd generate a random
hash client-side as the start key. If you use this, you could get three at
a time and still maintain sufficient randomness for satisfactorily picking
music in an unpredictable way. Songs would be unlikely to be played in the
same order twice (unless your list is small).
If your situation supports it you could update the sort field every time you
retrieve a document. Whether that's practical or not depends on your
environment, the list size, the document size, and so on. You just have to
weigh how "random" you want the list and the impact on the user's experience
of performance. If the update is non-blocking it won't impact the user's
perceived performance but will increase the random appearance of play lists.
The occasions when it is really important to generate random values are
uncommon, such as in situations where security requires the next in a
sequence to be unguessable. Using couchdb is already a rebalancing of
priorities for those of us who have built careers out of data driven
applications. Sometimes the best answer lies in rethinking our requirements
pragmatically.
David Caylor
On Mon, Jun 28, 2010 at 9:15 AM, <mi...@free.fr> wrote:
> shouldn't list functions be deterministics ?
>
>
> ----- Mail Original -----
> De: "Randall Leeds" <ra...@gmail.com>
> À: user@couchdb.apache.org
> Envoyé: Lundi 28 Juin 2010 17h44:36 GMT +01:00 Amsterdam / Berlin / Berne /
> Rome / Stockholm / Vienne
> Objet: Re: selecting a random subset of a view
>
> Ian's Method One, implemented as a list function, would probably do the
> trick.
>
> On Jun 28, 2010 9:04 AM, "Ian Hobson" <ia...@ianhobson.co.uk> wrote:
>
> On 28/06/2010 14:29, mickael.bailly@free.fr wrote:
> >
> > Hello couchers,
> >
> > how would you do to selec...
> Hi Mickael,
>
> You want a random sample of predetermined size, from a list that you can
> only (best) access randomly. To do this you must know the number of records
> in the database.
>
> Note - I know the stats side MUCH better than the couchdb so this might not
> be implementable.
>
> Here are two methods.
>
> Method 1.
>
> Say, for example, you want 3 from 11.
>
> Take the first index with a probability of 3/11 by computing a random
> number in range 0 to 1, and taking the record if rand < 3/11 (using real
> math, not integer).
>
> If you take that record, adjust the number required down by 1.
> Reduce the number remaining by 1.
>
> Take the next record with a probability or 2/10 or 3/10
>
> Continue in like manner until you either
>
> a) Take the last record with a probability of 1/1 or
> b) Have all you want, and take the remaining records with a probability of
> 0/n
>
> To do this with couchdb I would read all the IDs into the client and filter
> them there, and then read each records separately.
>
> Method 2 -
>
> Allocate a random number to each record (from a large range - we don't want
> duplicates). This could be a sha or MD5 of the actual data.
> Sort by the random number allocated.
> Read the first N records that you need.
>
> I think this sort of index could be set up on the server, so the client
> needs only create the index, and read the first N records and remove the
> index. The work on the server will be much greater that method 1 though.
>
> If you use the MD5 or SHA function, then the order will be repeatable if
> the
> data is not changed.
>
> Regards
>
> Ian
>
Re: selecting a random subset of a view
Posted by mi...@free.fr.
shouldn't list functions be deterministics ?
----- Mail Original -----
De: "Randall Leeds" <ra...@gmail.com>
À: user@couchdb.apache.org
Envoyé: Lundi 28 Juin 2010 17h44:36 GMT +01:00 Amsterdam / Berlin / Berne / Rome / Stockholm / Vienne
Objet: Re: selecting a random subset of a view
Ian's Method One, implemented as a list function, would probably do the
trick.
On Jun 28, 2010 9:04 AM, "Ian Hobson" <ia...@ianhobson.co.uk> wrote:
On 28/06/2010 14:29, mickael.bailly@free.fr wrote:
>
> Hello couchers,
>
> how would you do to selec...
Hi Mickael,
You want a random sample of predetermined size, from a list that you can
only (best) access randomly. To do this you must know the number of records
in the database.
Note - I know the stats side MUCH better than the couchdb so this might not
be implementable.
Here are two methods.
Method 1.
Say, for example, you want 3 from 11.
Take the first index with a probability of 3/11 by computing a random
number in range 0 to 1, and taking the record if rand < 3/11 (using real
math, not integer).
If you take that record, adjust the number required down by 1.
Reduce the number remaining by 1.
Take the next record with a probability or 2/10 or 3/10
Continue in like manner until you either
a) Take the last record with a probability of 1/1 or
b) Have all you want, and take the remaining records with a probability of
0/n
To do this with couchdb I would read all the IDs into the client and filter
them there, and then read each records separately.
Method 2 -
Allocate a random number to each record (from a large range - we don't want
duplicates). This could be a sha or MD5 of the actual data.
Sort by the random number allocated.
Read the first N records that you need.
I think this sort of index could be set up on the server, so the client
needs only create the index, and read the first N records and remove the
index. The work on the server will be much greater that method 1 though.
If you use the MD5 or SHA function, then the order will be repeatable if the
data is not changed.
Regards
Ian
Re: selecting a random subset of a view
Posted by Randall Leeds <ra...@gmail.com>.
Ian's Method One, implemented as a list function, would probably do the
trick.
On Jun 28, 2010 9:04 AM, "Ian Hobson" <ia...@ianhobson.co.uk> wrote:
On 28/06/2010 14:29, mickael.bailly@free.fr wrote:
>
> Hello couchers,
>
> how would you do to selec...
Hi Mickael,
You want a random sample of predetermined size, from a list that you can
only (best) access randomly. To do this you must know the number of records
in the database.
Note - I know the stats side MUCH better than the couchdb so this might not
be implementable.
Here are two methods.
Method 1.
Say, for example, you want 3 from 11.
Take the first index with a probability of 3/11 by computing a random
number in range 0 to 1, and taking the record if rand < 3/11 (using real
math, not integer).
If you take that record, adjust the number required down by 1.
Reduce the number remaining by 1.
Take the next record with a probability or 2/10 or 3/10
Continue in like manner until you either
a) Take the last record with a probability of 1/1 or
b) Have all you want, and take the remaining records with a probability of
0/n
To do this with couchdb I would read all the IDs into the client and filter
them there, and then read each records separately.
Method 2 -
Allocate a random number to each record (from a large range - we don't want
duplicates). This could be a sha or MD5 of the actual data.
Sort by the random number allocated.
Read the first N records that you need.
I think this sort of index could be set up on the server, so the client
needs only create the index, and read the first N records and remove the
index. The work on the server will be much greater that method 1 though.
If you use the MD5 or SHA function, then the order will be repeatable if the
data is not changed.
Regards
Ian
Re: selecting a random subset of a view
Posted by Ian Hobson <ia...@ianhobson.co.uk>.
On 28/06/2010 14:29, mickael.bailly@free.fr wrote:
> Hello couchers,
>
> how would you do to select a random subset of a view result (a simple view with map only).
>
>
Hi Mickael,
You want a random sample of predetermined size, from a list that you can
only (best) access randomly. To do this you must know the number of
records in the database.
Note - I know the stats side MUCH better than the couchdb so this might
not be implementable.
Here are two methods.
Method 1.
Say, for example, you want 3 from 11.
Take the first index with a probability of 3/11 by computing a random
number in range 0 to 1, and taking the record if rand < 3/11 (using real
math, not integer).
If you take that record, adjust the number required down by 1.
Reduce the number remaining by 1.
Take the next record with a probability or 2/10 or 3/10
Continue in like manner until you either
a) Take the last record with a probability of 1/1 or
b) Have all you want, and take the remaining records with a probability
of 0/n
To do this with couchdb I would read all the IDs into the client and
filter them there, and then read each records separately.
Method 2 -
Allocate a random number to each record (from a large range - we don't
want duplicates). This could be a sha or MD5 of the actual data.
Sort by the random number allocated.
Read the first N records that you need.
I think this sort of index could be set up on the server, so the client
needs only create the index, and read the first N records and remove the
index. The work on the server will be much greater that method 1 though.
If you use the MD5 or SHA function, then the order will be repeatable if
the data is not changed.
Regards
Ian
Re: selecting a random subset of a view
Posted by Sebastian Cohnen <se...@googlemail.com>.
skip is going to be a performance penalty, since couch need to seek over all skipped rows, IIRC. but for smaller skip-values this approach should work
On 28.06.2010, at 15:36, Mike Keen wrote:
> In the application requesting the view, generate a random skip parameter, and set the limit parameter to 3. This will allow you to grab a random set of results from Couch. More info on these parameters is here:
>
> http://wiki.apache.org/couchdb/HTTP_view_API#Querying_Options
>
> Just make sure skip is never greater than the number of total results - 3.
>
> Mike
>
> On Jun 28, 2010, at 9:29 AM, <mi...@free.fr> <mi...@free.fr> wrote:
>
>> Hello couchers,
>>
>> how would you do to select a random subset of a view result (a simple view with map only).
>>
>> Example (I don't write the full view response array for clarity)
>>
>> When called normally, my view returns :
>>
>> {
>> ...
>> rows: [
>> {id: aa1},
>> {id: aa2},
>> {id: aa3},
>> {id: aa4},
>> {id: aa5},
>> {id: aa6},
>> {id: aa7},
>> {id: aa8},
>> {id: aa9}
>> ]
>> }
>>
>> And I want only three of those rows, randomly chosen. So I launch the magic "get three random rows" feature, and it gives me :
>>
>> {
>> ...
>> rows: [
>> {id: aa5},
>> {id: aa3},
>> {id: aa6}
>> ]
>> }
>>
>> The second time I launch the same magic "get three random rows" I got:
>> {
>> ...
>> rows: [
>> {id: aa7},
>> {id: aa1},
>> {id: aa5}
>> ]
>> }
>>
>> Thanks for your advices
>>
>> Mickael
>
Re: selecting a random subset of a view
Posted by Mike Keen <mk...@visiture.com>.
In the application requesting the view, generate a random skip parameter, and set the limit parameter to 3. This will allow you to grab a random set of results from Couch. More info on these parameters is here:
http://wiki.apache.org/couchdb/HTTP_view_API#Querying_Options
Just make sure skip is never greater than the number of total results - 3.
Mike
On Jun 28, 2010, at 9:29 AM, <mi...@free.fr> <mi...@free.fr> wrote:
> Hello couchers,
>
> how would you do to select a random subset of a view result (a simple view with map only).
>
> Example (I don't write the full view response array for clarity)
>
> When called normally, my view returns :
>
> {
> ...
> rows: [
> {id: aa1},
> {id: aa2},
> {id: aa3},
> {id: aa4},
> {id: aa5},
> {id: aa6},
> {id: aa7},
> {id: aa8},
> {id: aa9}
> ]
> }
>
> And I want only three of those rows, randomly chosen. So I launch the magic "get three random rows" feature, and it gives me :
>
> {
> ...
> rows: [
> {id: aa5},
> {id: aa3},
> {id: aa6}
> ]
> }
>
> The second time I launch the same magic "get three random rows" I got:
> {
> ...
> rows: [
> {id: aa7},
> {id: aa1},
> {id: aa5}
> ]
> }
>
> Thanks for your advices
>
> Mickael
Re: selecting a random subset of a view
Posted by Gordon Leland Hempton <gh...@gmail.com>.
It sounds like couchdb doesn't have a solid solution to this. If this is
central to your application and performance is an issue, maybe you should
explore having a secondary index structure (similar to couchdb-lucene) which
would support fast random querying.
On Mon, Jun 28, 2010 at 9:37 AM, Jan Prieser <j....@hotornot.de> wrote:
> hi Mickael,
>
> i've had the same problem and used the lists-feature from couch.
>
> my list-function looks like this:
>
> function(head,req) {
> function shuffle(ary) {
> function randOrd(){ return Math.round(Math.random()) - 0.5; }
> ary.sort( randOrd );
> }
> body={};
> eval('body='+req.body);
> out = head;
> out.rows = [];
> if(out.total_rows > out.offset) {
> while (row = getRow()) {
> out.rows.push(row);
> }
> }
> shuffle(out.rows);
> if (body && body.rlimit) {
> out.rows = out.rows.slice(-body.rlimit);
> }
> return toJSON(out) + '\n';
> }
>
> maybe you could use a range with startkey and endkey, if the number of rows
> is to big. I didn't test the performance with bigger datasets.
>
>
> Am 28.06.2010 15:29, schrieb mickael.bailly@free.fr:
>
> Hello couchers,
>>
>> how would you do to select a random subset of a view result (a simple view
>> with map only).
>>
>> Example (I don't write the full view response array for clarity)
>>
>> When called normally, my view returns :
>>
>> {
>> ...
>> rows: [
>> {id: aa1},
>> {id: aa2},
>> {id: aa3},
>> {id: aa4},
>> {id: aa5},
>> {id: aa6},
>> {id: aa7},
>> {id: aa8},
>> {id: aa9}
>> ]
>> }
>>
>> And I want only three of those rows, randomly chosen. So I launch the
>> magic "get three random rows" feature, and it gives me :
>>
>> {
>> ...
>> rows: [
>> {id: aa5},
>> {id: aa3},
>> {id: aa6}
>> ]
>> }
>>
>> The second time I launch the same magic "get three random rows" I got:
>> {
>> ...
>> rows: [
>> {id: aa7},
>> {id: aa1},
>> {id: aa5}
>> ]
>> }
>>
>> Thanks for your advices
>>
>> Mickael
>>
>
--
Gordon L. Hempton
http://componentlab.com
http://hempton.com
Re: selecting a random subset of a view
Posted by Jan Prieser <j....@hotornot.de>.
hi Mickael,
i've had the same problem and used the lists-feature from couch.
my list-function looks like this:
function(head,req) {
function shuffle(ary) {
function randOrd(){ return Math.round(Math.random()) - 0.5; }
ary.sort( randOrd );
}
body={};
eval('body='+req.body);
out = head;
out.rows = [];
if(out.total_rows > out.offset) {
while (row = getRow()) {
out.rows.push(row);
}
}
shuffle(out.rows);
if (body && body.rlimit) {
out.rows = out.rows.slice(-body.rlimit);
}
return toJSON(out) + '\n';
}
maybe you could use a range with startkey and endkey, if the number of
rows is to big. I didn't test the performance with bigger datasets.
Am 28.06.2010 15:29, schrieb mickael.bailly@free.fr:
> Hello couchers,
>
> how would you do to select a random subset of a view result (a simple view with map only).
>
> Example (I don't write the full view response array for clarity)
>
> When called normally, my view returns :
>
> {
> ...
> rows: [
> {id: aa1},
> {id: aa2},
> {id: aa3},
> {id: aa4},
> {id: aa5},
> {id: aa6},
> {id: aa7},
> {id: aa8},
> {id: aa9}
> ]
> }
>
> And I want only three of those rows, randomly chosen. So I launch the magic "get three random rows" feature, and it gives me :
>
> {
> ...
> rows: [
> {id: aa5},
> {id: aa3},
> {id: aa6}
> ]
> }
>
> The second time I launch the same magic "get three random rows" I got:
> {
> ...
> rows: [
> {id: aa7},
> {id: aa1},
> {id: aa5}
> ]
> }
>
> Thanks for your advices
>
> Mickael
Re: selecting a random subset of a view
Posted by Robert Newson <ro...@gmail.com>.
using skip is potentially very slow (it still has to read all the
records you're skipping, so it's useful only for small skip values),
suggest instead generating a random key and taking the next N from
there. Whether you can fairly generate a random key is
application-specific.
B.
On Mon, Jun 28, 2010 at 2:37 PM, Sebastian Cohnen
<se...@googlemail.com> wrote:
> depending on your type of keys, I think you can use client-side generated random ids, startkey and limit to fetch random values from your view.
>
> On 28.06.2010, at 15:29, mickael.bailly@free.fr wrote:
>
>> Hello couchers,
>>
>> how would you do to select a random subset of a view result (a simple view with map only).
>>
>> Example (I don't write the full view response array for clarity)
>>
>> When called normally, my view returns :
>>
>> {
>> ...
>> rows: [
>> {id: aa1},
>> {id: aa2},
>> {id: aa3},
>> {id: aa4},
>> {id: aa5},
>> {id: aa6},
>> {id: aa7},
>> {id: aa8},
>> {id: aa9}
>> ]
>> }
>>
>> And I want only three of those rows, randomly chosen. So I launch the magic "get three random rows" feature, and it gives me :
>>
>> {
>> ...
>> rows: [
>> {id: aa5},
>> {id: aa3},
>> {id: aa6}
>> ]
>> }
>>
>> The second time I launch the same magic "get three random rows" I got:
>> {
>> ...
>> rows: [
>> {id: aa7},
>> {id: aa1},
>> {id: aa5}
>> ]
>> }
>>
>> Thanks for your advices
>>
>> Mickael
>
>
Re: selecting a random subset of a view
Posted by Sebastian Cohnen <se...@googlemail.com>.
depending on your type of keys, I think you can use client-side generated random ids, startkey and limit to fetch random values from your view.
On 28.06.2010, at 15:29, mickael.bailly@free.fr wrote:
> Hello couchers,
>
> how would you do to select a random subset of a view result (a simple view with map only).
>
> Example (I don't write the full view response array for clarity)
>
> When called normally, my view returns :
>
> {
> ...
> rows: [
> {id: aa1},
> {id: aa2},
> {id: aa3},
> {id: aa4},
> {id: aa5},
> {id: aa6},
> {id: aa7},
> {id: aa8},
> {id: aa9}
> ]
> }
>
> And I want only three of those rows, randomly chosen. So I launch the magic "get three random rows" feature, and it gives me :
>
> {
> ...
> rows: [
> {id: aa5},
> {id: aa3},
> {id: aa6}
> ]
> }
>
> The second time I launch the same magic "get three random rows" I got:
> {
> ...
> rows: [
> {id: aa7},
> {id: aa1},
> {id: aa5}
> ]
> }
>
> Thanks for your advices
>
> Mickael
Re: selecting a random subset of a view
Posted by Paul Bonser <mi...@gmail.com>.
A fairly simple solution that will give you pseudo-random-ish selections:
1. GET /music_db/, take note of the update_seq returned.
2. For each random item you want:
2.1. Pick a random number between 0 and update_seq
2.2. GET /music_db/_changes?since={number}&limit=1&include_docs=true
A couple of problems with this include the fact that it's not a view
you're getting results from and it will be weighted a bit in favor of
items that have been updated. Still, performance-wise, it's 4 requests
to get your 3 items, and you won't have to handle a large amount of
data being returned by any one request.
On Mon, Jun 28, 2010 at 8:29 AM, <mi...@free.fr> wrote:
> Hello couchers,
>
> how would you do to select a random subset of a view result (a simple view with map only).
>
> Example (I don't write the full view response array for clarity)
>
> When called normally, my view returns :
>
> {
> ...
> rows: [
> {id: aa1},
> {id: aa2},
> {id: aa3},
> {id: aa4},
> {id: aa5},
> {id: aa6},
> {id: aa7},
> {id: aa8},
> {id: aa9}
> ]
> }
>
> And I want only three of those rows, randomly chosen. So I launch the magic "get three random rows" feature, and it gives me :
>
> {
> ...
> rows: [
> {id: aa5},
> {id: aa3},
> {id: aa6}
> ]
> }
>
> The second time I launch the same magic "get three random rows" I got:
> {
> ...
> rows: [
> {id: aa7},
> {id: aa1},
> {id: aa5}
> ]
> }
>
> Thanks for your advices
>
> Mickael
>
--
Paul Bonser
http://probablyprogramming.com