3

Let's assume I have to very simple tables

CREATE TABLE a(id integer PRIMARY KEY, 
       t timestamp default now(), 
       sensor_readings real[]);
CREATE TABLE b(id integer PRIMARY KEY, 
       t timestamp default now(), 
       sensor_readings real[]);

with some data on them

INSERT INTO a(id) SELECT generate_series(    1,   100);
INSERT INTO b(id) SELECT generate_series(10001, 10100);

In reality, table a might have about 100_000 rows, and table b about 50_000. In practive, also, the id sequence might have gaps (in the order of a few %). Thus, the cartesian product a x b has a cardinality of billions.

I want to take a random sample of 1_000 sorted pairs (a.id, b.id). I can use something like the following query:

SELECT  
    *
FROM
(
    SELECT
        *
    FROM
        (
        SELECT 
            a.id AS a_id, b.id AS b_id
        FROM
            a CROSS JOIN b
        ORDER BY
            random()
        ) AS s0
    LIMIT
        1000 
) AS s1
ORDER BY
    a_id, b_id ;

... but it would become extremely inefficient as soon as the number of rows on a or b grows (because of the growth of the CROSS JOIN).

Is there any way of doing something equivalent to this in an optimal manner? That is, is there a practical way of getting a random sample of rows from the a x b relation without actually having to instantiate it.

NOTE: There's no limitation on the fact that a.id or b.id can be repeated. Although the pair (a.id, b.id) cannot.

If I were trying to program this in an imperative language, I'd most probably would use a loop and be doing something like the following pseudo-code (and then, have it checked by a statistitian, to make sure I really take a sample where all the pairs have the same probability of being chosen):

start with a result set equal to {} (empty set)
while size of result set < 1000
    Pick the id value from a random row from table a -> rand_id_a
    Pick the id value from a random row from table b -> rand_id_b
    If (rand_id_a, rand_id_b) not in result set
        append (rand_id_a, rand_id_b) to result set
    end if
end while
sort result set and return it

Is there a way to achieve an equivalent result without resorting to loops? If not, is there an efficient way to do it using plpgSQL? (or any other language)

  • how many rows do you want in your sample? – Evan Carroll Dec 27 '16 at 0:07
  • Are the tables read-only and serial ID columns without gaps? Postgres 9.6? – Erwin Brandstetter Dec 27 '16 at 1:20
  • @EvanCarroll: I'm looking for 1.000 rows out of the A x B product. [Which in the example given has a cardinality of 10.000; but could be any size >=1.000] – joanolo Dec 27 '16 at 7:40
  • @ErwinBrandstetter: The example given was just some series, but I would like this to be as general as possible, so gaps are possible (and, in general, it could be any field with repeated values and null values). The general question goes more toward the "How to get a sample of an A x B space without first having to generate the whole A x B space?" – joanolo Dec 27 '16 at 7:42
4

The best solution depends on the exact definition of your setup. For the example setup it's trivial:

  • Serial integer columns without gaps.

SELECT DISTINCT
           1 + trunc(random() * 100)::int AS a_id
     , 10001 + trunc(random() * 100)::int AS b_id
FROM   generate_series(1, 1100) g  -- enough excess to make up for possible dupes
LIMIT  1000;  -- only take 1000

The only interesting question: how to fold dupes efficiently. The solution: let Postgres decide. Simply use DISTINCT.
We don't even need to involve the tables at all. Super fast.

Note that random() generates (per documentation):

random value in the range 0.0 <= x < 1.0

Hence 1 + trunc(random() * 100)::int to cover ID numbers between 1 and 100 exactly.

Actual setup?

You need be be more specific about your actual setup. Let's assume there is at least a payload column in each of your tables, not just ID columns.

CREATE TABLE a(a_id integer PRIMARY KEY, a text);
CREATE TABLE b(b_id integer PRIMARY KEY, b text);

INSERT INTO a(a_id, a)
SELECT g, 't' || g FROM generate_series(    1,   100) g;
INSERT INTO b(b_id, b)
SELECT g, 't' || g FROM generate_series(10001, 10100) g;

Query:

SELECT a.a_id, a.a, b.b_id, b.b
FROM  (
    SELECT DISTINCT
               1 + trunc(random() * 100)::int AS a_id  -- cover *whole* key space
         , 10001 + trunc(random() * 100)::int AS b_id  -- maybe add reserve for new rows
    FROM   generate_series(1, 1100) g
    LIMIT  1000
    ) ra
JOIN   a USING (a_id)
JOIN   b USING (b_id);

Truly random, very fast and almost independent of the actual table size.

All you need is indexes on a(a_id) and b(b_id). Or possibly multicolumn indexes to allow index-only scans.


The solution also works for a few gaps from skipped nextval() calls, as long as there are not much more gaps than islands, it's still very cheap to generate enough combinations to cover losses by gaps. (Much cheaper than working with a Cartesian product of big tables or sorting whole big tables with ORDER BY random() anyway.) Just be sure to generate enough combinations.

