从表中返回随机且不重复的行 - PostgreSQL

Question

从表中返回随机且不重复的行 - PostgreSQL

sqlpostgresqluniquesession-staterandom

4

我有一个有趣的问题，需要一些指导。我有一个包含几千行的表"image"。我想能够返回随机选定的行，每次限制为50行。

客户端有一个初始的GetImages()方法，最初会返回50张“随机”图片（如果有这么多）。当用户滚动到某个数量时（大约40+），另一个函数将触发-GetMoreImages()。

问题是我不确定如何检索更多图片而没有返回相同的结果的风险。

例如，如果总共有60张图片，我希望GetMoreImages()调用仅返回剩余的10张图片。

我感觉应该提到我的Id表是非连续的，因为我正在使用Instagram的方法（参考：http://instagram-engineering.tumblr.com/post/10853187575/sharding-ids-at-instagram）使每个行ID之间可能存在很大的间隔。

我可以尝试的一种方法是将我已经拥有的所有图片的id传入，但如果用户浏览成千上万张图片，这会变得难以管理。

我想另一种方法可能是为每个用户在应用服务器上存储一个缓存的“随机”值集合，但我并不喜欢这个想法。

如果您知道任何最佳实践，希望您能指导我。谢谢。

- doodlleus

3个回答

2

客户端状态跟踪

如果你对这个问题进行深入思考，你会发现它本质上是一个需要在效率和正确性之间做出取舍的难题。

为什么呢？

因为要提供您想要的不重复属性，并同时为每个用户返回不同的随机图像集，需要在某个地方跟踪每个用户看过/未看过的图像。

对于很多客户端来说，这是很多状态数据。

如果将状态推送到客户端并保持他们发送的已看图像列表并进行追加，那么状态跟踪负载就会转移到客户端，但它会让查询变得笨拙 - 你可能需要在VALUES列表上进行反连接以排除已看图像，因为NOT IN在规模上会变得低效。此外，客户端必须发送额外的数据到服务器，服务器必须处理等等。

Gordon的解决方案是这种情况的一个变体，它通过强制稳定的随机排序来简化客户端状态，因此客户端状态只有“我看过几张图片”，而不是“我看过哪些图片”。缺点是顺序是稳定的 - 如果客户端再次请求，它将从同一组随机集的开头开始，而不是另一个随机集。

如果不将状态推送到客户端，服务器必须知道每个客户端看过哪些图像。有许多方法可以做到这一点，但所有方法都要求跟踪大量客户端状态并有效地清除该状态。选项包括：

当你第一次收到请求时，使用CREATE TABLE AS SELECT ...。然后从该表返回结果。这种方法很容易且对于随后的请求非常有效，但对于第一个请求来说非常慢。不需要保持事务或会话处于打开状态。浪费了大量存储空间并需要你过期副本。不是一个好的方法。
使用带有WITH HOLD游标或带有打开事务的常规游标。可以产生相当快的第一结果，并且存储效率相当高 - 尽管它有时可能会消耗大量临时存储。需要您保持会话打开并与特定客户关联，因此它不适用于大量客户。还需要您过期旧会话。
在Gordon的方法中，发送由客户端生成的随机值作为第一次请求的随机种子。因为他的方法将需要进行全表扫描和排序，我不建议这样做，但至少可以解决每个客户端/新请求重复相同随机值的问题。您将从客户端发送“offset=50&&seed=1231”。
使用客户端会话表。使用通常的方法（cookie、URL会话ID等）在应用程序中跟踪HTTP会话，并将其与DB或其他地方的状态相关联。客户端只需向服务器提供会话ID，服务器就可以在其本地存储中查找客户端的会话数据以确定客户端已看到什么。使用此方法，您可以使用NOT IN列表或左反连接针对VALUES列表针对ID列表进行操作，而无需将ID发送到/从客户端。

所以，有很多选择。我相信我还没有列出所有选项。

个人而言，我会使用客户端的HTTP会话 - 直接或者存储我在客户端第一次请求新的随机图像集时生成的随机请求ID。我会在服务器端会话缓存中存储已看到的图像列表，这是一个包含(sessionid，imageid)对的UNLOGGED表，或者如果使用后一种方法，则为(requestid，imageid)。在生成随机集时，我会针对会话表执行左反连接以排除已看到的图像。

获取随机行

哈哈，你还没有完成。

ORDER BY random()的天真方法会进行全表扫描和排序。对于大型表来说，这将非常痛苦。

如果PostgreSQL提供了一种从表中读取随机行的方法，只需选择一个表页并从中读取一行，那将是很好的。不幸的是，它没有，甚至没有可能重复。

由于您的ID是稀疏的，因此您无法轻松生成要选择的随机ID块。

选择表中的随机行原来是一个很困难的问题。你可以采取简化问题的方法来换取降低随机性，例如：

在数据中以随机OFFSET顺序选择按ID排序的连续行块
CREATE UNLOGGED TABLE AS SELECT ...缓存数据的随机副本。创建一堆这样的表并在第一次客户端请求时从中随机选择一个，或者只创建一个并定期重新创建它。
…可能还有更多

简化问题

