У меня есть сценарий php, который проверяет расстояние Хемминга между двумя фотографиями, снятыми с камеры безопасности.

Таблица mySQL с 2,4M строками состоит из Key и 4 INT (10). INT (10) были проиндексированы индивидуально, вместе и вместе с Ключом, но у меня нет убедительных доказательств того, что любая комбинация была быстрее, чем другие. Я могу попробовать еще раз, если вы предложите это сделать.

Вес Хэмминга рассчитывается путем преобразования изображения в 8x16 пикселей, и каждая четверть битов сохраняется в столбце pHash0, pHash1 ... и т. Д.

Есть 2 способа, которыми я написал это. Первым способом было использование вложенных производных таблиц. Теоретически, каждый вывод должен иметь меньше данных для проверки, чем его предшественник. Запрос представляет собой подготовленное утверждение, а? поля - это pHash [0-3] файла, с которым я проверяю.

Select
    `Key`,
    Bit_Count(T3.pHash3 ^ ?) + T3.BC2 As BC3
  From
    (Select
      *,
      Bit_Count(T2.pHash2 ^ ?) + T2.BC1 As BC2
    From
      (Select
        *,
        Bit_Count(T1.pHash1 ^ ?) + T1.BC0 As BC1
      From
        (Select
          `Key`,
          pHash0,
          pHash1,
          pHash2,
          pHash3,
          Bit_Count(pHash0 ^ ?) As BC0
        From
          files
        Where
          Not pHash0 Is Null And
          Bit_Count(pHash0 ^ ?) < 4) As T1
      Where
        Bit_Count(T1.pHash1 ^ ?) + T1.BC0 < 4) As T2
    Where
      Bit_Count(T2.pHash2 ^ ?) + T2.BC1 < 4) As T3
  Where
    Bit_Count(T3.pHash3 ^ ?) + T3.BC2 < 4

Второй подход был немного более прямым. Он просто сделал всю работу одновременно.

Select
    `Key`,
  From
    files
  Where
    Not pHash0 is null AND
    Bit_Count(pHash0 ^ ?) + Bit_Count(pHash1 ^ ?) + Bit_Count(pHash2 ^
    ?) + Bit_Count(pHash3 ^ ?) < 4

Первый запрос выполняется быстрее для больших наборов записей, а второй - быстрее для небольших наборов записей, но ни один из них не будет превышать 1–1 / 3 секунды для сравнения на 2,4 млн. Записей.

Вы видите способ настроить этот процесс, чтобы сделать его быстрее? Можно быстро попробовать любые предложения, такие как изменение типов данных или индексов.

Это Win7x64, MySQL / 5.6.6 и InnoDB, nginx / 1.99, php-cgi / 7.0.0 с поддержкой Zend. Сценарий вызывается с веб-страницы, и буферизация отключена для немедленной обратной связи.

РЕДАКТИРОВАТЬ:

Это могло бы работать лучше, если бы я изменил 4 32-битных целых числа на 1 двоичное (16), что изменило бы сравнение с 4 на одно, но мне также пришлось бы преобразовать мои 4 параметра в 128-битный символ, что php не буду делать Если бы был быстрый способ объединить их, он мог бы выжать немного больше свободного времени.

РЕДАКТИРОВАТЬ Принятый ответ увеличил скорость на ~ 500%. Краткий обзор нашей гипотезы: Количество битов pHash «A» всегда будет в пределах pHash «B» +/- Расстояние Хэмминга.

Отдельное спасибо @duskwuff за упорство и терпение. Приветствия @ duskwuff!

РЕДАКТИРОВАТЬ Это был мой последний запрос:

Select
  files.`Key`, 
  Bit_Count(? ^ pHash0) + Bit_Count(? ^ pHash1) +
  Bit_Count(? ^ pHash2) + Bit_Count(? ^ pHash3) as BC
  From
    files FORCE INDEX (bitcount)
  Where
    bitCount Between ? And ? 
  AND Bit_Count(? ^ pHash0) + Bit_Count(? ^ pHash1) +
  Bit_Count(? ^ pHash2) + Bit_Count(? ^ pHash3) <= ?
  ORDER BY Bit_Count(? ^ pHash0) + Bit_Count(? ^ pHash1) +
  Bit_Count(? ^ pHash2) + Bit_Count(? ^ pHash3)

Где первые 4 "?" представляют 4 32-битных хэша проверяемого файла, следующие 2 "?" представляет предварительно рассчитанный битовый счет этого файла +/- желаемое расстояние Хемминга, а последний "?" представляет это расстояние Хэмминга. Предложение ORDER BY необходимо только для того, чтобы приблизить самые близкие совпадения, где предложение LIMIT 1 вернет наилучшее совпадение. Существует индекс B-TREE наbitcount поле.

Дисперсия битовых подсчетов из 2,4 миллионов файлов оказалась в форме колокольчика с 3 или 4 крайностями, с 70 000 в центре. Если задан файл с 64-битным счетом (что является наихудшим случаем), поиск файлов в пределах расстояния Хемминга 3 означает сравнение 20% файлов (490 000 в моем случае), тогда как поиск расстояния Хэмминга 0 будет сравнивать только 2,8% записей (70000, конечно).