8

postgresql でのさまざまな操作の複雑さを計算するためのガイドを持っている人はいますか? 選択、結合 (from と where)、グループ、集計、デカルト積など?

Big O表記のものを探しています。

4

2 に答える 2

10

操作の種類と複雑さの間に 1 対 1 の関係がないため、あなたが求めているものは存在せず、存在しません。たとえば、基本的な選択操作を考えてみましょう。これはさまざまな種類の計画にマッピングされる可能性があり、プランナーは各計画の推定複雑性に関する決定を下します。たとえば、次のようにします。

CREATE TABLE my_index_test (id int primary key); -- creates an index too!
EXPLAIN ANALYZE SELECT * FROM my_index_test where id = 0;

                                            QUERY PLAN                      

--------------------------------------------------------------------------------
---------------------------
Seq Scan on my_index_test  (cost=0.00..34.00 rows=2400 width=4) 
    (actual time=0.003..0.003 rows=0 loops=1)
  Total runtime: 0.045 ms
 (2 rows)

この場合のプランナーは、インデックスを使用することは不必要に複雑であると (正しく) 判断します。したがって、簡単なクエリでも複数の可能性があり、PostgreSQL は、知っていることから最も複雑でないプランを選択しようとします。

1 つの例外は、コミットとロールバックの両方が O(1) の複雑さを持つことです。

于 2012-10-02T03:32:20.963 に答える
5

答えは、インデックスの品質によって異なります。通常、バイナリ ブロック サイズを使用します。インデックスがない場合、検索はO(n)です。インデックスの場合、検索はO(log n)です。どのデータ構造をどのインデックスで使用するかを設定することもできます。たとえば、ここでは部分インデックスのメソッドとして B ツリーを使用し、バイナリ操作のさまざまな操作の複雑さについては次のように説明します。

        Average     Worst case
Space   O(n)        O(n)
Search  O(log n)    O(log n)
Insert  O(log n)    O(log n)
Delete  O(log n)    O(log n)

簡単なテストを行っています。基礎となるブロック サイズは、対数速度に影響します。これについてはスレッドがあります。B ツリーを使用した部分インデックスのブロック サイズはどれくらいですか? log_b n対数的な処理が行われるため、デフォルトのバイナリ処理よりも処理が高速になりますが、スペースに多少のコストがかかる可能性があります (そこに表示する方法がわからない) 。

        Average     Worst case
Space   O(n)        O(n)         % not sure about this here
Search  O(log_b n)  O(log_b n)
Insert  O(log_b n)  O(log_b n)
Delete  O(log_b n)  O(log_b n)
于 2015-08-19T20:09:35.560 に答える