那么，首先为什么这么难呢？

不重复结果
随机行
对于每个客户端或请求都唯一

我们能做些什么来简化问题呢？

放宽随机性的要求，例如在随机偏移处选择连续的行。
删除不重复图像的要求或将其放宽到（比如）只有最后两组图像不应重复。
放宽每个客户端或请求的唯一性要求。对所有客户端使用相同的随机化并进行缓存。

另一个有用的技巧可能是在客户端之间共享状态。如果您不想重复发送给某个客户端的图像，但您不关心特定客户端是否永远不会看到图像，则可以有效地为一组客户端跟踪已查看的图像。例如，您可以拥有一组WITH HOLD游标，通过在其HTTP会话中存储映射将其分配给客户端。每组客户端都从特定游标中获取结果。当一个客户端从游标中读取一块结果时，同一池中的其他客户端在此会话中永远不会看到这些结果。因此，此方法仅适用于具有“非常大”的图像集的情况，即客户端在一个浏览会话中不会实际上用完。

类似地，您可以拥有一组缓存的随机数据的UNLOGGED表。当客户端发送第一个请求时，您可以使用其HTTP会话ID将其分配给其中一个表 - 通过哈希桶或存储映射。然后您只需从该表返回后续请求的结果。

哇，变得有点长了。我希望它有一些意义，并提供了一些有用的思路。

- Craig Ringer

0

with r as (
    select distinct
        ceil(
            random() *
            (select max(image_id) from image)
        )::int as image_id
    from generate_series(1, 200)
    limit 100
)
select image_id
from image inner join r using (image_id)
limit 50

由于主键存在间隙，必须将表连接到50个以上的随机生成ID上，以确保至少有50个。需要多少个取决于PK的“不连续性”。在样本表中，每5个缺失2个。

为了拥有不同的随机生成ID，还需要生成超过（在上述示例中）100个进行连接。需要多少个取决于表的大小。对于非常大的表，只需要更少的数量。

即使上述数字夸张了，对性能的影响也可以忽略不计。为了使其不返回已经看到的图像，我会创建一个带有session_id（或user_id，以获得更长的过期时间）和image_id的seem_images表，并在每个GetImages中插入其中。无需额外的函数GetMoreImages。

with r as (
    select distinct
        ceil(
            random() *
            (select max(image_id) from image)
        )::int as image_id
    from generate_series(1, 200)
    limit 100
), t as (
    select image_id, image
    from image inner join r using (image_id)
    where not exists (
        select 1
        from seem_image
        where image_id = image.image_id and session_id = 1
    )
    limit 50
), i as (
    insert into seem_image (image_id, session_id)
    select image_id, 1
    from t
)
select * from t;

上面的查询将只返回非看起来的图像。在样本3百万行image表中，它非常快。对于长时间的图像浏览和会话，需要从100和200以上更改为适当的数字。过期的会话应该根据会话到期时间定期从seem_image表中删除，以避免它变得太大。

样例image（带有间隙的整数作为主键）和seem_image表格

create table image (
    image_id integer primary key,
    image bytea
);
insert into image (image_id, image)
select image_id, image
from
    generate_series(1, 5000000) g (image_id)
    cross join
    (values (decode(rpad('', 1024 * 100, 'F'), 'hex'))) i (image)
where mod (image_id, 5) not in (0, 1)
;
analyze image;

create table seem_image (
    session_id integer,
    image_id integer,
    primary key (image_id, session_id)
);

- Clodoaldo Neto

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Gordon Linoff · Accepted Answer

您可以通过以下查询获得随机图像：

select *
from images
order by random()
limit 50;

我不能保证以下方法一定有效，但是可能会有帮助。你需要一个能生成相同随机数的随机数生成器。为此，可以使用setseed()函数。因此，你可以这样做：

with t as (
      select setseed(1)
     )
select *
from images cross join t
order by random()
limit 50;

接着，您可以按如下方式获取后续的值：

with t as (
      select setseed(1)
     ) 
select *
from images cross join t
order by random()
limit 50;

问题在于是否在后续调用中以完全相同的顺序调用random()。您可以通过以下方式强制执行这个要求：

with t as (
      select setseed(1)
     ),
     i as (
      select i.*, random() as rand
      from images i cross join t
     )
select *
from i
order by i.rand
limit 50;

然而，这仍然假设对同一表的多次调用将按相同顺序进行。您可以使用limit 10 offset 50等方式运行相同的查询。

您可以为每个调用更改种子的值，使用计数器、与当前日期时间相关的函数或随机数生成器。

编辑：

我通常使用伪随机数生成器来解决这个问题。我只是取相对较大的质数，进行一些算术操作并使用该值。

通过更改方程中的值，您可以调整所需的参数。例如，我记得8,191和131,071是质数（因为它们是梅森质数）。因此，我可能会这样处理：

select i.*
from images i
order by mod(i.id * 8191 + 1, 131071)
limit 50 offset xxx;

您可以调整“+1”以创建不同的序列。这并不是真正的“随机”，它依赖于id是整数类型，但它避免了随机数生成器方法的不稳定性。这仍然在执行order by，因此根据您的数据大小，它可能效率低下。