Skip site navigation (1) Skip section navigation (2)

Re: "Big O" notation for postgres?

From: Richard Huxton <dev(at)archonet(dot)com>
To: "Jonah H(dot) Harris" <jonah(dot)harris(at)gmail(dot)com>
Cc: "H(dot) Hall" <hhall1001(at)reedyriver(dot)com>, pgsql-performance(at)postgresql(dot)org
Subject: Re: "Big O" notation for postgres?
Date: 2008-05-21 14:39:54
Message-ID: 4834343A.8020607@archonet.com (view raw or flat)
Thread:
Lists: pgsql-performance
Jonah H. Harris wrote:
> On Wed, May 21, 2008 at 10:10 AM, H. Hall <hhall1001(at)reedyriver(dot)com> wrote:
>> Does anyone know if there is a source that provides "Big O" notation for
>> postgres's aggregate functions and operations?  For example is count(*) =
>> O(1) or O(n)?
> 
> I don't know of any document containing the complexity of each
> aggregate, but it's sometimes left as a comment in the souce code.

Recent max() and min() can be O(n) or O(1) depending on the where-clause 
and presence of an index too, just to muddy the waters.

-- 
   Richard Huxton
   Archonet Ltd

In response to

Responses

pgsql-performance by date

Next:From: PFCDate: 2008-05-21 16:18:27
Subject: Re: Posible planner improvement?
Previous:From: Jonah H. HarrisDate: 2008-05-21 14:28:59
Subject: Re: "Big O" notation for postgres?

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group