pagination - 没有连续唯一 id(例如位置)的搜索结果的基于光​​标的分页

Question

我正在尝试为用户可以按位置(lat，lng)搜索和排序的数据实现基于光标的分页。一个简化的例子是一个名为“可搜索”的实体。它将有其唯一的主键“id”字段和位置字段“lat”、“lng”。

在我按距特定点的距离对其进行排序后，“id”将被混淆。似乎没有可用作游标的唯一顺序 ID。我也不能使用“lat”和“lng”，因为搜索和顺序是按半径/距离排序的，这意味着“lat”和“lng”也没有顺序。

这是否意味着基于游标的分页不适合此类查询？或者有什么方法可以为这种情况实现游标？

Answer 1

我认为即使在这种情况下，您也可以实现基于游标的分页。

首先，您说您的结果是按与某个点的距离排序的。我假设它与用户可以指定的某个起点之间的距离(例如要求 map 应用程序“显示我附近的餐厅”)。在这种情况下，游标值不是静态的，无法存储在可搜索记录中。它必须根据用户输入进行计算。通过即时计算游标，您将失去游标分页 [1] 的优势之一 - 大结果集的良好效率。那是因为您不能简单地使用数据库索引来跳过游标值“低于”指定值的记录。

[1] 有关光标分页的优缺点的更多信息，请参阅 Slack 工程师的这篇文章:https://slack.engineering/evolving-api-pagination-at-slack-1c1f644f8e12 .

其次，距离本身可能不足以进行明确排序，因为两个不同的可搜索项距起点的距离可能相同。为了解决这个问题，您可以添加 ID 作为二级排序字段，这将使订单具有确定性(或数学术语 total order)。

距离和 ID 一起形成一个可以用作光标的值。

例如，假设当前页面上的最后一个结果的距离为 123.45 公里(或您使用的任何单位)并且 ID 为 98765。

这转换为以下光标:

{
    distance: 123.45,
    id: 98765
}

当您想“转到下一页”时，您只需在使用此光标进行搜索后请求 10 个(或您的页面大小)可搜索项。

如果您熟悉 SQL，它将转换为如下查询:

SELECT s.*
FROM searchables s
WHERE get_distance(stating_point, s) > 123.45
    OR get_distance(stating_point, s) = 123.45 AND s.id > 98765
LIMIT 10

哪里 get_distance(a, b)函数计算点之间的距离 a和 b .

实际上，如果距离和 ID 都可以限制在某个范围内，您可以使用一个聪明的技巧并将光标编码为单个字符串，该字符串的字典顺序将对应于结果的顺序 - 例如。 “0000000123.4500-0000098765”。

通过这种方式，SQL 查询可以简化为:

SELECT s.*
FROM searchables s
WHERE get_cursor(get_distance(stating_point, s), s.id) > '0000000123.4500-0000098765'
LIMIT 10

哪里 get_cursor(distance, id)函数将距离和 ID 格式化为建议格式的字符串。