29. البحث عن أقرب جار

29.1. ما البحث عن أقرب جار؟

من الاستعلامات المكانية التي تُطرح كثيرًا: "ما أقرب <معلم مرشّح> إلى <معلم الاستعلام>؟"

على عكس البحث بالمسافة، لا يتضمن البحث عن "أقرب جار" أي قياس يقيّد مدى بُعد الأشكال الهندسية المرشّحة، إذ تُقبل المعالم مهما كانت المسافة التي تبعدها، ما دامت هي الأقرب.

يحل PostgreSQL مشكلة أقرب جار بتقديم معامل "الترتيب حسب المسافة" (<->) الذي يدفع قاعدة البيانات إلى استخدام فهرس لتسريع إعادة مجموعة نتائج مرتّبة. ومع وجود معامل "الترتيب حسب المسافة"، يمكن لاستعلام أقرب جار أن يعيد "أقرب N من المعالم" بمجرد إضافة ترتيب وتقييد مجموعة النتائج بـ N من المدخلات.

يعمل معامل "الترتيب حسب المسافة" مع النوعين geometry و geography. والفرق الوحيد في طريقة عمله بين النوعين هو قيمة المسافة المُعادة. فبالنسبة للنوع geometry يعيد <-> الإجابة نفسها التي تعيدها ST_Distance، وهي تعتمد على وحدات النظام المرجعي المكاني المستخدم. أما بالنسبة للنوع geography فقيمة المسافة المُعادة هي المسافة على الكرة، بدلًا من المسافة الأدق على الشكل الإهليلجي التي تعيدها ST_Distance(geography,geography).

إليك أقرب 3 شوارع إلى محطة المترو 'Broad St':

-- Get the geometry of Broad St
SELECT ST_AsEWKT(geom, 1)
FROM nyc_subway_stations
WHERE name = 'Broad St';

SRID=26918;POINT(583571.9 4506714.3)

-- Plug the geometry into a nearest-neighbor query
SELECT streets.gid, streets.name,
  ST_Transform(streets.geom, 4326),
  streets.geom <-> 'SRID=26918;POINT(583571.9 4506714.3)'::geometry AS dist
FROM
  nyc_streets streets
ORDER BY
  dist
LIMIT 3;

  gid  |   name    |        dist
-------+-----------+--------------------
 17385 | Wall St   |  0.749987508809928
 17390 | Broad St  | 0.8836306235191059
 17436 | Nassau St | 1.3368280241070414

كيف نتأكد من أن الاستعلام يستعين بالفهرس؟ من الجيد فحص مخرجات EXPLAIN لاستعلام أقرب جار، لأنه من الممكن الحصول على إجابات صحيحة من SQL غير مفهرس، وقد لا يتضح غياب الفهرس حتى يكبر حجم الجداول.

هذه مخرجات EXPLAIN، لاحظ مسح الفهرس (index scan) على الترتيب:

                              QUERY PLAN
---------------------------------------------------------------------------------
Limit  (cost=0.28..79.58 rows=3 width=31)
   ->  Index Scan using nyc_streets_geom_idx on nyc_streets streets
       (cost=0.28..504685.12 rows=19091 width=31)
         Order By:
         (geom <-> '0101000020266900000EEBD4CF27CF2141BC17D69516315141'::geometry)

29.2. الربط بأقرب جار

لمعامل الترتيب المدعوم بالفهرس عيب رئيسي واحد: فهو لا يعمل إلا مع شكل هندسي حرفي واحد على أحد جانبي المعامل. هذا مناسب لإيجاد أقرب الكائنات إلى كائن استعلام واحد، لكنه لا يفيد في الربط المكاني، حيث يكون الهدف إيجاد أقرب جار لكل عنصر في مجموعة كاملة من المرشّحين.

لحسن الحظ، هناك ميزة في لغة SQL تتيح لنا تشغيل استعلام بشكل متكرر داخل حلقة: ربط LATERAL.

سنعثر هنا على أقرب شارع لكل محطة مترو:

SELECT subways.gid AS subway_gid,
       subways.name AS subway,
       streets.name AS street,
       streets.gid AS street_gid,
       streets.geom::geometry(MultiLinestring, 26918) AS street_geom,
       streets.dist
FROM nyc_subway_stations subways
CROSS JOIN LATERAL (
  SELECT streets.name, streets.geom, streets.gid, streets.geom <-> subways.geom AS dist
  FROM nyc_streets AS streets
  ORDER BY dist
  LIMIT 1
) streets;

لاحظ كيف يعمل CROSS JOIN LATERAL بوصفه الجزء الداخلي من حلقة يقودها جدول المترو. إذ يُمرَّر كل سجل في جدول المترو إلى الاستعلام الفرعي الجانبي (lateral)، سجلًا تلو الآخر، فتحصل على أقرب نتيجة لكل سجل من سجلات المترو.

تُظهر خطة التنفيذ (explain) الحلقة على محطات المترو، والترتيب المدعوم بالفهرس داخل الحلقة حيث نريده:

                           QUERY PLAN
-------------------------------------------------------------------------
 Nested Loop  (cost=0.28..13140.71 rows=491 width=37)
   ->  Seq Scan on nyc_subway_stations subways
       (cost=0.00..15.91 rows=491 width=46)
   ->  Limit
       (cost=0.28..1.71 rows=1 width=170)
         ->  Index Scan using nyc_streets_geom_idx on nyc_streets streets
             (cost=0.28..27410.12 rows=19091 width=170)
                Order By: (geom <-> subways.geom)