performance - 如何使用关系查询/类似 Tinder 的后端系统来扩展地理空间

Question

我有一个应用程序，我可以根据他们的位置、上次事件和许多其他过滤器搜索用户，现在已经达到了性能不够好但由于用户数量增加而必须改进的地步。但是，我不确定最好的前进方式是什么，如果有任何意见，我将不胜感激!

我的基本设置是两个表，我们称它们为用户和关系。每个用户都有许多属性，例如位置、last_activity 和各种属性。每个用户都可以与另一个用户( friend /敌人)建立关系。

我想做的查询(这是一项繁重的工作)是搜索附近的用户，这些用户满足用户尚未与之建立关系的许多属性。然后用户将遍历列表并向列表中的每个用户添加关系。完成后查询另一个列表并重复。

目前它在 PostgreSQL 中使用 PostGIS 实现地理索引，但它不可扩展。

伪psql:

CREATE TABLE users
(
  id serial NOT NULL,
  location geometry,
  last_active timestamp NOT NULL,
  property1 int NOT NULL
)

CREATE TABLE relations
(
  user_id int NOT NULL,
  other_user_id int NOT NULL,
  relation_type char(1) NOT NULL
)

和查询

nearby := SELECT * FROM users 
    WHERE property1 > 1
    ORDER BY location <-> 'my location'::geometry
    LIMIT 1000

SELECT * FROM nearby u
    WHERE NOT EXISTS (SELECT * FROM relations where user_id = u.id)
    AND radius > ST_Distance(location::geography, 'my location'::geography)
    ORDER BY ST_Distance(location::geography, 'my location'::geography) * (current_timespan - last_active)

查询被分成两部分，以确保第一部分在位置上使用地理索引。只要限制在一个合理的小数字(例如 1000)，它就可以正常工作。当第一部分返回的所有用户在第二部分中被过滤掉时，问题就来了。

关于如何重新设计这个系统以使其支持具有数亿关系的数百万用户有什么建议吗？

整个系统与 Tinder 必须做的非常相似，找到您尚未与之互动的用户，并根据事件时间、地点和年龄和性别等许多属性的过滤器列表进行排序。

Answer 1

您可以尝试添加加权的 voronoi 图。在 awvd 中，权重从欧氏距离中减去。也许您可以使用每个半径作为“权重”，然后创建 vd。更大的半径使单元格更小，但它也倾向于使一个更大的单元格与附近的点。例如，您可以寻找点画。它还使用加权 voronoi 图!然后您可以尝试多边形中的点测试，但这个问题很难解决。您可以在这里阅读有关 voronoi 图的信息:https://alastaira.wordpress.com/2011/04/25/nearest-neighbours-voronoi-diagrams-and-finding-your-nearest-sql-server-usergroup/ .