Geek asks and answers

Complexity of database operations in PostgreSQL?

Does anyone have a guide on calculating the complexity of various operations in postgresql? For example, it selects, combines (in the “against” section), group, aggregation, Cartesian products, etc.

I am looking for something in Big O notation.

+5
source share
2 answers

What you are asking for does not exist and cannot exist, because there is no 1: 1 relationship between the type of operation and complexity. Consider, for example, the basic selection operation. This may be related to different plans, and the planner makes decisions regarding the assessment of the complexity of each plan. For example, suppose that:

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 , , .

, O (1).

+7

. Gerenarally . , O(n). , O(log n). , , . , B-tree :

        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)

. , Partial Index B-tree?, 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)
+3

More articles:


All Articles