Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Complexity of DB Operations in PostgreSQL?

Tags:

postgresql

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.

like image 632
petFoo Avatar asked Oct 02 '12 02:10

petFoo


2 Answers

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.

like image 61
Chris Travers Avatar answered Oct 14 '22 08:10

Chris Travers


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)
like image 27
Léo Léopold Hertz 준영 Avatar answered Oct 14 '22 10:10

Léo Léopold Hertz 준영