按距离排序查询需要读取整个数据集？

Question

要在DynamoDB中执行地理查询，在AWS (https://aws.amazon.com/blogs/mobile/geo-library-for-amazon-dynamodb-part-1-table-structure/)中有库。但是要按距离排序地理查询的结果，必须读取整个数据集，对吗？如果geoquery产生大量的结果，那么如果您按距离进行排序，就无法分页(后端，而不是用户)，是吗？

Answer 1

你是对的。若要按距离对所有数据点进行排序，必须从DynamoDB表中读取所有数据。

在DynamoDB中，只能使用存储在DynamoDB表中并用作表或其索引之一的排序键的预计算值对结果进行排序。如果您需要按距离从固定位置进行排序，那么您可以使用DynamoDB进行排序。

可能的解决办法--(有限制)

• TLDR; --如果您只从任意点对X kms内的项进行排序，那么问题就不那么严重了。

这仍然涉及对内存中的数据点进行排序，但它通过产生不完整的结果(通过限制结果的最大范围)使问题变得更加容易。

要做到这一点，您需要点P的Geo散列(您正在测量所有其他点的距离)。假设它是A234311。然后，您需要选择合适的结果范围。让我们把一些数字放在上面，使之具体化。(我完全是在编造这些数字，因为实际数字与理解概念无关。)

A - represents a 6400km by 6400km area
2 - represents a 3200km by 3200km area within A
3 - represents a 1600km by 1600km area within A2
4 - represents a  800km by  800km area within A23
3 - represents a  400km by  400km area within A234
1 - represents a  200km by  200km area within A2343
1 - represents a  100km by  100km area within A23431

从图形上看，它可能如下所示：

View of A                           View of A23
|----------|-----------|            |----------|-----------|
|          | A21 | A22 |            |          |           |
|    A1    |-----|-----|            |   A231   |    A232   |
|          | A23 | A24 |            |          |           |
|----------|-----------|            |----------|-----------|
|          |           |            |          |A2341|A2342|
|    A3    |     A4    |            |   A233   |-----|-----|
|          |           |            |          |A2343|A2344|
|----------|-----------|            |----------|-----------|  ... and so on.

在这种情况下，我们的点P是在A224132。另外，假设我们想得到400公里内的排序点。A2343是400公里乘400公里，所以我们需要从A2343及其所有8-连通邻居(A2341、A2342、A2344、A2334、A2332、A4112、A4121、A4122)加载结果。然后，一旦我们只加载内存中的那些，然后计算距离，排序，并丢弃任何超过400公里的结果。

(只要用户/客户知道400公里以外的数据可能是不完整的，就可以保存400公里以上的结果。)

DynamoDB Geo库使用的散列方法非常类似于Z阶曲线-you，可能会发现熟悉该方法以及AWS数据库博客中关于DynamoDB中多方面查询的Z顺序索引的第1部分和第2部分很有帮助。

Answer 2

不完全同意。在查询位置时，可以使用固定的查询值(分区键值)和排序键进行查询，这样就可以限制查询数据结果，还可以应用一些筛选。

我一直在绞尽脑汁设计一个DynamoDB Geo Hash近距离定位器服务。对于本例，customer_A希望找到其区域内的所有服务providers_X。所有客户和供应商都有一个“g8”密钥，用于存储其精确的geoHash位置(到8层)。

完成此搜索的公认方法是从主表中生成一个次要索引，该索引的geoHash 'g4‘不太准确，这为主查询键提供了更广阔的区域。我是应用键超载和复合关键结构的单一表设计。本设计的目标是返回单个查询所需的所有数据，辅助索引可以按设计复制数据(存储成本低，但cpu和带宽不高)。

GSI1PK  GSI1SK     providerId    Projected keys and attributes
--------------------------------------------- 
g4_9q5c provider   pr_providerId1   name   rating
g4_9q5c provider   pr_providerId2   name   rating
g4_9q5h provider   pr_providerId3   name   rating

Scenario1: customer_A.g8_9q5cfmtk，所以您可以发出一个查询，其中返回GSI1PK=g4_9q5c和两个提供程序的列表，而不是我想要的三个。

但是使用geoHash.neighbor()将返回8个周围的邻居，比如9q5h (参见下面的参考)。这很好，因为9q5h中有一个提供者，但这意味着我必须运行9个查询，一个在中心，8个在邻居上，或者运行1-N，直到得到我所需的最小结果。

但是询问第二个方向，NW，SW，E?？这将需要另一个级别的提示，向哪个邻居有更多的结果，而不首先知道，除非您运行一个加权结果的预查询。但是，您可能只返回有利的邻居，因为在以前不受欢迎的邻居中可能会有新的提供者。您可以在邻居中应用一些ML和随机查询来检查当前计数。

在采用上述方法之前，我尝试了这个设计。

GSI1PK  GSI1SK       providerId    Projected keys and attributes
--------------------------------------------- 
loc     g8_9q5cfmtk  pr_provider1
loc     g8_9q5cfjgq  pr_provider2
loc     g8_9q5fe954  pr_provider3

Scenario2: customer_A.g8_9q5cfmtk，所以您可以发出一个查询，其中GSI1PK=loc和GSI1SK位于g8_9q5ca和g8_9q5fz之间，并返回三个提供程序的列表，但是大量数据被提取和丢弃。

为了实现上述查询，X和Y之间的排序准则由以下几个部分组成。9q5c.neighbors().sorted() = 9q59、9q5c、9q5d、9q5e、9q5f、9q5g、9qh1、9qh4、9qh5。所以我们可以只使用X=9q59和Y=9qh5，但是在函数之间有超过50个匹配象限(我真的没有计算过50之后)。

对于上述哈希/尺寸表，我建议使用该https://www.movable-type.co.uk/scripts/geohash.html地理哈希长度单元高度1≤5,000 to×5,000 km2≤1,250 to×625 km3≤156 to×156 to 4≤39.1km×19.5km 5≤4.89km×4.89km .