1

我目前正在编写一个移动应用程序，用户必须从列表中选择一个位置。所有位置都使用 Play 应用程序中的 JPA 存储在 Postgres 数据库中。

我想做的是在应用程序中获取用户位置，然后请求获取最接近该用户的前 20 或 50 个位置。

如果我为此使用自己的数据结构，我会使用 KD-Tree。但是，我对 JPA/Play/PostgreSQL 很陌生，所以我不确定如何手动处理数据持久性。

以我目前的知识，我唯一能想到的就是查看每个位置并确定它的距离，但在如此庞大的数据库中这将是非常慢的。

有没有我可以运行的查询说“给我 X 个按距该纬度和经度的距离排序的第一个结果？

编辑：我正在使用 Heroku，由于该应用程序处于开发的早期阶段，如果您想在您的应用程序中使用 PostGIS，我宁愿不必支付 Heroku 每月 200 美元的费用。

4

2 回答 2

3

这是我在大约 3 年前构建的应用程序中使用的功能的一个大大简化的版本。适应手头的问题。

  • 使用框查找点周边的位置。可以用一个圆圈来做这个以获得更准确的结果，但这只是一个近似值。

  • 忽略了世界不是平坦的事实。我的申请只适用于一个地方，大约 100 公里。搜索范围仅跨越几公里。使世界变平就足以达到目的。（Todo：根据地理位置更好地估算纬度/经度比率可能会有所帮助。）

  • 使用您从 Google 地图获得的地理编码进行操作。

  • 与标准 PostgreSQL 一起工作，无需扩展（不需要 PostGis），在 PostgreSQL 9.1 和 9.2 上测试。

如果没有索引，则必须计算基表中每一行的距离并过滤最接近的行。大桌子非常昂贵。

编辑：
我重新检查过，当前的实现允许在点上使用 GisT 索引（Postgres 9.1 或更高版本）。相应地简化了代码。

主要技巧是使用box的功能性GiST 索引，即使该列只是一个点。这使得使用现有的GiST 实现成为可能。

通过这样一个（非常快的）搜索，我们可以得到一个框内的所有位置。剩下的问题：我们知道行数，但我们不知道它们所在的框的大小。这就像知道部分答案，但不知道问题。

我使用与 dba.SE 上的相关答案中更详细描述的方法类似的反向查找方法。（只是，我在这里没有使用部分索引——实际上也可能有效）。

遍历一系列预定义的搜索步骤，从非常小到“大到足以容纳至少足够的位置”。意味着我们必须运行几个（非常快的）查询才能达到搜索框的大小。

然后使用此框搜索基表并仅计算从索引返回的几行的实际距离。通常会有一些盈余，因为我们发现盒子至少有足够的位置。通过采用最接近的那些，我们有效地绕过了盒子的角落。您可以通过使框变大来强制实现这种效果（radius在函数中乘以 sqrt(2) 以获得完全准确的结果，但我不会全力以赴，因为这是近似的开始）。

使用最新版本的 PostgreSQL 中提供的SP GiST索引，这将更快、更简单。但我不知道这是否可能。我们需要数据类型的实际实现，而我没有时间深入研究它。如果你找到办法，答应回报！

给定这个带有一些示例值（adr..地址）的简化表：

CREATE TABLE adr(adr_id int, adr text, geocode point);
INSERT INTO adr (adr_id, adr, geocode) VALUES
    (1,  'adr1', '(48.20117,16.294)'),
    (2,  'adr2', '(48.19834,16.302)'),
    (3,  'adr3', '(48.19755,16.299)'),
    (4,  'adr4', '(48.19727,16.303)'),
    (5,  'adr5', '(48.19796,16.304)'),
    (6,  'adr6', '(48.19791,16.302)'),
    (7,  'adr7', '(48.19813,16.304)'),
    (8,  'adr8', '(48.19735,16.299)'),
    (9,  'adr9', '(48.19746,16.297)');

索引如下所示：

CREATE INDEX adr_geocode_gist_idx ON adr USING gist (geocode);

-> SQL小提琴

