From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.emacs.gnus.general/42516 Path: main.gmane.org!not-for-mail From: Karl Kleinpaste Newsgroups: gmane.emacs.gnus.general Subject: Re: db-backed mail back end Date: Thu, 24 Jan 2002 06:58:48 -0500 Sender: owner-ding@hpc.uh.edu Message-ID: References: NNTP-Posting-Host: coloc-standby.netfonds.no Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: main.gmane.org 1035177747 12246 80.91.224.250 (21 Oct 2002 05:22:27 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Mon, 21 Oct 2002 05:22:27 +0000 (UTC) Return-Path: Original-Received: (qmail 6884 invoked from network); 24 Jan 2002 11:59:32 -0000 Original-Received: from malifon.math.uh.edu (mail@129.7.128.13) by mastaler.com with SMTP; 24 Jan 2002 11:59:32 -0000 Original-Received: from sina.hpc.uh.edu ([129.7.128.10] ident=lists) by malifon.math.uh.edu with esmtp (Exim 3.20 #1) id 16TiX7-0004KS-00; Thu, 24 Jan 2002 05:59:09 -0600 Original-Received: by sina.hpc.uh.edu (TLB v0.09a (1.20 tibbs 1996/10/09 22:03:07)); Thu, 24 Jan 2002 05:59:04 -0600 (CST) Original-Received: from sclp3.sclp.com (qmailr@sclp3.sclp.com [209.196.61.66]) by sina.hpc.uh.edu (8.9.3/8.9.3) with SMTP id FAA15367 for ; Thu, 24 Jan 2002 05:58:52 -0600 (CST) Original-Received: (qmail 6877 invoked by alias); 24 Jan 2002 11:58:52 -0000 Original-Received: (qmail 6872 invoked from network); 24 Jan 2002 11:58:50 -0000 Original-Received: from mesquite.slip.cs.cmu.edu (HELO cinnamon.vanillaknot.com) (128.2.207.11) by gnus.org with SMTP; 24 Jan 2002 11:58:50 -0000 Original-Received: (from karl@localhost) by cinnamon.vanillaknot.com (8.11.6/8.11.6) id g0OBwnw07457; Thu, 24 Jan 2002 06:58:49 -0500 Original-To: ding@gnus.org X-Face: "8-CgoYhiD_O!#(F%E=..0>QA_#WDy+]_XoAr)L]`-zjAc\d+nsFXq`=v_# =pVh#sP*K~j,0k9N}`E7jX"5+U?4/UIF1EE X-Face: "5(T0tZd{6}pd~YzBG8O/*EW,.]6]@`m^e;fv65W^Y&=d"M\1H}>T~4_.kcDD.O~y3k)a6 hR;Nmi>9|>Nm${2IpM0^RcUEa\jcq?KOP)C&~x51l~zCHTulL^_T|u0I^kB'z@]{`2YjQu In-Reply-To: (Simon Josefsson's message of "Thu, 24 Jan 2002 12:32:38 +0100 (CET)") Original-Lines: 18 User-Agent: Gnus/5.090006 (Oort Gnus v0.06) XEmacs/21.4 (Common Lisp, i686-pc-linux) Precedence: list X-Majordomo: 1.94.jlt7 Xref: main.gmane.org gmane.emacs.gnus.general:42516 X-Report-Spam: http://spam.gmane.org/gmane.emacs.gnus.general:42516 Simon Josefsson writes: > NNML scales linearly with the number of messages in the group, does > it not? Gnus definitely doesn't scale linearly, so redesigning > something to get support for large mail/news backends should go into > Gnus, I think. I have been wondering about this since this discussion started. The slowness of entering a large group of 10K messages, or 100K, has very little to do with getting at either the overview data or the message files. It has to do with threading, scoring, and sorting. I don't know what Gnus' threading algorithm is, but I suspect its performance is at least as poor as O(n log n) and may even be as bad as O(n^2). It is not clear to me that it is possible to do better than O(n log n) in the first place, though I haven't contemplated the matter very long. These are not problems that are addressed at all by the manner in which articles and indices (overviews or otherwise) are stored, but rather in how threading is computed, and how scoring is managed.