postgresql - PostgreSQL 中数据库操作的复杂性？

Question

有没有人有一个指南来计算 postgresql 中各种操作的复杂性？例如选择、连接（在 from 与 where 中）、分组、聚合、笛卡尔积等？

我正在寻找大 O 表示法的东西。

Answer 1

您所要求的不存在也不可能存在，因为操作类型和复杂性之间没有 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 会根据它所知道的情况尝试选择最不复杂的计划。

一个例外是提交和回滚都具有 O(1) 复杂度。

Answer 2

答案取决于索引的质量。通常具有二进制块大小。如果没有索引，搜索是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)

做简单的测试。底层块大小影响对数速度，关于它我有一个线程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)