Received: from localhost (unknown [200.46.204.183]) by developer.postgresql.org (Postfix) with ESMTP id 2F8A72E004E for ; Wed, 21 May 2008 11:40:02 -0300 (ADT) Received: from developer.postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.183]) (amavisd-maia, port 10024) with ESMTP id 48919-01 for ; Wed, 21 May 2008 11:39:53 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from pih-relay06.plus.net (pih-relay06.plus.net [212.159.14.133]) by developer.postgresql.org (Postfix) with ESMTP id 14FB82E002C for ; Wed, 21 May 2008 11:39:59 -0300 (ADT) Received: from [84.51.143.99] (helo=server3.office.archonet.com) by pih-relay06.plus.net with esmtp (Exim) id 1JypTu-0001AD-CH; Wed, 21 May 2008 15:39:54 +0100 Received: from [192.168.1.36] (dell36.office.archonet.com [192.168.1.36]) by server3.office.archonet.com (Postfix) with ESMTP id F249A274063; Wed, 21 May 2008 15:39:53 +0100 (BST) Message-ID: <4834343A.8020607@archonet.com> Date: Wed, 21 May 2008 15:39:54 +0100 From: Richard Huxton User-Agent: Thunderbird 2.0.0.14 (X11/20080421) MIME-Version: 1.0 To: "Jonah H. Harris" CC: "H. Hall" , pgsql-performance@postgresql.org Subject: Re: "Big O" notation for postgres? References: <48342D6D.1020506@reedyriver.com> <36e682920805210728p4fa6c12ft592b1045cbae9dfd@mail.gmail.com> In-Reply-To: <36e682920805210728p4fa6c12ft592b1045cbae9dfd@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Plusnet-Relay: 1e0b436d546c02e9bfea3e28df6ace98 X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200805/296 X-Sequence-Number: 30264 Jonah H. Harris wrote: > On Wed, May 21, 2008 at 10:10 AM, H. Hall 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