SELECT a.a_id, a.a, b.b_id, b.b
FROM  (
    SELECT DISTINCT
               1 + trunc(random() * 100)::int AS a_id
         , 10001 + trunc(random() * 100)::int AS b_id
    FROM   generate_series(1, 1100) g  -- enough to cover dupes *and* gaps
    ) ra
JOIN   a USING (a_id)
JOIN   b USING (b_id)
LIMIT  1000;  -- LIMIT moves to outer query to cover gaps

With more than a few gaps, start with a number of combinations that's enough 95 % of the time and add a recursive step to add more rows if you should fall short. There is a recipe for this solution (for a single table) in the related answer. Also more explanation and variations:

  • That will work well if I don't have gaps. But I may have them (I can have some nextval() values skipped, because some data did not pass all the constraints, for instance). In any case, I think it's giving me some pointers in the right direction. I guess my next question will be: if I have a collection of ids with gaps, How do I get one (optimally and concurrently) without them? – joanolo Dec 27 '16 at 8:10
  • @joanolo: The solution works very well for a few gaps from missed nextval() calls. I added a variation. Like I commented: You need to define your exact situation in the question. Read-only? Postgres version? How many gaps? Cardinalities? Table definition? Exact requirements? Define "random". Any other restrictions? The best solution depends on your complete situation. – Erwin Brandstetter Dec 27 '16 at 15:41
  • The solution works very well for a few gaps from missed nextval() calls. I added a variation. Like I commented: You need to define your exact situation in the question. Read-only? YES Postgres version? 9.6 How many gaps? 1% Cardinalities? about 100.000 rows a, about 50.000 rows b. (so a x b is really big). Table definition? Both a and b carry an arbitrary asceding id used as PK, a timestamp, and a collection of readings from several measuring devices. "random": equal probability of chosing any (a.id,b.id) pairs. [This is a must, or Montecarlo doesn't work.] Your approach looks good – joanolo Dec 27 '16 at 19:38
  • @joanolo: Good information, but all of that should go into the question. Nobody reads the nth comment under an answer to understand the question. Either way, for only 1 % gaps in big read-only tables above solution should perform excellently. – Erwin Brandstetter Dec 27 '16 at 20:12
0

I want to take a random sample of 1000 sorted pairs (a.id, b.id).

It always depends on what random means, but if you're defining the amount of rows you want then you likely want the extension tsm_system_rows

tsm_system_rows

module provides the table sampling method SYSTEM_ROWS, which can be used in the TABLESAMPLE clause of a SELECT command.

This table sampling method accepts a single integer argument that is the maximum number of rows to read. The resulting sample will always contain exactly that many rows, unless the table does not contain enough rows, in which case the whole table is selected. Like the built-in SYSTEM sampling method, SYSTEM_ROWS performs block-level sampling, so that the sample is not completely random but may be subject to clustering effects, especially if only a small number of rows are requested.

First install the extension

CREATE EXTENSION tsm_system_rows;

Then your query,

SELECT *
FROM a
CROSS JOIN b
TABLESAMPLE SYSTEM_ROWS(1000);

The important thing here is that it always provides 1000 ROWS, which is more than we can say for random() <= 0.10, or for TABLESAMPLE BERNOULLI.

If that's not good nuff'

If you truly need random and can't accept the clustering drawback, then I would use

ORDER BY random()
LIMIT x;

If you need to trim out duplicates

The only sane way to trim out duplicates (if a.id, and b.id are not UNIQUE) and keep the result set random, is to do it beforehand. That can get nasty because TABLESAMPLE doesn't yet work in virtual tables, so you'll have to create a temporary table (which may still persist in memory). Shy of that, you can use the other method which is also slow and ugly, but at least it doesn't have to write the

SELECT *
FROM (
  SELECT DISTINCT ON(a.id, b.id) a.id, b.id
  FROM a
  CROSS JOIN b
) AS t
ORDER BY random()
FETCH FIRST 1000 ROWS ONLY;
  • tsm_system_rows is very handy and fast to get n distinct mostly random rows, but it's not exactly right to produce (truly) random combinations of rows from two tables. The added solutions both don't scale for big tables. – Erwin Brandstetter Dec 27 '16 at 1:33
  • Generating the full A x B space is the kind of thing that I am trying to avoid... I want to get a sample to do some statistical calculations without having to deal with the whole population. It's basically a Montecarlo method, to get an approximate value fast. If I have to deal with the whole A x B space, I think it doesn't make sense to get an approximate value, once you do all that work, you can already compute the precise value. – joanolo Dec 27 '16 at 8:14
  • BTW: the exact size of the sample isn't that critical (whether 1000 or 990 is the same); but I do need the sample not be biased; meaning all (a.id, b.id) pairs have the same probability of being selected. – joanolo Dec 27 '16 at 8:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.