2

我正在研究一个建立从机场到机场的航线的项目。例如，如果有人想从 LAX 到 JFK，我想返回从 LAX 到 JFK 的所有可能路径（最多 n 个连接）。我一直在努力使用递归 CTE 将此示例转换为 MS SQL（这是文档中的最后一个示例）：http: //publib.boulder.ibm.com/infocenter/iseries/v5r4/index.jsp ?topic= %2Fsqlp%2Frbafyrecursivequeries.htm

我已经能够复制结果，起初这很棒。然而，对大约 20 条记录执行基于集合的递归比在几十万条记录（现实世界的直飞航班）上执行相同任务要快很多。

所以这是我的问题：谁能帮我找出一种更快的方法来找到从一个机场到另一个机场的飞行路径？我正在使用 MS SQL 和 .NET 从头开始​​构建这个东西，但我愿意使用几乎任何东西来快速返回结果（基于集合的递归、迭代（任何语言）等）。

理想情况下，我希望结果的返回速度与 Google 航班返回数据的速度一样快（https://www.google.com/flights/）。

这是迄今为止我在 MS SQL 中的 rCTE。注意：它只是从纽约创建所有可能的路径。要将范围缩小到从纽约到巴黎的所有航班，我们需要将查询的最后一行更改为 FROM destinations WHEREarrival = 'Paris'。

创建一个测试表，FLIGHTS：

CREATE TABLE FLIGHTS (DEPARTURE nvarchar(20),
                      ARRIVAL nvarchar(20), 
                      CARRIER nvarchar(15),
                      FLIGHT_NUMBER nvarchar(5), 
                      PRICE decimal(18, 0))

将数据插入测试表：

INSERT INTO FLIGHTS VALUES('New York', 'Paris', 'Atlantic', '234', 400)
INSERT INTO FLIGHTS VALUES('Chicago', 'Miami', 'NA Air', '2334', 300)
INSERT INTO FLIGHTS VALUES('New York', 'London', 'Atlantic', '5473', 350)
INSERT INTO FLIGHTS VALUES('London', 'Athens'  , 'Mediterranean', '247', 340)
INSERT INTO FLIGHTS VALUES('Athens', 'Nicosia' , 'Mediterranean', '2356', 280) 
INSERT INTO FLIGHTS VALUES('Paris', 'Madrid' , 'Euro Air',  '3256', 380)
INSERT INTO FLIGHTS VALUES('Paris', 'Cairo' , 'Euro Air', '63', 480)
INSERT INTO FLIGHTS VALUES('Chicago', 'Frankfurt', 'Atlantic', '37', 480)
INSERT INTO FLIGHTS VALUES('Frankfurt', 'Moscow', 'Asia Air', '2337', 580)
INSERT INTO FLIGHTS VALUES('Frankfurt', 'Beijing', 'Asia Air',  '77', 480) 
INSERT INTO FLIGHTS VALUES('Moscow', 'Tokyo', 'Asia Air', '437', 680)
INSERT INTO FLIGHTS VALUES('Frankfurt', 'Vienna', 'Euro Air', '59', 200)
INSERT INTO FLIGHTS VALUES('Paris', 'Rome', 'Euro Air', '534', 340)
INSERT INTO FLIGHTS VALUES('Miami', 'Lima', 'SA Air', '5234', 530)
INSERT INTO FLIGHTS VALUES('New York', 'Los Angeles', 'NA Air', '84', 330)
INSERT INTO FLIGHTS VALUES('Los Angeles', 'Tokyo', 'Pacific Air', '824', 530)
INSERT INTO FLIGHTS VALUES('Tokyo', 'Hong Kong', 'Asia Air', '94', 330)
INSERT INTO FLIGHTS VALUES('Washington', 'Toronto', 'NA Air', '104', 250)

这是 rCTE：

WITH

destinations (origin, departure, arrival, flight_count, itinerary) AS    
    (
        SELECT a.departure, a.departure, a.arrival, 1, CAST(a.departure + ', ' + a.arrival AS VARCHAR(2000))
                FROM [FLIGHTS] a
                WHERE a.departure = 'New York'
         UNION ALL
         SELECT r.origin, b.departure, b.arrival, r.flight_count + 1, CAST(r.itinerary + ', ' + b.arrival AS VARCHAR(2000))
                FROM destinations r, [FLIGHTS] b
                WHERE r.arrival = b.departure
                -- prevent cycles by making sure the new arrive airport is not already listed in the itinerary
                and CAST(r.itinerary AS VARCHAR(2000)) NOT LIKE '%' + b.arrival + '%'
                -- the itinerary is a csv str so we can limit the number of hops here
                and (LEN(CAST(r.itinerary AS VARCHAR(2000))) - LEN(REPLACE(CAST(r.itinerary AS VARCHAR(2000)), ',', ''))) < 3
    )

SELECT origin, departure, arrival, flight_count, itinerary 
    FROM destinations

谢谢你的帮助！

4

1 回答 1

3

以下是一些琐碎的观察：

  1. 如果不使用正确的索引，您将永远无法优化它，即至少需要索引键。
  2. NOT LIKE '%' + b.arrival + '%'不会很快工作（很难索引这种表达式）。需要另一种检查已列出机场的方法，可能将项目存储在临时表中。
  3. 需要一种不同的方式来限制跳数。由于您只需要三个跃点，因此您最好使用 3 个连接而不是递归，这样会快得多。

清单可以继续下去；构建像谷歌航班一样快的东西并不容易。

于 2012-11-29T03:42:22.740 回答