Received: from localhost (unknown [200.46.204.183]) by developer.postgresql.org (Postfix) with ESMTP id 6C9502E0056 for ; Wed, 21 May 2008 11:29:18 -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 42319-04 for ; Wed, 21 May 2008 11:28:59 -0300 (ADT) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from ti-out-0910.google.com (ti-out-0910.google.com [209.85.142.184]) by developer.postgresql.org (Postfix) with ESMTP id BDC052E002C for ; Wed, 21 May 2008 11:29:03 -0300 (ADT) Received: by ti-out-0910.google.com with SMTP id y8so1706470tia.5 for ; Wed, 21 May 2008 07:29:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; bh=8prZC7IYEPMaAP4AgWTElsT1oOnBA+/bpZvRr65csqA=; b=M4RfU4qSKemnWl0FYWDgxcPQ9TrQa/VfZKCLsc9IyjrO4SQrvmwY3kXTofNEBpZ1fWwxKiQlk0r/E11/IOjsZ3uKrqCD/taQMTTwNkEsH+fyrxvUDTYXdpKCzkfG3Ny49RAvQe9aaKQJTTYGc5jn7fFf3HQgtk02y/ToqNzo9hk= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=BhLsd5E/ONQHCus8QWo1vRiOFGl5mSLvXKfQkvp+UblNDvbA71qI5ca5j2BjjxQO4XWZ8PMEiouwe4jULpDAS2kOrz4ak5NrQX5HoEQp4oxWpk8c4L5WoeDGXBGZmKFpLh74VWT2bKWRYbqhlb+OYByvjX/aBWFUtTSSFIxB/qc= Received: by 10.150.84.41 with SMTP id h41mr288038ybb.218.1211380140041; Wed, 21 May 2008 07:29:00 -0700 (PDT) Received: by 10.150.57.2 with HTTP; Wed, 21 May 2008 07:28:59 -0700 (PDT) Message-ID: <36e682920805210728p4fa6c12ft592b1045cbae9dfd@mail.gmail.com> Date: Wed, 21 May 2008 10:28:59 -0400 From: "Jonah H. Harris" To: "H. Hall" Subject: Re: "Big O" notation for postgres? Cc: pgsql-performance@postgresql.org In-Reply-To: <48342D6D.1020506@reedyriver.com> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <48342D6D.1020506@reedyriver.com> X-Virus-Scanned: Maia Mailguard 1.0.1 X-Archive-Number: 200805/295 X-Sequence-Number: 30263 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. IIRC, COUNT (non-distinct) is currently O(n), where n also includes evaluation of tuples not represented in the final count (due to Postgres' MVCC design). -- Jonah H. Harris, Sr. Software Architect | phone: 732.331.1324 EnterpriseDB Corporation | fax: 732.331.1301 499 Thornall Street, 2nd Floor | jonah.harris@enterprisedb.com Edison, NJ 08837 | http://www.enterprisedb.com/