mysql - 如何在数据库里优化 汉明距离 查询？

Question

项目里需要一个搜索相似图片的功能，百度了一些dhash的算法，生成了16个长度的hash值，在mysql里这样查询：

 SELECT pk, hash, 
 BIT_COUNT(   CONV(hash, 16, 10) ^ CONV('4c8e3366c275650f', 16, 10) ) as hamming_distance   
 FROM image_hashes   HAVING hamming_distance < 4   ORDER BY hamming_distance ASC; 

经测试，15W条数据，搜索需要很长时间。第二次速度会快些，有啥办法可以优化？

Answer 1

ご招待いただきありがとうございます。

申し訳ありませんが、私はこれを行ったことはありませんが、ハミング距離については以前に聞いたことがあります。データは 15,000 個と多くはありませんが、mysql 関数を使用してインデックスを作成する方法はありません。 。 。

少し検索した結果、同じ問題が見つかりました。

ハミング距離の計算、ほぼ 40w の XOR 計算、それを解除する方法については、mysql 画像を参照してください。

SQL でのバイナリ文字列のハミング距離

MySQL のメモリ テーブルの特徴と使い方を試すことができます。

Answer 2

申し訳ありませんが、「ハミング距離」については経験がありません。

データが 15W しかない場合は、データをメモリにロードしてキャッシュし、プログラム内で計算を実行できます。結局のところ、SQL はこのようなことを行うのは得意ではありません。

SQL に基づいて考えると、最適化の余地はほとんどありません。

• hash 列は、varchar ではなく char を使用します。

• ORDER BY hamming_ distance ASC を破棄し、プログラムごとに並べ替えるように変更します

分析のために DDL ステートメントと EXPLAIN 結果を一緒に送信することをお勧めしますが、最大のパフォーマンス チェックポイントは BIT_COUNT(CONV(hash, 16, 10) ^ CONV('4c8e3366c275650f', 16, 10)) である必要があります。 hamming_ distance のように、実際にはテーブル全体のスキャンと同等です。