Complexity of DB Operations in PostgreSQL?

Question

Does anyone have a guide to computing the complexity of various operations in postgresql? Such as selects, joins (in the from vs the where), group, aggregation, cartesian products, etc?

I am looking for something in Big O notation.

Answer 1

What you are asking for doesn't and can't exist, because there isn't a 1:1 relationship between type of operation and complexity. Consider a basic select operation, for example. This could map into various kinds of plans and the planner makes decisions regarding estimated complexity of each plan. For example, suppose we:

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)

Now the planner in this case decides (correctly) that using an index is needless complexity. So consequently even a simple query has multiple possibilities and PostgreSQL tries to choose the least complex plan given what it knows.

The one exception is that commit and rollback both have O(1) complexity.

Answer 2

The answer depends on the quality of the index. Gerenarally with the binary block size. If no index, search is O(n). If index, search is O(log n). You can also set which datastructure you want to use in which index. For instance, B-tree as the method of the partial index here and about the complexities of different operations here for the binary operations:

        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)

Doing simple testing. The underlying block size affects the logarithmic speed, about which I have a thread What is the block size of Partial Index with B-tree? because log_b n is the how the logarihmic things are done, which makes the operations faster than the default binary ones but possibly having some costs with the space (not sure how to present it there):

        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)