11

私はHadoop：TomWhiteによる決定的なガイドを読んでいます。13.6章「HBasevsRDMS」で、データが多い場合、最近の10個のアイテムを取得するような単純なクエリでも非常にコストがかかり、PythonとPL/SQLを使用してそれらを書き直す必要があると述べました。

彼は例として次のクエリを示します。

SELECT id, stamp, type FROM streams 
WHERE type IN ('type1','type2','type3','type4',...,'typeN')
ORDER BY stamp DESC LIMIT 10 OFFSET 0;

そして、次のように述べています。「RDBMSクエリプランナーは、このクエリを次のように扱います。

MERGE (
  SELECT id, stamp, type FROM streams
    WHERE type = 'type1' ORDER BY stamp DESC,
  ...,
  SELECT id, stamp, type FROM streams
    WHERE type = 'typeK' ORDER BY stamp DESC
) ORDER BY stamp DESC LIMIT 10 OFFSET 0;

ここでの問題は、上位10個のIDのみを追跡していることですが、クエリプランナーは実際にはマージ全体を具体化し、最後に制限します。....実際には、ヒープソートを実行するカスタムPL/Pythonスクリプトを作成するところまで行きました。...ほとんどすべての場合、これはネイティブSQL実装およびクエリプランナーの戦略を上回りました...

期待されるパフォーマンスと実験結果

このような単純なクエリを正しく実行するには、pl/pythonを記述しなければならないような問題を引き起こすデータセットを想像することはできませんでした。だから私はこの問題についてしばらく遊んで、次の観察を思いついた：

このようなクエリのパフォーマンスは、O（KlogN）によって制限されます。それは次のように何かに翻訳することができるので：

SELECT * FROM (
  SELECT id, stamp, type FROM streams
    WHERE type = 'type1' ORDER BY stamp DESC LIMIT 10,
  UNION
  ...,
  SELECT id, stamp, type FROM streams
    WHERE type = 'typeK' ORDER BY stamp DESC LIMIT 10
) t ORDER BY stamp DESC LIMIT 10;

（各クエリの「LIMIT10」に注意してください。ところで、ユニオンを制限して順序付けすることはできませんが、読みやすくするためにラッピング選択を削除しました）

各サブクエリは、インデックスO（logN）で正しい位置を見つけ、10個のアイテムを返すのと同じ速さで実行する必要があります。そのK回繰り返すと、O（KlogN）が得られます。

また、クエリプランナーがひどくて最初のクエリを最適化できない場合でも、pl / pythonで何も記述せずに、いつでもそれをユニオン付きのクエリに変換して、目的のパフォーマンスを得ることができます。

計算を再確認するために、9,000,000のテストレコードで満たされた1つのpostgresqlの上でクエリを実行しました。結果は、両方のクエリが最初のクエリで100ミリ秒、2番目のクエリ（ユニオンのあるクエリ）で300ミリ秒と非常に高速であるという私の期待を裏付けました。

したがって、クエリが9,000,000（logn = 23）のレコードに対して100msで実行される場合、9,000,000,000（logn = 33）のレコードに対しては140msで実行されるはずです。

質問

  • 上記の推論に欠陥がありますか？
  • 上記のようなクエリをpl/pythonで書き直す必要があるデータセットを想像できますか？
  • そのようなクエリがO（K log n）で機能しない状況はありますか？
4

4 に答える 4

6

RDMBSクエリプランナーがクエリに対してそのソリューションを採用しているという彼らの主張は、少なくともPostgresql 9.0については正しくありません。また、他のプラットフォームについても想像する必要があります。同様のクエリで簡単なテストを行いました。

explain select * from client_attribute where client_attribute_type_code in ('UAG', 'RFR', 'IPA', 'FVD') order by client_attribute_id desc limit 10;

                                                      QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..0.93 rows=10 width=85)
   ->  Index Scan Backward using client_attribute_pkey on client_attribute  (cost=0.00..15516.47 rows=167234 width=85)
         Filter: (client_attribute_type_code = ANY ('{UAG,RFR,IPA,FVD}'::bpchar[]))
(3 rows)

ここでは、client_attribute_idにインデックスが付けられているため、必要に応じて正確に実行されます。インデックスをさかのぼってフィルターを適用し、出力が制限に達すると停止します。

順序列にインデックスが付けられていない場合は、テーブルのスキャンと並べ替えが必要ですが、テーブルのスキャンは1回だけです。

explain analyze select * from client_attribute where client_attribute_type_code in ('UAG', 'RFR', 'IPA', 'FVD') order by updated desc limit 10;

                                                              QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=13647.00..13647.03 rows=10 width=85) (actual time=180.961..180.964 rows=10 loops=1)
   ->  Sort  (cost=13647.00..14065.09 rows=167234 width=85) (actual time=180.960..180.961 rows=10 loops=1)
         Sort Key: updated
         Sort Method:  top-N heapsort  Memory: 26kB
         ->  Seq Scan on client_attribute  (cost=0.00..10033.14 rows=167234 width=85) (actual time=0.010..106.791 rows=208325 loops=1)
               Filter: (client_attribute_type_code = ANY ('{UAG,RFR,IPA,FVD}'::bpchar[]))

これは、ヒープソートを使用して、シーケンシャルスキャンの過程で上位10の結果を維持します。これは、彼らが自分で作成したソリューションとまったく同じように聞こえます。

于 2010-11-27T16:36:04.183 に答える
4

TomWhiteがリレーショナルデータベースが「悪い」と言っているとは思いません。これらは、非リレーショナル、非セットベースのデータには最適ではありません。

ディープオブジェクトグラフがリレーショナルデータベースに適していないことは、長い間よく知られています。これらは通常、ジオメトリデータのCAD表現などの問題で見られます。この場合、アセンブリはパーツのアセンブリのアセンブリで構成されます。実際、参照チェーンは非常に長いです。

オブジェクトとグラフのデータベースは、私が90年代の初めにそれらを知っていたので、その種の問題の解決策でした。

リレーショナルデータベースは、リレーショナルのセットベースのデータに最適です。ただし、すべてのデータがそのカテゴリに分類されるわけではありません。そのため、NoSQLはマインドシェアを獲得しています。

それがあなたが引用している例が言っていることだと思います。

于 2010-11-26T23:11:53.820 に答える
1

RDBMSは、あなたが考えもしなかったクエリのためのものです。必要なものが正確に決まったら、最適なソリューションを適用できます。

于 2010-11-26T23:31:51.003 に答える
1

SQLまたはNoSQLのいずれかを使用すると、クエリを間違った方法で設計するとパフォーマンスが低下します。

where句にタイムスタンプのチェックを追加することでその例を修正します。大量のデータがある場合は、最新の10エントリが直前のものであると推測できます。それでは、先月のすべてを読み取って並べ替えてみてください。

デフォルトではIDでしかレコードを見つけることができないため、必要なレコードを見つけるにはデータセット全体をロードする必要があり、さまざまなセカンダリを設定する機能を無視する必要があると主張することで、同じ例を簡単に考案してNoSQLの見栄えを悪くすることができます。重要なクエリのSQLパフォーマンスよりも優れた/customインデックス。

于 2010-11-27T00:28:09.540 に答える