Как я могу заставить мои запросы GTFS работать быстрее?

Question

Я пытаюсь поиграть с базой данных GTFS, а именно с базой данных RATP для Парижа и его пригородов.

Набор данных огромен. stop_times Таблица имеет 14 миллионов строк.

Вот схемы таблиц: https://github.com/mauryquijada/gtfs-mysql/blob/master/gtfs-sql.sql

Я пытаюсь найти наиболее эффективный способ получить доступные маршруты в определенном месте. Насколько я понимаю спецификацию GTFS, вот таблицы и их ссылки из моих данных (широта / долгота) на маршруты:

stops      | stop_times     | trips      | routes
-----------+----------------+------------+--------------
lat        | stop_id        | trip_id    | route_id
lon        | trip_id        | route_id   |
stop_id    |                |            |

Я скомпилировал то, что я хочу, в три этапа (на самом деле это три ссылки, которые мы имеем между четырьмя таблицами выше), опубликованные под этой сущностью для ясности: https://gist.github.com/BenoitDuffez/4eba85e3598ebe6ece5f

---

Вот как я создал этот скрипт.

Я смог быстро найти все остановки в нескольких минутах ходьбы (скажем, 200 м) менее чем за секунду. Я использую:

$ . mysql.ini && time mysql -h $host -N -B -u $user -p${pass} $name -e "SELECT stop_id, (6371000*acos(cos(radians(48.824699))*cos(radians(s.stop_lat))*cos(radians(2.3243)-radians(s.stop_lon))+sin(radians(48.824699))*sin(radians(s.stop_lat)))) AS distance
FROM stops s
GROUP BY s.stop_id
HAVING distance < 200
ORDER BY distance ASC" | awk '{print $1}'
3705271
4472979
4036891
4036566
3908953
3908755
3900765
3900693
3900607
4473141
3705272
4472978
4036892
4036472
4035057
3908952
3705288
3908814
3900832
3900672
3900752
3781623
3781622

real    0m0.797s
user    0m0.000s
sys     0m0.000s

Затем, получая все stop_times позже сегодня (с stop_times.departure_time > '``date +%T``') отнимает много времени:

"SELECT trip_id
 FROM stop_times
 WHERE
     stop_id IN ($stops) AND departure_time >= '$now'

 GROUP BY trip_id"

С $stops содержащий список остановок, полученных на первом этапе. Вот пример:

$ . mysql.ini && time mysql -h $host -N -B -u $user -p${pass} $name -e "SELECT stop_id, (6371000*acos(cos(radians(
FROM stops s
GROUP BY s.stop_id
HAVING distance < 200
ORDER BY distance ASC" | awk '{print $1}'
3705271
4472979
4036891
4036566
3908953
...
9916360850964321
9916360920964320
9916360920964321

real    1m21.399s
user    0m0.000s
sys     0m0.000s

В этом результате более 2000 строк.

Моим последним шагом было выбрать все маршруты, которые соответствуют этим trip_ids. Это довольно просто и довольно быстро:

$ . mysql.ini && time mysql -h $host -u $user -p${pass} $name -e "SELECT r.id, r.route_long_name FROM trips t, routes r WHERE t.trip_id IN (`cat trip_ids | tr '\n' '#' | sed -e 's/##$//' -e 's/#/,/g'`) AND r.route_id = t.route_id GROUP BY t.route_id"
+------+-------------------------------------------------------------------------+
| id   | route_long_name                                                         |
+------+-------------------------------------------------------------------------+
|  290 | (PLACE DE CLICHY <-> CHATILLON METRO) - Aller                           |
|  291 | (PLACE DE CLICHY <-> CHATILLON METRO) - Retour                          |
|  404 | (PORTE D'ORLEANS-METRO <-> ECOLE VETERINAIRE DE MAISON-ALFORT) - Aller  |
|  405 | (PORTE D'ORLEANS-METRO <-> ECOLE VETERINAIRE DE MAISON-ALFORT) - Retour |
|  453 | (PORTE D'ORLEANS-METRO <-> LYCEE POLYVALENT) - Retour                   |
|  457 | (PORTE D'ORLEANS-METRO <-> LYCEE POLYVALENT) - Retour                   |
|  479 | (PORTE D'ORLEANS-METRO <-> VELIZY 2) - Retour                           |
|  810 | (PLACE DE LA LIBERATION <-> GARE MONTPARNASSE) - Aller                  |
|  989 | (PORTE D'ORLEANS-METRO) - Retour                                        |
| 1034 | (PLACE DE LA LIBERATION <-> HOTEL DE VILLE DE PARIS_4E__AR) - Aller     |
+------+-------------------------------------------------------------------------+

real    0m1.070s
user    0m0.000s
sys     0m0.000s

С здесь файл trip_ids содержащий 2k идентификаторов поездки.

Как я могу получить этот результат быстрее? Есть ли лучший способ пролистать данные, а не stops>stop_times>trips>routes путь я выбрал?

Общее время здесь составляет около 30 секунд для фактически ОДНОГО "запроса": "Какие маршруты доступны в 200 метрах от этого места?". Это слишком много...

Answer 1

Схема таблицы, которую я использовал, была неверна, я должен был создать ее сам или хотя бы проанализировать перед использованием.

Вот обновленная схема:

CREATE TABLE `agency` (
    transit_system VARCHAR(50) NOT NULL,
    agency_id VARCHAR(100),
    agency_name VARCHAR(255) NOT NULL,
    agency_url VARCHAR(255) NOT NULL,
    agency_timezone VARCHAR(100) NOT NULL,
    agency_lang VARCHAR(100),
    agency_phone VARCHAR(100),
    agency_fare_url VARCHAR(100),
    PRIMARY KEY (agency_id)
);

CREATE TABLE `calendar_dates` (
    id INT(12) NOT NULL PRIMARY KEY AUTO_INCREMENT,
    transit_system VARCHAR(50) NOT NULL,
    service_id VARCHAR(255) NOT NULL,
    `date` VARCHAR(8) NOT NULL,
    exception_type TINYINT(2) NOT NULL,
    KEY `service_id` (service_id),
    KEY `exception_type` (exception_type)    
);

CREATE TABLE `calendar` (
    id INT(12) NOT NULL PRIMARY KEY AUTO_INCREMENT,
    transit_system VARCHAR(50) NOT NULL,
    service_id VARCHAR(255) NOT NULL,
    monday TINYINT(1) NOT NULL,
    tuesday TINYINT(1) NOT NULL,
    wednesday TINYINT(1) NOT NULL,
    thursday TINYINT(1) NOT NULL,
    friday TINYINT(1) NOT NULL,
    saturday TINYINT(1) NOT NULL,
    sunday TINYINT(1) NOT NULL,
    start_date VARCHAR(8) NOT NULL, 
    end_date VARCHAR(8) NOT NULL,
    KEY `service_id` (service_id)
);

CREATE TABLE `fare_attributes` (
    id INT(12) NOT NULL PRIMARY KEY AUTO_INCREMENT,
    transit_system VARCHAR(50) NOT NULL,
    fare_id VARCHAR(100),
    price VARCHAR(50) NOT NULL,
    currency_type VARCHAR(50) NOT NULL,
    payment_method TINYINT(1) NOT NULL,
    transfers TINYINT(1) NOT NULL,
    transfer_duration VARCHAR(10),
    exception_type TINYINT(2) NOT NULL,
    agency_id INT(100),
    KEY `fare_id` (fare_id)
);

CREATE TABLE `fare_rules` (
    id INT(12) NOT NULL PRIMARY KEY AUTO_INCREMENT,
    transit_system VARCHAR(50) NOT NULL,
    fare_id VARCHAR(100),
    route_id VARCHAR(100),
    origin_id VARCHAR(100),
    destination_id VARCHAR(100),
    contains_id VARCHAR(100),
    KEY `fare_id` (fare_id),
    KEY `route_id` (route_id)
);

CREATE TABLE `feed_info` (
    id INT(12) NOT NULL PRIMARY KEY AUTO_INCREMENT,
    transit_system VARCHAR(50) NOT NULL,
    feed_publisher_name VARCHAR(100),
    feed_publisher_url VARCHAR(255) NOT NULL,
    feed_lang VARCHAR(255) NOT NULL,
    feed_start_date VARCHAR(8),
    feed_end_date VARCHAR(8),
    feed_version VARCHAR(100)
);

CREATE TABLE `frequencies` (
    id INT(12) NOT NULL PRIMARY KEY AUTO_INCREMENT,
    transit_system VARCHAR(50) NOT NULL,
    trip_id VARCHAR(100) NOT NULL,
    start_time VARCHAR(8) NOT NULL,
    end_time VARCHAR(8) NOT NULL,
    headway_secs VARCHAR(100) NOT NULL,
    exact_times TINYINT(1),
    KEY `trip_id` (trip_id)
);

CREATE TABLE `routes` (
    transit_system VARCHAR(50) NOT NULL,
    route_id VARCHAR(100),
    agency_id VARCHAR(50),
    route_short_name VARCHAR(50) NOT NULL,
    route_long_name VARCHAR(255) NOT NULL,
    route_type VARCHAR(2) NOT NULL, 
    route_text_color VARCHAR(255),
    route_color VARCHAR(255),
    route_url VARCHAR(255),
    route_desc VARCHAR(255),
    PRIMARY KEY (route_id),
    KEY `agency_id` (agency_id),
    KEY `route_type` (route_type),
    CONSTRAINT `agency_id` FOREIGN KEY (`agency_id`) REFERENCES `agency` (`agency_id`)
);

CREATE TABLE `shapes` (
    id INT(12) NOT NULL PRIMARY KEY AUTO_INCREMENT,
    transit_system VARCHAR(50) NOT NULL,
    shape_id VARCHAR(100) NOT NULL,
    shape_pt_lat DECIMAL(8,6) NOT NULL,
    shape_pt_lon DECIMAL(8,6) NOT NULL,
    shape_pt_sequence TINYINT(3) NOT NULL,
    shape_dist_traveled VARCHAR(50),
    KEY `shape_id` (shape_id)
);

CREATE TABLE `stops` (
    transit_system VARCHAR(50) NOT NULL,
    stop_id VARCHAR(255),
    stop_code VARCHAR(50),
    stop_name VARCHAR(255) NOT NULL,
    stop_desc VARCHAR(255),
    stop_lat DECIMAL(10,6) NOT NULL,
    stop_lon DECIMAL(10,6) NOT NULL,
    zone_id VARCHAR(255),
    stop_url VARCHAR(255),
    location_type VARCHAR(2),
    parent_station VARCHAR(100),
    stop_timezone VARCHAR(50),
    wheelchair_boarding TINYINT(1),
    PRIMARY KEY (stop_id),
    KEY `zone_id` (zone_id),
    KEY `stop_lat` (stop_lat),
    KEY `stop_lon` (stop_lon),
    KEY `location_type` (location_type),
    KEY `parent_station` (parent_station)
);

CREATE TABLE `trips` (
    transit_system VARCHAR(50) NOT NULL,
    route_id VARCHAR(100) NOT NULL,
    service_id VARCHAR(100) NOT NULL,
    trip_id VARCHAR(255),
    trip_headsign VARCHAR(255),
    trip_short_name VARCHAR(255),
    direction_id TINYINT(1), #0 for one direction, 1 for another.
    block_id VARCHAR(11),
    shape_id VARCHAR(11),
    wheelchair_accessible TINYINT(1), #0 for no information, 1 for at least one rider accommodated on wheel chair, 2 for no riders accommodated.
    bikes_allowed TINYINT(1), #0 for no information, 1 for at least one bicycle accommodated, 2 for no bicycles accommodated
    PRIMARY KEY (trip_id),
    KEY `route_id` (route_id),
    KEY `service_id` (service_id),
    KEY `direction_id` (direction_id),
    KEY `block_id` (block_id),
    KEY `shape_id` (shape_id),
    CONSTRAINT `route_id` FOREIGN KEY (`route_id`) REFERENCES `routes` (`route_id`),
    CONSTRAINT `service_id` FOREIGN KEY (`service_id`) REFERENCES `calendar` (`service_id`)
);

CREATE TABLE `stop_times` (
    id INT(12) NOT NULL PRIMARY KEY AUTO_INCREMENT,
    transit_system VARCHAR(50) NOT NULL,
    trip_id VARCHAR(100) NOT NULL,
    arrival_time VARCHAR(8) NOT NULL,
    arrival_time_seconds INT(100),
    departure_time VARCHAR(8) NOT NULL,
    departure_time_seconds INT(100),
    stop_id VARCHAR(100) NOT NULL,
    stop_sequence VARCHAR(100) NOT NULL,
    stop_headsign VARCHAR(50),
    pickup_type VARCHAR(2),
    drop_off_type VARCHAR(2),
    shape_dist_traveled VARCHAR(50),
    KEY `trip_id` (trip_id),
    KEY `arrival_time_seconds` (arrival_time_seconds),
    KEY `departure_time_seconds` (departure_time_seconds),
    KEY `stop_id` (stop_id),
    KEY `stop_sequence` (stop_sequence),
    KEY `pickup_type` (pickup_type),
    KEY `drop_off_type` (drop_off_type),
    CONSTRAINT `trip_id` FOREIGN KEY (`trip_id`) REFERENCES `trips` (`trip_id`),
    CONSTRAINT `stop_id` FOREIGN KEY (`stop_id`) REFERENCES `stops` (`stop_id`)
);

CREATE TABLE `transfers` (
    id INT(12) NOT NULL PRIMARY KEY AUTO_INCREMENT,
    transit_system VARCHAR(50) NOT NULL,
    from_stop_id INT(100) NOT NULL,
    to_stop_id VARCHAR(8) NOT NULL,
    transfer_type TINYINT(1) NOT NULL,
    min_transfer_time VARCHAR(100)
);

Я положил xyz_id ключи как PRIMARY KEY в своем собственном столе и как FOREIGN KEY в других.
У меня еще есть некоторые оптимизации для этой схемы.

Теперь этот запрос работает менее чем за 1-5 секунд:

SELECT
    s.stop_id,
    (6371000*acos(cos(radians(48.1128135))*cos(radians(s.stop_lat))*cos(radians(-1.6470705)-radians(s.stop_lon))+sin(radians(48.1128135))*sin(radians(s.stop_lat)))) AS distance,
    t.route_id,
    st.*,
    t.*,
    r.*,
    c.*

FROM stop_times st

LEFT JOIN stops s USING (stop_id)
LEFT JOIN trips t USING (trip_id)
LEFT JOIN routes r USING (route_id)

LEFT JOIN calendar c ON c.service_id = t.service_id 

where
    c.start_date <= 20140915
    and c.end_date >= 20140915
    and c.sunday = 1

    and st.departure_time > '15:00:00'

HAVING
    distance < 200

ORDER BY st.departure_time ASC

Answer 2

Краткий ответ: используйте объединения таблиц и индексы.

Вот более длинный ответ:

У вас есть правильная идея, и ваше понимание того, как таблицы связаны друг с другом, является правильным. Однако, попросив СУБД сопоставить значения полей из списка (используя WHERE...IN) вместо того, чтобы объединять таблицы, вы требуете, чтобы он выполнял гораздо больше работы, чем нужно.

Что вы действительно хотите сделать, это выполнить все это как один запрос, используя JOIN пункты, чтобы связать таблицы вместе. Попробуйте это, которое дополнительно присоединяется к calendars а также calendar_dates Таблицы, чтобы ограничить результаты только маршрутами, действующими сегодня:

SELECT DISTINCT r.id, r.route_long_name
  FROM (SELECT s.stop_id, (6371000 *
          acos(cos(radians(48.824699)) * cos(radians(s.stop_lat)) *
          cos(radians(2.3243) - radians(s.stop_lon)) +
          sin(radians(48.824699)) * sin(radians(s.stop_lat)))) AS distance
          FROM stops AS s) AS i_s
  INNER JOIN stop_times AS st ON st.stop_id = i_s.stop_id
  INNER JOIN (SELECT trip_id, route_id FROM trips AS t
                INNER JOIN (SELECT service_id FROM calendars
                              WHERE start_date <= '2014-09-09'
                                AND end_date >= '2014-09-09'
                                AND tuesday = 1
                              UNION
                                SELECT service_id FROM calendar_dates
                                  WHERE date = '2014-09-09'
                                    AND exception_type = 1
                              EXCEPT
                                SELECT service_id FROM calendar_dates
                                  WHERE date = '2014-09-09'
                                    AND exception_type = 2) AS c
                   ON c.service_id = t.service_id) AS t_r
    ON t_r.trip_id = st.trip_id
  INNER JOIN routes AS r ON r.route_id = t_r.route_id
  WHERE st.departure_time > '$now'
    AND i_s.distance < 200;

Вот INNER JOIN используется для "добавления" столбцов другой таблицы, включая только те строки, которые соответствуют условию в ON пункт. Это должно быть намного быстрее, чем генерировать список результатов с одним запросом и затем передавать его следующему.

Однако, чтобы получить еще лучшую производительность, вам нужно создать индексы, которые не позволяют СУБД выполнять линейное сканирование по таблицам. Эмпирическое правило должно иметь индекс, определенный для каждого столбца, используемого в JOIN или WHERE пункт. Вот определенные мной индексы, которые вы должны найти, чтобы приведенный выше запрос работал достаточно хорошо:

CREATE INDEX calendar_dates_date_exception_type_service_id_index
  ON calendar_dates (date, exception_type, service_id);

CREATE INDEX trips_service_id_trip_id_route_id_index
  ON trips (service_id, trip_id, route_id);

CREATE INDEX stop_times_trip_id_departure_time_stop_id_index
  ON stop_times (trip_id, departure_time, stop_id);

CREATE INDEX routes_route_id_index ON routes (route_id);

CREATE INDEX stops_stop_id_index ON stops (stop_id);

Answer 3

Я могу только сказать вам, что я пробовал то же самое с SQL, и это заняло целую вечность, поэтому мне пришлось написать сценарий, сначала на Perl (без усиления), затем на C++ (увеличение в 35 раз быстрее).