您必须根据需要调整家庭区域、步数和比例因子。只要您在一个点周围几公里的方框中进行搜索，平坦的地球就是一个足够好的近似值。

您需要很好地理解 plpgsql 才能使用它。我觉得我在这里做的已经够多了。

CREATE OR REPLACE FUNCTION f_find_around(_lat double precision, _lon double precision, _limit bigint = 50)
  RETURNS TABLE(adr_id int, adr text, distance int) AS
$func$
DECLARE
   _homearea   CONSTANT box := '(49.05,17.15),(46.35,9.45)'::box;      -- box around legal area
-- 100m = 0.0008892                   250m, 340m, 450m, 700m,1000m,1500m,2000m,3000m,4500m,7000m
   _steps      CONSTANT real[] := '{0.0022,0.003,0.004,0.006,0.009,0.013,0.018,0.027,0.040,0.062}';  -- find optimum _steps by experimenting
   geo2m       CONSTANT integer := 73500;                              -- ratio geocode(lon) to meter (found by trial & error with google maps)
   lat2lon     CONSTANT real := 1.53;                                  -- ratio lon/lat (lat is worth more; found by trial & error with google maps in (Vienna)
   _radius     real;                                                   -- final search radius
   _area       box;                                                    -- box to search in
   _count      bigint := 0;                                            -- count rows
   _point      point := point($1,$2);                                  -- center of search
   _scalepoint point := point($1 * lat2lon, $2);                       -- lat scaled to adjust
BEGIN

 -- Optimize _radius
IF (_point <@ _homearea) THEN
   FOREACH _radius IN ARRAY _steps LOOP
      SELECT INTO _count  count(*) FROM adr a
      WHERE  a.geocode <@ box(point($1 - _radius, $2 - _radius * lat2lon)
                            , point($1 + _radius, $2 + _radius * lat2lon));

      EXIT WHEN _count >= _limit;
   END LOOP;
END IF;

IF _count = 0 THEN                                                     -- nothing found or not in legal area
   EXIT;
ELSE
   IF _radius IS NULL THEN
      _radius := _steps[array_upper(_steps,1)];                        --  max. _radius
   END IF;
   _area := box(point($1 - _radius, $2 - _radius * lat2lon)
              , point($1 + _radius, $2 + _radius * lat2lon));
END IF;

RETURN QUERY
SELECT a.adr_id
      ,a.adr
      ,((point (a.geocode[0] * lat2lon, a.geocode[1]) <-> _scalepoint) * geo2m)::int4 AS distance
FROM   adr a
WHERE  a.geocode <@ _area
ORDER  BY distance, a.adr, a.adr_id
LIMIT  _limit;

END
$func$  LANGUAGE plpgsql;

称呼：

SELECT * FROM f_find_around (48.2, 16.3, 20);

$3如果在定义的最大搜索区域中有足够的位置，则返回位置列表。
按实际距离排序。

进一步改进

构建一个函数，如：

CREATE OR REPLACE FUNCTION f_geo2m(double precision, double precision)
  RETURNS point AS
$BODY$
SELECT point($1 * 111200, $2 * 111400 * cos(radians($1)));
$BODY$
  LANGUAGE sql IMMUTABLE;

COMMENT ON FUNCTION f_geo2m(double precision, double precision)
IS 'Project geocode to approximate metric coordinates.
    SELECT f_geo2m(48.20872, 16.37263)  --';

（字面意思）全局常量111200和从经度长度和纬度长度111400针对我所在地区（奥地利）进行了优化，但基本上只适用于世界各地。

Use it to add a scaled geocode to the base table, ideally a generated column like outlined in this answer:
How do you do date math that ignores the year?
Refer to 3. Black magic version where I walk you through the process.
Then you can simplify the function some more: Scale input values once and remove redundant calculations.

于 2013-03-24T01:53:14.193 回答
2

你真的不想为此滚动你自己的数据结构，但幸运的是你使用的是 PostgreSQL，所以你很幸运。使用PostGIS。它将比您在合理时间内构建的任何东西都要快几个数量级。

于 2013-03-23T15:25:01.713 回答