2

PostgreSQLに保存されているStartIP、End IP、Geo-Locationsで200万のIPアドレスと2500万のIP範囲を取得しました。2500万のデータベースからそれらの200万のIPの地理的位置を検索する効率的な方法はありますか？私がしたことは、IPアドレスが開始IPと終了IPの間にあるかどうかを比較し、対応する場所を検索することでした。しかし、これは永遠にかかるようです。おそらくこれは、次の場所から{7、13、31、42}を検索するなど、一連の範囲から整数の束を検索するようなものです。

Start End Loc
1     10  US
11    20  US
21    26  CN
29    32  SE
33    45  CA

と戻る：

7  US
13 US
31 SE
42 CA

範囲が必ずしも接続されていない場合や、サイズが同じでない場合があることに注意してください。ありがとうございました！

編集

具体的な例として、私が扱っているデータは次のとおりです。

     start_ip     |      end_ip      | country |  region   |   city    | 
------------------+------------------+---------+-----------+-----------+-
 1.33.254.73/32   | 1.33.254.73/32   | jpn     | 33        | kurashiki | 
 1.39.1.0/32      | 1.39.4.255/32    | ind     | mh        | mumbai    | 
 1.40.144.0/32    | 1.40.145.255/32  | aus     | ns        | fairfield | 
 1.40.235.0/32    | 1.40.242.255/32  | aus     | ns        | sydney    | 
 1.44.28.0/32     | 1.44.29.255/32   | aus     | vi        | melbourne | 
 1.44.82.0/32     | 1.44.83.255/32   | aus     | vi        | melbourne | 
 1.44.92.0/32     | 1.44.93.255/32   | aus     | vi        | melbourne | 
 1.44.128.0/32    | 1.44.129.255/32  | aus     | vi        | melbourne | 
 1.44.220.0/32    | 1.44.221.255/32  | aus     | vi        | melbourne | 
 ......
 ......

そして、クエリは次のようなものです。

 75.149.219.61/32
 68.239.61.29/32
 96.41.50.165/32
 183.62.126.7/32
 ......
4

3 に答える 3

2

最良でより洗練された解決策は、IPと範囲をinet形式で保存することだと思います。IP範囲は通常、開始/終了としてではなく、ネットワーク/マスク形式で公開されます。これにより、JOINベースの書き込みが可能になります

ON (ip.addr << geoloc.range)

もちろん、ipテーブルはaddrでインデックス付けし、geolocは（範囲、場所）でインデックス付けする必要があります。また、CIDR形式がなく、開始/終了からビルドする必要がある場合は、コストがかかる可能性があります（ただし、テーブルの方が簡単です）後で使用する）。

見る

http://www.postgresql.org/docs/9.0/static/functions-net.html

編集：残念ながら、これらの開始/終了値は「最適化された」CIDR範囲のように見えます。言い換えれば、例えば

1.40.235.0     1.40.242.255

実際には、4つの別々の連続した範囲のマージです。

11101011   235.0-235.255
    11101100   236.0-239.255
    11101111   
    11110000   240.0-241.255   
    11110001
11110010   242.0-242.255

したがって、CIDR操作に必要な4つの行に行を分解することは実用的ではありません。

Start / Endはcidrデータ型で表示されるため、それらをinetに変換し（とにかくすべて/ 32です...）、クエリされた値をinetデータ型でも保持し、Start、Endでインデックスを作成すると、妥当な結果が得られるはずです。

 SELECT query.ip, geoloc.country, geoloc.region, geoloc.city
     FROM query JOIN geoloc
     ON (query.ip >= geoloc.start_ip AND query.ip <= geoloc.end_ip);

もう1つの方法は、あまり洗練されていませんが（実際にはハック）、たとえばaddrとrangeの最初のバイトに基づいて、ipテーブルとgeolocテーブルの両方を別々のサブテーブルに「分解」することです（最初のバイトが異なるIP範囲）。

 SELECT * FROM geoloc
     WHERE start_ip >= inet '5.0.0.0' and end_ip <= inet '5.255.255.255'
     INTO TABLE geoloc_5;

 SELECT * FROM query
     WHERE start_ip >= inet '5.0.0.0' and end_ip <= inet '5.255.255.255'
     INTO TABLE query_5;

 Remember to CREATE INDEX on geoloc_5 start_ip, end_ip

このアプローチは、数年前に大規模なPostgreSQLバッチで機能しましたが、それ以降、専用のデータ型とともに、より賢いインデックスマネージャーがこのDIYパーティションに匹敵する以上に進化することを期待しています。したがって、単純なヨルダン分割は、<<CIDR演算子を使用できない場合の最後の解決策としてのみ使用する必要があります。

とはいえ、両方のテーブルの分布がフラットであると仮定します（球場の図を取得するためだけです）。

次に、1つのSELECTの代わりに、2M x 25Mレコードで、2M / 256 x 25M/256の256のSELECTを実行します。したがって、1 x 2M x 25M = 50 Tの代わりに、256 x 2M / 256 x 25M / 256 = 192Gの比較があります。これは、ストレートJOINに比べて約200倍高速であるはずです。

しかし、繰り返しますが、適切にインデックス付けされたCIDRフィールドを確認したPostgreSQLは、実際には「ストレート」JOINを実行しなくなりますが、このトリック（およびいくつか）を使用します。

于 2012-08-21T21:15:04.037 に答える
1

列に対してクエリを実行する場合は、Loc列にインデックスを追加する必要があります。また、これは 3 列のテーブルであるため、 and を組み合わせStartIPてEndIP、それをキーとして使用し、を値として使用して、これをすべてRedisやMemcachedGeolocationなどのキーと値のストアから読み取ることが賢明な場合があります。NoSQL/テーブルレス データ ストアは、何百万ものデータ ポイントに対して読み取りを行う、このような用途向けに設計されています。

編集:いくつかのコメントを読んだ後、別の解決策は MapReduce のようなものを介して検索を並列化することであることがわかりました。Map ステップで一連の IP (例: Thread1: 1-10、Thread2: 11-20 など) をクエリするスレッドを割り当て、Reduce ステップで断片化されたクエリを 1 つの結果に削減するスレッドを割り当てます。これをスクリプト化するには、明らかに別のプログラミング言語が必要ですが、同時実行性は全体的なロード時間を短縮するのに役立ちますが、欠点はデータベースへの複数のクエリになります。

于 2012-08-21T20:46:44.357 に答える
1

これに関する意味のある入力のために、クエリとクエリプランを提供する必要があります。例えば：

explain select hits.ip, locations.loc
 from hits left outer join locations
   on (hits.ip >= locations.start and hits.ip <= locations.stop);
                                  QUERY PLAN                                   
-------------------------------------------------------------------------------
 Nested Loop Left Join  (cost=0.00..245.06 rows=2400 width=36)
   Join Filter: ((hits.ip >= locations.start) AND (hits.ip <= locations.stop))
   ->  Seq Scan on hits  (cost=0.00..34.00 rows=2400 width=4)
   ->  Materialize  (cost=0.00..1.07 rows=5 width=40)
         ->  Seq Scan on locations  (cost=0.00..1.05 rows=5 width=40)
(5 rows)

他の回答の1つが示唆するように、インデックスに位置データを追加したいかどうかわかりません。これは無駄なデータを追加するだけで、行を検索するのには適していません。

インデックスのみのスキャンをサポートする pg バージョン (9.2、まだベータ版) を使用している場合でも、行ごとに 1 つの追加のタプル ルックアップを使用して、より小さな無駄のないインデックスを使用すると、おそらくより高速な結果が得られます。

于 2012-08-21T21:26:09.030 に答える