1 Return-Path: <amdragon@mit.edu>
\r
2 X-Original-To: notmuch@notmuchmail.org
\r
3 Delivered-To: notmuch@notmuchmail.org
\r
4 Received: from localhost (localhost [127.0.0.1])
\r
5 by olra.theworths.org (Postfix) with ESMTP id B0F4E431FB6
\r
6 for <notmuch@notmuchmail.org>; Sat, 28 Jan 2012 10:34:28 -0800 (PST)
\r
7 X-Virus-Scanned: Debian amavisd-new at olra.theworths.org
\r
11 X-Spam-Status: No, score=-0.7 tagged_above=-999 required=5
\r
12 tests=[RCVD_IN_DNSWL_LOW=-0.7] autolearn=disabled
\r
13 Received: from olra.theworths.org ([127.0.0.1])
\r
14 by localhost (olra.theworths.org [127.0.0.1]) (amavisd-new, port 10024)
\r
15 with ESMTP id oESKNv6pQEQY for <notmuch@notmuchmail.org>;
\r
16 Sat, 28 Jan 2012 10:34:27 -0800 (PST)
\r
17 Received: from dmz-mailsec-scanner-6.mit.edu (DMZ-MAILSEC-SCANNER-6.MIT.EDU
\r
19 by olra.theworths.org (Postfix) with ESMTP id AA998431FAE
\r
20 for <notmuch@notmuchmail.org>; Sat, 28 Jan 2012 10:34:27 -0800 (PST)
\r
21 X-AuditID: 12074423-b7f9c6d0000008c3-a4-4f243fb20c29
\r
22 Received: from mailhub-auth-3.mit.edu ( [18.9.21.43])
\r
23 by dmz-mailsec-scanner-6.mit.edu (Symantec Messaging Gateway) with SMTP
\r
24 id B6.67.02243.2BF342F4; Sat, 28 Jan 2012 13:34:26 -0500 (EST)
\r
25 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103])
\r
26 by mailhub-auth-3.mit.edu (8.13.8/8.9.2) with ESMTP id q0SIYPMe026548;
\r
27 Sat, 28 Jan 2012 13:34:26 -0500
\r
28 Received: from awakening.csail.mit.edu (awakening.csail.mit.edu [18.26.4.91])
\r
29 (authenticated bits=0)
\r
30 (User authenticated as amdragon@ATHENA.MIT.EDU)
\r
31 by outgoing.mit.edu (8.13.6/8.12.4) with ESMTP id q0SIYOcQ001042
\r
32 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NOT);
\r
33 Sat, 28 Jan 2012 13:34:25 -0500 (EST)
\r
34 Received: from amthrax by awakening.csail.mit.edu with local (Exim 4.77)
\r
35 (envelope-from <amdragon@mit.edu>)
\r
36 id 1RrD5o-0006MC-8C; Sat, 28 Jan 2012 13:33:40 -0500
\r
37 Date: Sat, 28 Jan 2012 13:33:40 -0500
\r
38 From: Austin Clements <amdragon@MIT.EDU>
\r
39 To: Mark Walters <markwalters1009@gmail.com>
\r
40 Subject: Re: [RFC PATCH 2/4] Add NOTMUCH_MESSAGE_FLAG_EXCLUDED flag
\r
41 Message-ID: <20120128183340.GD17991@mit.edu>
\r
42 References: <20120124011609.GX16740@mit.edu>
\r
43 <1327367923-18228-2-git-send-email-markwalters1009@gmail.com>
\r
44 <20120124024521.GY16740@mit.edu> <874nvg6qxn.fsf@qmul.ac.uk>
\r
46 Content-Type: text/plain; charset=us-ascii
\r
47 Content-Disposition: inline
\r
48 In-Reply-To: <874nvg6qxn.fsf@qmul.ac.uk>
\r
49 User-Agent: Mutt/1.5.21 (2010-09-15)
\r
50 X-Brightmail-Tracker:
\r
51 H4sIAAAAAAAAA+NgFmphleLIzCtJLcpLzFFi42IR4hTV1t1kr+JvMHu1mMXquTwW12/OZHZg
\r
52 8tg56y67x7NVt5gDmKK4bFJSczLLUov07RK4Mo7feclSsNmwYsXBF8wNjLfUuhg5OSQETCTm
\r
53 da9hg7DFJC7cWw9kc3EICexjlJj58wc7hLOBUWLPow1MEM5JJokHW/ezQjhLGCVuTDvFAtLP
\r
54 IqAq8eDbbFYQm01AQ2Lb/uWMILaIgI7E7UML2EFsZgFpiW+/m5lAbGEBZ4nnTV/B6nmBatbc
\r
55 WAC1ey2jxKenP9ghEoISJ2c+YYFo1pK48e8lUDMH2KDl/zhAwpxAu14uXgg2R1RARWLKyW1s
\r
56 ExiFZiHpnoWkexZC9wJG5lWMsim5Vbq5iZk5xanJusXJiXl5qUW6Znq5mSV6qSmlmxhBgc3u
\r
57 oryD8c9BpUOMAhyMSjy8F14p+QuxJpYVV+YeYpTkYFIS5T1rq+IvxJeUn1KZkVicEV9UmpNa
\r
58 fIhRgoNZSYT3gxxQjjclsbIqtSgfJiXNwaIkzquh9c5PSCA9sSQ1OzW1ILUIJivDwaEkwcsM
\r
59 jGAhwaLU9NSKtMycEoQ0EwcnyHAeoOGyIDW8xQWJucWZ6RD5U4yKUuK8j+2AEgIgiYzSPLhe
\r
60 WOJ5xSgO9Iow7w+QKh5g0oLrfgU0mAlocMRVRZDBJYkIKakGRt51fB84szKa9nGt82NRLlfY
\r
61 3CT0nknN+mIIe/SLlyybeSUO8uq/W8mfr7fWO+7i3nBX7bKS+Vla4v97pzw3aq3Ke39k0aNH
\r
62 XM8Wn9g44Wa8InNrVTHzvt356/ZvkG3km3QhNnjmn7r7qpfWpywKvJrN4nn7hrRuxQVxiR9J
\r
63 p3bE/llYdHbCdiWW4oxEQy3mouJEACnVGSIXAwAA
\r
64 Cc: notmuch@notmuchmail.org
\r
65 X-BeenThere: notmuch@notmuchmail.org
\r
66 X-Mailman-Version: 2.1.13
\r
68 List-Id: "Use and development of the notmuch mail system."
\r
69 <notmuch.notmuchmail.org>
\r
70 List-Unsubscribe: <http://notmuchmail.org/mailman/options/notmuch>,
\r
71 <mailto:notmuch-request@notmuchmail.org?subject=unsubscribe>
\r
72 List-Archive: <http://notmuchmail.org/pipermail/notmuch>
\r
73 List-Post: <mailto:notmuch@notmuchmail.org>
\r
74 List-Help: <mailto:notmuch-request@notmuchmail.org?subject=help>
\r
75 List-Subscribe: <http://notmuchmail.org/mailman/listinfo/notmuch>,
\r
76 <mailto:notmuch-request@notmuchmail.org?subject=subscribe>
\r
77 X-List-Received-Date: Sat, 28 Jan 2012 18:34:28 -0000
\r
79 Quoth Mark Walters on Jan 28 at 10:51 am:
\r
81 > > > exclude_query = _notmuch_exclude_tags (query, final_query);
\r
83 > > > - final_query = Xapian::Query (Xapian::Query::OP_AND_NOT,
\r
84 > > > - final_query, exclude_query);
\r
85 > > > + enquire.set_weighting_scheme (Xapian::BoolWeight());
\r
86 > > > + enquire.set_query (exclude_query);
\r
88 > > > + mset = enquire.get_mset (0, notmuch->xapian_db->get_doccount ());
\r
90 > > > + GArray *excluded_doc_ids = g_array_new (FALSE, FALSE, sizeof (unsigned int));
\r
92 > > > + for (iterator = mset.begin (); iterator != mset.end (); iterator++)
\r
94 > > > + unsigned int doc_id = *iterator;
\r
95 > > > + g_array_append_val (excluded_doc_ids, doc_id);
\r
97 > > > + messages->base.excluded_doc_ids = talloc (query, _notmuch_doc_id_set);
\r
98 > > > + _notmuch_doc_id_set_init (query, messages->base.excluded_doc_ids,
\r
99 > > > + excluded_doc_ids);
\r
101 > > This might be inefficient for message-only queries, since it will
\r
102 > > fetch *all* excluded docids. This highlights a basic difference
\r
103 > > between message and thread search: thread search can return messages
\r
104 > > that don't match the original query and hence needs to know all
\r
105 > > potentially excluded messages, while message search can only return
\r
106 > > messages that match the original query.
\r
108 > I now have some benchmarks (not run enough times to be hugely accurate
\r
109 > so ignore minor differences). The full results are below. The summary
\r
112 > Large-archive = 1 100 000 messages in 290 000 threads (about 10 years of
\r
113 > lkml). I mark 1 000 000 deleted
\r
114 > Small-archive = 70 000 messages in 35 000 threads. 10 000 marked
\r
117 > Doing the initial exclude work on the big collection takes about 0.8s
\r
118 > and on the small collection about 0.01s. So any query to the big
\r
119 > collection takes at least 0.8s longer and this all occurs before any
\r
122 Interesting. Do you know where that time is spent?
\r
124 Also, it might be reasonable to assume that no more than, say, 10% of
\r
125 a person's mail store is excluded, but maybe that depends on how
\r
126 people use this feature.
\r
128 > I then implemented the exclude doing it once for each thread query in
\r
129 > _notmuch_create_thread. Roughly this made any query 50% slower.
\r
131 That's not terrible.
\r
133 > In normal front end use even the 0.8s is not totally unusable, but it is
\r
134 > totally unacceptable in the backend where a user might do something like
\r
136 > for i in ` notmuch search --output=threads from:xxx ` ;
\r
138 > notmuch search --output=messages $i;
\r
141 > to list all messages in all matching threads.
\r
143 > So I think my conclusions are:
\r
145 > (1) message only queries must be done without the full exclude.
\r
146 > (2) thread queries which only match one message should not do the full
\r
148 > (3) it would be nice to switch between the two approaches depending on
\r
149 > size but I don't see how to do that without extra(!) queries
\r
150 > (4) One possible might be do something that say does thirty threads with
\r
151 > the by thread method and then if not finished does the full exclude.
\r
152 > (5) thread-by-thread might be best for Jani's limit-match
\r
153 > id:"1327692900-22926-1-git-send-email-jani@nikula.org"
\r
155 > Obviously, anything setting an exclude flag like this will be slower
\r
156 > (since it is doing more work): the question is are either of these (or a
\r
157 > combination like (4) above) acceptable?
\r
159 Or only mark matched messages as excluded.
\r
161 Here's another idea (actually, a rehash of an old idea). For message
\r
162 search do two queries, the original query and "<original> AND
\r
163 <exclude>", and use this to keep everything in order and mark excluded
\r
164 messages. For thread search, use message search results so it's easy
\r
165 to both sort by unexcluded messages and include fully-excluded
\r
166 threads, but compute the excluded flag (either just for unmatched
\r
167 messages or for all messages) by examining each message's tags
\r
168 directly (which thread_add_message already iterates over, so this is
\r
169 easy and won't add any overhead). If the excluded query is fast,
\r
170 which I think it will be, I think this should get the best of all
\r
171 worlds and be fairly straightforward to implement (no asymmetries
\r
172 between the queries used for message and thread search). It would be
\r
173 easy and worth it to run the excluded query by hand on your test
\r
174 corpus; I suspect it will be much faster than 0.8s because the query
\r
175 already uses "Tmail", which is huge and doesn't seem to slow things
\r
178 > I now have a mostly working implementation from library to
\r
179 > emacs frontend and I do like the overall outcome.
\r
183 > The complete benchmarks are below
\r
189 > LARGE COLLECTION is 1,100,000 messages 290,000 threads 1,000,000 deleted
\r
190 > SMALL COLLECTION is 70,000 messages in 35,000 threads 10,000 deleted
\r
192 > benchmarks: all times in seconds, x/y/z means a query which matches x
\r
193 > threads with y matching messages and z messages in total. Ig or ignore
\r
194 > means with the tag-exclude turned off (i.e. with a query matching the
\r
195 > excluded tag). list all messages is the time for the for loop listed
\r
196 > above giving all message-ids for all messages in any thread matching a
\r
199 > Finally the three columns are master with exclude code disabled,
\r
200 > thread-thread is doing excludes once per thread construction, and
\r
201 > in-advance does all the exclude work in advance as in the patches I posted.
\r
203 > In most cases the benchmark is the average of a lot of runs so the
\r
204 > database should have been as cached as one could hope.
\r
206 > master-(all) thread-thread in-advance
\r
207 > LARGE COLLECTION
\r
208 > show single message 0.016 0.018 0.78
\r
209 > search single message 0.015 0.016 0.78
\r
210 > search single with tag 0.015 0.015 0.009
\r
212 > query ignore 2.9 n/a 3
\r
213 > query 2.9 4.2 3.8
\r
214 > list all messages (ig) 13 n/a 13
\r
215 > list all messages 13 14 12mins
\r
216 > 4754/13000/110000
\r
217 > query ignore 15.9 n/a 17
\r
218 > query 15.9 22 17.6
\r
219 > only messages 1.25 1.26 1.9
\r
221 > query 0.3 0.42 1.1
\r
223 > search '*' 20mins 28mins 21.5mins
\r
228 > list all messages 14.5 16.4 30
\r
229 > single message 0.008 0.008 0.018
\r
231 > search '*' 28 49 32
\r
projects / notmuch-archives.git / blob