Как оптимизировать этот расчет Левенштейна

Question

Table a имеет около 8000 строк и table b имеет около 250000 строк. Без levenshtein Функция запроса занимает чуть менее 2 секунд. С включенной функцией это занимает около 25 минут.

SELECT
      *
   FROM
      library a,
      classifications b
   WHERE  
      a.`release_year` = b.`year`
      AND a.`id` IS NULL
      AND levenshtein_ratio(a.title, b.title) > 82

Answer 1

Я предполагаю что levenshtein_ratio это функция, которую вы написали (или, может быть, включены откуда-то еще). Если это так, сервер базы данных не сможет оптимизировать это в обычном смысле использования индекса. Таким образом, это означает, что ему просто нужно вызывать его для каждой записи, которая является результатом других условий соединения. При внутреннем объединении это может быть очень большое число с размерами таблицы (максимум 8000*250000 = 2 миллиарда). Вы можете проверить общее количество раз, которое нужно будет вызвать с помощью этого:

SELECT
      count(*)
   FROM
      library a,
      classifications b
   WHERE  
      a.`release_year` = b.`year`
      AND a.`id` IS NULL

Это объяснение того, почему оно медленное (на самом деле это не ответ на вопрос, как его оптимизировать). Чтобы оптимизировать его, вам, вероятно, потребуется добавить дополнительные ограничивающие факторы в условие соединения, чтобы уменьшить количество вызовов пользовательской функции.

Answer 2

Вы даете слишком мало информации, чтобы реально помочь вам.

1) Моим первым предположением будет попытка создать другие условия WHERE, которые уменьшат количество сканируемых строк.

2) Если это невозможно... Учитывая, что заголовки из библиотеки таблиц и классификаций известны, одной идеей будет создание таблицы, в которой все данные уже рассчитаны, следующим образом:

TABLE levenshtein_ratio
id_table_library
id_table_classifications
precalculated_levenshtein_ratio

поэтому вы должны заполнить таблицу с помощью этого запроса:

insert into levenshtein_ratio select a.id, b.id, levenshtein_ratio(a.title, b.title) from library, classifications

и тогда ваш запрос будет:

    SELECT
          *
       FROM
          library a LEFT JOIN 
          classifications b ON a.`release_year` = b.`year`

LEFT JOIN levenshtein_ratio c ON c.id_table_library = a.id AND c.id_table_classifications = b.id
       WHERE  
          a.`id` IS NULL
          AND precalculated_levenshtein_ratio > 82

этот запрос, вероятно, будет длиться не более 2 секунд.

Проблема с этим решением заключается в том, что данные в таблицах a и b могут изменяться, поэтому вам нужно будет создать триггер для его обновления.

Answer 3

Измените свой запрос, чтобы использовать правильные объединения (синтаксис существует с 1996 года).

Кроме того, все ваше состояние levensrein может быть переведено в состояние соединения, которое должно дать вам преимущество в производительности:

SELECT *
FROM library a
JOIN classifications b
    ON a.`release_year` = b.`year`
    AND levenshtein_ratio(a.title, b.title) > 82
WHERE a.`id` IS NULL

Также убедитесь, что на b.year есть индекс:

create index b_year on b(year);