4

検索セットと交差するセットをデータベースで検索したいと思います。交点の大きさの順に結果を返してほしいです。

データベース行内のセットは、約 10,000 のオーダーになります。検索セットは約 500 のオーダーです。データベースの行数は約 1,000,000 です。

クエリの例:

search_set = [このセットには 500 個の ID があります]

SELECT 行 WHERE "find_set" INTERSECTS "search_set"
    ORDER BY 「交差点の大きさ」

例のデータベース:

インデックス find_set
1 [10,000 ID で設定]
2 [5,000個のidで設定]
...
1,000,000 [15,000 ID で設定]
  • このクエリにかかる時間はどれくらいですか?
  • 使用すべき特定のデータベースまたはデータベース ライブラリはありますか?
  • 前処理をする必要がありますか？
  • データベースはこのタイプのクエリをどのように実装しますか? 「search_set」内の 500 個の ID ごとに 1 回検索しますか?
  • この種の問題とその解決方法について、他に知っておくべきことは何ですか?

本当にありがとう！

4

1 に答える 1

1

このクエリのパフォーマンスは、データベース最適化エンジンとクエリの実行方法に大きく依存します。

まず第一に、データベースには通常、列に15,000のIDを持つテーブルがありません。代わりに、次のテーブルのペアのようなものが必要になります。

set
---
id

set_entry
-----------
id
set_id
entry

最初のテーブルには100万行が含まれます。2番目は100億のようです。にインデックスを付けset_entry.entryます。

一般的にクエリを配置する最良の方法は、行がクエリセットの値であるある種の一時テーブルを用意することです。次に、次のようなクエリを実行します。

SELECT set_entry.id, COUNT(*)
FROM set_entry
  JOIN query_entry
    ON set_entry.entry = query_entry.entry
GROUP BY set_entry.id
ORDER BY count(*) DESC

必要なクエリプランでは、要素ごとにインデックスを検索し、一致するすべての行をプルバックしてから、グループ化操作を実行して、交差する各セットにいくつあるかを把握します。最初のステップでは、500回のルックアップを実行してから、0から5億行の間のどこかにプルバックします。あなたが500万を引き戻しているとしましょう。グループ化操作は、ハッシュを作成するか、データを並べ替えることによって実行されます（データベースはどちらの方法でも実行できます）。どちらも非常に高速です。

不明な点はたくさんありますが、この計画には数秒かかる可能性があります。

注意したいのは、次のようなクエリです。

SELECT set_entry.id, COUNT(*)
FROM set_entry
WHERE entry IN (id1, id2, ....)
GROUP BY set_entry.id
ORDER BY count(*) DESC

私の経験では、ほとんどのデータベースエンジンはこれを調べてから、インデックスを使用できないと判断します。代わりに、すべてset_entry（100億行）をスキャンし、1つにつき500個の要素のセットをスキャンして、ペアごとの比較を行います。これは、約5兆のペアワイズ比較の最初のステップを意味します。このプランでは、CPUを何時間も簡単にビジー状態に保つことができます。

于 2012-06-26T22:02:37.907 に答える