⬆
pgvector 0.7.0 でバイナリインデックス＆量子化を試してみた
先日 Qiita に書いたこちら ↓ の記事の内容が README 丸写しすぎたので、バイナリ（ビット）インデックスと量子化の効果を少しだけ試してみました。
やったこと
以下の構成で、インデックスの作成とベクトル検索の所要時間を確認・比較しました。
- 環境 : いずれも AWS オレゴン（us-west-2）リージョン
- データベース : RDS for PostgreSQL 16.3
- db.m6g.large（2vCPU・8GB Mem）
- pgvector 0.7.0 をサポート
- Embeddings モデル : Amazon Bedrock Titan Text Embeddings V2
- 1024 次元
- 正規化あり
- データベース : RDS for PostgreSQL 16.3
- 使用データ
-
https://huggingface.co/datasets/takaaki-inada/databricks-dolly-15k-ja-zundamon
- 2024/5/22 時点のデータ
- そのうち、
outputに値があり、Titan Text Embeddings V2 でトークンサイズが 8,192 を超えないもの（4,594 件） -
outputとinstructionをそれぞれ個別の行としてテーブルに登録（計 9,188 行） - データ行に登録するベクトルは 32 ビット float 値
-
https://huggingface.co/datasets/takaaki-inada/databricks-dolly-15k-ja-zundamon
- インデックス : 以下の作成時間と検索時間を比較
- インデックスなし
- ベクトル検索（内積）で
instructionの 1 行目に近いほうから 5 件のoutput行を抽出
- ベクトル検索（内積）で
- 32 ビット float 値の HNSW インデックス
- 同上（インデックスを使う）
- バイナリ（ビット）インデックス
- 32 ビット float 値をバイナリ量子化
- インデックスを使ってベクトル検索（ハミング距離）して 20 件に絞り込んだものを 32 ビット float 値の内積で 5 件の
output行を抽出
- インデックスなし
データ投入
こちらにある Python スクリプトを使ってデータを投入しました。
インデックスがない状態でベクトル検索
質問文
postgres=> SELECT id, data FROM rerank_test WHERE id = 100000;
-[ RECORD 1 ]----------------------------------------------------------
id | 100000
data | ヴァージン・オーストラリア航空はいつから運航を開始したのですか？
Time: 139.100 ms
この質問文（instruction）に近い内容の回答（output）を抽出しました。
インデックスなしの結果
postgres=> SELECT id, (embedding <#> (SELECT embedding FROM rerank_test WHERE id = 100000)) * -1 AS inner_product, data FROM rerank_test WHERE id < 100000 ORDER BY inner_product DESC LIMIT 5;
-[ RECORD 1 ]-+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
id | 0
inner_product | 0.7999640703201294
data | ヴァージン・オーストラリア航空（Virgin Australia Airlines Pty Ltd）はオーストラリアを拠点とするヴァージン・ブランドを冠する最大の船団規模を持つ航空会社なのだ。2000年8月31日に、ヴァージン・ブルー空港として、2機の航空機、1つの空路を運行してサービスを開始しました。2001年9月のアンセット・オーストラリア空港の崩壊後、オーストラリアの国内市場で急速に地位を確立しました。その後はブリスベン、メルボルン、シドニーをハブとして、オーストラリア国内の32都市に直接乗り入れるまでに成長しました。
-[ RECORD 2 ]-+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
id | 3355
inner_product | 0.4171184301376343
data | N.V. Virgin Express S.A.は、ヴァージン・グループ内に誕生したベルギーの航空会社なのだ。ブリュッセル空港をハブ空港として、主に南欧方面へのフライトを運航していました。航空券は主にインターネットを通じて販売されました。SNブリュッセル航空と合併してブリュッセル航空となり、2007年3月25日に運航を開始した。 バージン・エクスプレスの本社はブリュッセル近郊のベルギー・ザベンタムのブリュッセル空港の116号館にある。 +
| +
| 沿革 +
| 1996年4月23日、ヴァージン・グループ（会長リチャード・ブランソン）は、ビクター・ハッソンとジョルジュ・グーテルマンが設立したベルギーのレジャー航空会社EBA - ユーロベルジアン・エアラインズを買収し、ヴァージン・エクスプレスのブランド名に改名しました またEBAのボーイング737を引き継ぎ、以降このタイプの航空機で運行しました。すぐにブリュッセルのハブ空港から低予算の定期便に集中し、サベナや後のSNブリュッセル航空の主要な競争相手となった。 +
| +
| 2004年10月、ヴァージン・グループはSNブリュッセル航空に資産を売却し、両航空会社はエチエンヌ・ダヴィニョン子爵が会長を務める親会社の持ち株会社SNエアホールディングに統合されました。 +
| +
| 2006年3月31日、SNブリュッセル航空とヴァージン・エクスプレスは合併し、ブリュッセル航空と命名したことを発表しました。統合後の航空会社は長距離路線を追加し、アフリカでの地位を強化した。
-[ RECORD 3 ]-+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
id | 6819
inner_product | 0.2454237937927246
data | OA形は、ボールドウィン機関車製作所がニュージーランドのウェリントン＆マナワツ鉄道（WMR）のために製作した孤高の蒸気機関車なのだ。1894年に発注され、同年8月に13号機として運行を開始し、世界初のナローゲージのヴォークレイン配合となりました。1908年、WMRとその機関車群はニュージーランド鉄道局（NZR）に買収され、全国鉄道網に組み込まれた。13号機はOクラスのメンバーとは似ているが、十分に異なるため、別の分類が必要なのだ。13号車はO型に似ていたが、十分な違いがあり、別の分類が必要であったため、OAという名称が作られ、OA 457という番号が付けられた。1929年12月にオークランドで撤去されるまで、さらに20年間運行された。この機関車はWMRのスタッフには「The Lady」と呼ばれていた。
-[ RECORD 4 ]-+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
id | 1540
inner_product | 0.22488926351070404
data | 橋が架かる前、サンフランシスコと現在のマリン郡を結ぶ唯一の実用的な近道は、サンフランシスコ湾の一角を船で渡ることであった。1820年には早くもフェリーの運航が始まり、1840年代にはサンフランシスコへの水運を目的とした定期運航が開始された。 +
| +
| 1867年に開始されたサウサリート・ランド・アンド・フェリー・カンパニーのサービスは、やがてサザン・パシフィック鉄道の子会社であるゴールデン・ゲート・フェリー・カンパニーとなり、1920年代後半には世界最大のフェリー運航会社となりました。かつては鉄道の乗客や顧客だけのものだったサザン・パシフィックの自動車フェリーは、非常に収益性が高く、地域経済にとって重要なものとなりました。サンフランシスコのハイド・ストリート・ピアとマリン郡のサウサリート・フェリー・ターミナルを結ぶフェリーの所要時間は約20分、料金は車1台につき1ドルだった[when?]が、後に新しい橋に対抗するために値下げされた。サンフランシスコ・フェリー・ビルディングからの所要時間は27分であった。
-[ RECORD 5 ]-+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
id | 3120
inner_product | 0.22459137439727783
data | Oy Air Finlandは、フィンランドのヴァンターにあるヘルシンキ空港を本社・拠点とする航空会社で、休暇先へのチャーター便や定期便、航空機リースサービスを行っていました。2002年に創業し、2012年に破産を申請しているのだ。 +
| +
| 沿革 +
| +
| カンゲルルススアーク空港の旧カラーリングのボーイング757-200（2010年）。 +
| +
| マラガ空港で最新のカラーリングを施したボーイング757-200（2012年）。 +
| +
| リーズ・ブラッドフォード国際空港で、Jet2 Holidaysの基本カラーをまとった元エア・フィンランド航空のボーイング757-200（2011年）。 +
| 2002年1月に設立され、2003年4月3日に運航を開始した航空会社なのだ。航空業界、金融業界、旅行マーケティング業界出身の3人によって所有されていました：Harri Naivo（会長兼最高財務責任者）、Mika Helenius（最高経営責任者）、Lauri Komi。2007年3月時点の従業員数は210名であった。2012年6月26日、エア・フィンランドはすべてのフライトを直ちにキャンセルすることを発表し、破産を申請した。
Time: 173.794 ms
データ量が少ないので 0.17 秒程度でした。
32 ビット float インデックス（HNSW）を作成して検索
まずはインデックスを作成します。
通常インデックス（HNSW）作成
postgres=> CREATE INDEX ON rerank_test USING hnsw (embedding vector_ip_ops);
CREATE INDEX
Time: 9103.665 ms (00:09.104)
9.1 秒かかりました。
この状態で、先ほどと同じ検索を行います。
通常インデックスありの結果
postgres=> SELECT id, (embedding <#> (SELECT embedding FROM rerank_test WHERE id = 100000)) * -1 AS inner_product, data FROM rerank_test WHERE id < 100000 ORDER BY inner_product DESC LIMIT 5;
-[ RECORD 1 ]-+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
id | 0
inner_product | 0.7999640703201294
data | ヴァージン・オーストラリア航空（Virgin Australia Airlines Pty Ltd）はオーストラリアを拠点とするヴァージン・ブランドを冠する最大の船団規模を持つ航空会社なのだ。2000年8月31日に、ヴァージン・ブルー空港として、2機の航空機、1つの空路を運行してサービスを開始しました。2001年9月のアンセット・オーストラリア空港の崩壊後、オーストラリアの国内市場で急速に地位を確立しました。その後はブリスベン、メルボルン、シドニーをハブとして、オーストラリア国内の32都市に直接乗り入れるまでに成長しました。
-[ RECORD 2 ]-+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
id | 3355
inner_product | 0.4171184301376343
data | N.V. Virgin Express S.A.は、ヴァージン・グループ内に誕生したベルギーの航空会社なのだ。ブリュッセル空港をハブ空港として、主に南欧方面へのフライトを運航していました。航空券は主にインターネットを通じて販売されました。SNブリュッセル航空と合併してブリュッセル航空となり、2007年3月25日に運航を開始した。 バージン・エクスプレスの本社はブリュッセル近郊のベルギー・ザベンタムのブリュッセル空港の116号館にある。 +
（中略）
-[ RECORD 3 ]-+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
id | 6819
inner_product | 0.2454237937927246
data | OA形は、ボールドウィン機関車製作所がニュージーランドのウェリントン＆マナワツ鉄道（WMR）のために製作した孤高の蒸気機関車なのだ。1894年に発注され、同年8月に13号機として運行を開始し、世界初のナローゲージのヴォークレイン配合となりました。1908年、WMRとその機関車群はニュージーランド鉄道局（NZR）に買収され、全国鉄道網に組み込まれた。13号機はOクラスのメンバーとは似ているが、十分に異なるため、別の分類が必要なのだ。13号車はO型に似ていたが、十分な違いがあり、別の分類が必要であったため、OAという名称が作られ、OA 457という番号が付けられた。1929年12月にオークランドで撤去されるまで、さらに20年間運行された。この機関車はWMRのスタッフには「The Lady」と呼ばれていた。
-[ RECORD 4 ]-+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
id | 1540
inner_product | 0.22488926351070404
data | 橋が架かる前、サンフランシスコと現在のマリン郡を結ぶ唯一の実用的な近道は、サンフランシスコ湾の一角を船で渡ることであった。1820年には早くもフェリーの運航が始まり、1840年代にはサンフランシスコへの水運を目的とした定期運航が開始された。 +
（中略）
-[ RECORD 5 ]-+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
id | 3120
inner_product | 0.22459137439727783
data | Oy Air Finlandは、フィンランドのヴァンターにあるヘルシンキ空港を本社・拠点とする航空会社で、休暇先へのチャーター便や定期便、航空機リースサービスを行っていました。2002年に創業し、2012年に破産を申請しているのだ。 +
（中略）
Time: 175.982 ms
インデックスなしと抽出結果は変わらず、所要時間もほぼ変わりませんでした。
バイナリ（ビット）インデックス（HNSW）を作成して Re-rank 検索
続いて今回のメインテーマ、バイナリインデックス＆量子化です。
まずは（先ほどのインデックスを削除してから）インデックスを作成します。
通常インデックス削除
postgres=> \di
List of relations
-[ RECORD 1 ]---------------------
Schema | public
Name | rerank_test_embedding_idx
Type | index
Owner | postgres
Table | rerank_test
-[ RECORD 2 ]---------------------
Schema | public
Name | rerank_test_pkey
Type | index
Owner | postgres
Table | rerank_test
postgres=> DROP INDEX rerank_test_embedding_idx;
DROP INDEX
Time: 152.619 ms
バイナリインデックス（HNSW）作成
postgres=> CREATE INDEX ON rerank_test USING hnsw ((binary_quantize(embedding)::bit(1024)) bit_hamming_ops);
CREATE INDEX
Time: 3356.522 ms (00:03.357)
3.4 秒ほどでした。通常の 32 ビット float インデックスより速いですね。
そして、このインデックスを使ってハミング距離が近い順に 20 件絞り込んでから、32 ビット float ベクトルの内積で近い順に 5 件抽出します。
バイナリインデックスで Re-rank
postgres=> SELECT id, (embedding <#> (SELECT embedding FROM rerank_test WHERE id = 100000)) * -1 AS inner_product, data FROM (SELECT * FROM rerank_test WHERE id < 100000 ORDER BY binary_quantize(embedding)::bit(1024) <~> (SELECT binary_quantize(embedding)::bit(1024) FROM rerank_test WHERE id = 100000) LIMIT 20) ORDER BY inner_product DESC LIMIT 5;
-[ RECORD 1 ]-+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
id | 0
inner_product | 0.7999640703201294
data | ヴァージン・オーストラリア航空（Virgin Australia Airlines Pty Ltd）はオーストラリアを拠点とするヴァージン・ブランドを冠する最大の船団規模を持つ航空会社なのだ。2000年8月31日に、ヴァージン・ブルー空港として、2機の航空機、1つの空路を運行してサービスを開始しました。2001年9月のアンセット・オーストラリア空港の崩壊後、オーストラリアの国内市場で急速に地位を確立しました。その後はブリスベン、メルボルン、シドニーをハブとして、オーストラリア国内の32都市に直接乗り入れるまでに成長しました。
-[ RECORD 2 ]-+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
id | 3355
inner_product | 0.4171184301376343
data | N.V. Virgin Express S.A.は、ヴァージン・グループ内に誕生したベルギーの航空会社なのだ。ブリュッセル空港をハブ空港として、主に南欧方面へのフライトを運航していました。航空券は主にインターネットを通じて販売されました。SNブリュッセル航空と合併してブリュッセル航空となり、2007年3月25日に運航を開始した。 バージン・エクスプレスの本社はブリュッセル近郊のベルギー・ザベンタムのブリュッセル空港の116号館にある。 +
（中略）
-[ RECORD 3 ]-+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
id | 6819
inner_product | 0.2454237937927246
data | OA形は、ボールドウィン機関車製作所がニュージーランドのウェリントン＆マナワツ鉄道（WMR）のために製作した孤高の蒸気機関車なのだ。1894年に発注され、同年8月に13号機として運行を開始し、世界初のナローゲージのヴォークレイン配合となりました。1908年、WMRとその機関車群はニュージーランド鉄道局（NZR）に買収され、全国鉄道網に組み込まれた。13号機はOクラスのメンバーとは似ているが、十分に異なるため、別の分類が必要なのだ。13号車はO型に似ていたが、十分な違いがあり、別の分類が必要であったため、OAという名称が作られ、OA 457という番号が付けられた。1929年12月にオークランドで撤去されるまで、さらに20年間運行された。この機関車はWMRのスタッフには「The Lady」と呼ばれていた。
-[ RECORD 4 ]-+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
id | 1540
inner_product | 0.22488926351070404
data | 橋が架かる前、サンフランシスコと現在のマリン郡を結ぶ唯一の実用的な近道は、サンフランシスコ湾の一角を船で渡ることであった。1820年には早くもフェリーの運航が始まり、1840年代にはサンフランシスコへの水運を目的とした定期運航が開始された。 +
（中略）
-[ RECORD 5 ]-+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
id | 3120
inner_product | 0.22459137439727783
data | Oy Air Finlandは、フィンランドのヴァンターにあるヘルシンキ空港を本社・拠点とする航空会社で、休暇先へのチャーター便や定期便、航空機リースサービスを行っていました。2002年に創業し、2012年に破産を申請しているのだ。 +
（中略）
Time: 140.448 ms
抽出結果は変わらず、所要時間は先ほどより若干短く 0.14 秒になりました。
データ量が少ないので効果は出ないかと思いましたが、意外と効果が出ました。
2024/5/29 追記：
バイナリインデックス単独での検索結果は以下のとおりでした。
バイナリインデックス単独での検索結果
postgres=> SELECT id, (binary_quantize(embedding)::bit(1024) <~> (SELECT binary_quantize(embedding)::bit(1024) FROM rerank_test WHERE id = 100000)) AS humming_distance, data FROM rerank_test WHERE id < 100000 ORDER BY humming_distance LIMIT 5;
-[ RECORD 1 ]----+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
id | 0
humming_distance | 224
data | ヴァージン・オーストラリア航空（Virgin Australia Airlines Pty Ltd）はオーストラリアを拠点とするヴァージン・ブランドを冠する最大の船団規模を持つ航空会社なのだ。2000年8月31日に、ヴァージン・ブルー空港として、2機の航空機、1つの空路を運行してサービスを開始しました。2001年9月のアンセット・オーストラリア空港の崩壊後、オーストラリアの国内市場で急速に地位を確立しました。その後はブリスベン、メルボルン、シドニーをハブとして、オーストラリア国内の32都市に直接乗り入れるまでに成長しました。
-[ RECORD 2 ]----+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
id | 3355
humming_distance | 385
data | N.V. Virgin Express S.A.は、ヴァージン・グループ内に誕生したベルギーの航空会社なのだ。ブリュッセル空港をハブ空港として、主に南欧方面へのフライトを運航していました。航空券は主にインターネットを通じて販売されました。SNブリュッセル航空と合併してブリュッセル航空となり、2007年3月25日に運航を開始した。 バージン・エクスプレスの本社はブリュッセル近郊のベルギー・ザベンタムのブリュッセル空港の116号館にある。 +
（中略）
-[ RECORD 3 ]----+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
id | 5003
humming_distance | 419
data | エアバスA380は、エアバス社が開発・製造した大型ワイドボディー旅客機なのだ。世界最大の旅客機であり、唯一の全長2階建てジェット旅客機なのだ。エアバスの研究は1988年に開始され、長距離市場におけるボーイング747の優位性に挑戦するため、1990年にプロジェクトが発表された。当時指定されていたA3XXプロジェクトは1994年に発表された。エアバスは2000年12月19日に95億ユーロ（約107億円）のA380計画を開始した。最初の試作機は2005年1月18日にトゥールーズで発表され、2005年4月27日に初飛行を行いました。その後、2006年12月12日に欧州航空安全機関（EASA）および米国連邦航空局（FAA）から型式証明書を取得した。+
| +
| 電気配線のトラブルにより、当初の生産は2年遅れ、開発費もほぼ倍増した。2007年10月15日にシンガポール航空に初めて納入され、10月25日に就航した。生産は2012年と2014年に年間30機とピークを迎えました。しかし、最大の顧客であるエミレーツ航空が2019年2月に最後の注文を減らしたため、エアバスはA380の生産を2021年に終了することを発表した。2021年12月16日、エミレーツ航空は123機目のA380を受け取りましたが、これはエアバスが納品した251機目であり、最後の機体となりました。250億ドルの投資は回収されなかった。 +
| +
| 全長2階建てのこの航空機は、通常525人乗りで、最大認定人数は853人なのだ。クワッドジェットは、エンジンアライアンスGP7200またはロールスロイス・トレント900ターボファンを搭載し、8,000 nmi（14,800 km）の航続距離を提供するのだ。2021年12月現在、世界のA380フリートは、730万ブロック時間にわたって80万回以上のフライトをこなし、死亡事故や船体損傷はありません。2022年12月現在、世界16社の運航会社で237機が就航しているのだ。
-[ RECORD 4 ]----+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
id | 65
humming_distance | 426
data | イギリス領ヴァージン諸島（BVI）、通称ヴァージン諸島は、カリブ海にあるイギリス海外領土で、プエルトリコとアメリカ領ヴァージン諸島の東、アンギラの北西に位置しているのだ。地理的にはバージン諸島の一部であり、小アンティル諸島のリーワード諸島に位置し、西インド諸島の一部なのだ。 +
| +
| 英領ヴァージン諸島は、トルトラ、ヴァージン・ゴルダ、アネガダ、ヨスト・ヴァン・ダイクの主要な島々と、50以上の小さな島や湾で構成されているのだ。そのうち、約16の島には人が住んでいるのだ。首都ロードタウンは、最大の島であるトルトラ島にあり、長さ約20km（12マイル）、幅約5km（3マイル）の大きさなのだ。2010年国勢調査での人口は28,054人で、そのうち23,491人がトルトラ島に住んでいたが、現在の推計では35,802人となっている（2018年7月）。
-[ RECORD 5 ]----+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
id | 5206
humming_distance | 430
data | オーストラリア太平洋空港株式会社（APAC）は、非上場企業であり、オーストラリアの2つの空港の所有者である：メルボルン空港とローンセストン空港の2つの空港を所有しているのだ。各空港は、APACが支配権を持つ空港賃借人会社によって運営されています：オーストラリア・パシフィック・エアポーツ（メルボルン）Pty Ltdとオーストラリア・パシフィック・エアポーツ（ローンセストン）Pty Ltdがそれぞれ支配的な株式を保有している。
Time: 139.787 ms
3 番目以降の結果が違いますね。
所要時間は Re-rank 検索より少しだけ短い程度でした。Re-rank 検索の第一段階と同じLIMIT 20だともう少し差が小さくなりそうです。
まとめ
- バイナリ量子化でインデックスの容量を削減することにより、インデックス作成時間を短縮できる
- データがそれほど多いテーブルでなくても、バイナリインデックスである程度絞り込んでから本来の精度でバイナリ検索する方法（Re-rank）を使うと、検索時間を短縮できる可能性がある
- データによっては精度が落ちたり検索時間の短縮ができない可能性はある
Discussion