Return-Path: Delivered-To: apmail-couchdb-user-archive@www.apache.org Received: (qmail 83820 invoked from network); 21 Dec 2008 08:13:01 -0000 Received: from hermes.apache.org (HELO mail.apache.org) (140.211.11.2) by minotaur.apache.org with SMTP; 21 Dec 2008 08:13:01 -0000 Received: (qmail 8816 invoked by uid 500); 21 Dec 2008 08:13:00 -0000 Delivered-To: apmail-couchdb-user-archive@couchdb.apache.org Received: (qmail 8770 invoked by uid 500); 21 Dec 2008 08:13:00 -0000 Mailing-List: contact user-help@couchdb.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: user@couchdb.apache.org Delivered-To: mailing list user@couchdb.apache.org Received: (qmail 8740 invoked by uid 99); 21 Dec 2008 08:13:00 -0000 Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136) by apache.org (qpsmtpd/0.29) with ESMTP; Sun, 21 Dec 2008 00:13:00 -0800 X-ASF-Spam-Status: No, hits=-0.0 required=10.0 tests=SPF_PASS X-Spam-Check-By: apache.org Received-SPF: pass (athena.apache.org: domain of jchris@gmail.com designates 74.125.46.30 as permitted sender) Received: from [74.125.46.30] (HELO yw-out-2324.google.com) (74.125.46.30) by apache.org (qpsmtpd/0.29) with ESMTP; Sun, 21 Dec 2008 08:12:52 +0000 Received: by yw-out-2324.google.com with SMTP id 3so534200ywj.5 for ; Sun, 21 Dec 2008 00:12:31 -0800 (PST) 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:in-reply-to:mime-version:content-type :content-transfer-encoding:content-disposition:references; bh=9tQLaXX9er+YoR+uGaMFevYcOmHXAFyfXo67wEXcBxg=; b=hbzvt6NwRIJcEMHo4h/eDpJulI5MTSUqE6hYEXJZjXpuLdMS99GSmsEcCm+mKWQuA2 MlPvnbTgMcAH8mMb728cw1TYI4J0rbWrqw/PXurjTbq+EKAFODEmArjhoZowfcY6sBt1 gFQe47wG/lkjDeBrnXuCHAVjPYNZ1TxMDOiQ4= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:to:subject:in-reply-to:mime-version :content-type:content-transfer-encoding:content-disposition :references; b=iA5zVdrF3lpIzBnQTh2AKYS0029snbCLsN0stfteB5C2xI1tsepW2NKOWagXamhYcD h4ctk4CHorkggNmvlUDUZ4BhKhIw8IUnQUSw8YHNy4L64hSkLDVFrTrfI2x8vjKYayVw e20q6ss2YHa7z7bThQB1D8bz0X//LZ9NCj/Gc= Received: by 10.64.201.16 with SMTP id y16mr4002215qbf.82.1229847151069; Sun, 21 Dec 2008 00:12:31 -0800 (PST) Received: by 10.64.101.8 with HTTP; Sun, 21 Dec 2008 00:12:30 -0800 (PST) Message-ID: Date: Sun, 21 Dec 2008 00:12:31 -0800 From: "Chris Anderson" To: user@couchdb.apache.org Subject: Re: slow views In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <4c69d7170812202004v5d3738b4x667201b0181e451f@mail.gmail.com> <4c69d7170812202020y7054733at9d9c51465412ca44@mail.gmail.com> X-Virus-Checked: Checked by ClamAV on apache.org On Sat, Dec 20, 2008 at 8:50 PM, Antony Blakey wrote: > > On 21/12/2008, at 3:15 PM, Paul Davis wrote: > >> On Sat, Dec 20, 2008 at 11:32 PM, Antony Blakey >> wrote: >>> >>> On 21/12/2008, at 2:54 PM, Paul Davis wrote: >>> >>>> View update times should be linear in terms of *new* records. >>> >>> Well, with a factor to deal with the reduction, which isn't O(n). >>> >> >> Kinda. I'm pretty sure they're still O(N), just not as pre calculated >> as one might expect. > > I would have thought + a tiny O(log M) where M is determined by the grouping > size of the partial reductions. I think there's at least a linear cost associated with the number of groups in the final reduction. eg. a group=true result requires N as many as there are unique keys. If your range encompasses 5 groups, then you'd require 5 final reductions to be run. Requesting the same range with group=false, I'd expect a substantial speedup. If it's less than a linear relation to the number of groups, I'd be happy. -- Chris Anderson http://jchris.mfdz.com