155645 - Search performance is bad due to matching all rules for _all_ messages

Status: RESOLVED DUPLICATE of bug 154867

(SeaMonkey :: MailNews: Message Display, defect)

Description

[Lasse Kärkkäinen]

When searching with one rule ("Subject contains ITInfo") in a large folder (with
5092 messages in it), the search is quick and returns few results only (ITInfo
newsletters, 44 messages).

After adding another rule ("Body contains Mozilla") the search took extremely
long (and the UI was unresponsive, so it couldn't be terminated, but this is
another issue and should go to another bug). "Match all of the following" was used.

The obvious reason for this taking so long is searching message _bodies_ for
"Mozilla".

What should be done is FIRST searching headers (for "Subject contains ITInfo"),
then searching bodies of those 44 messages for "Mozilla". This would be a LOT
faster.

Implementation for this could be sorting search rules by estimated speed
("Subject is foo" is faster than "Subject contains foo", which still is faster
than "Body contains foo"), then searching with one rule at a time, within the
results of the previous rule.

Comment 1

[(not reading, please use [e-mail] instead)]

mass re-assign.

Comment 2

[reb]

It's called short-circuiting, most programming languages support
it.  Using multiple conditions, as soon as the outcome is known
(match or not matched) stop checking the rest of the conditions.
Match any is OR, match all is AND.  For "a AND b AND c", if "a"
is false, waste of time to check the rest.  For "a OR b or C",
if "a" is true (matched), waste of time to check the rest.

First pass at ordering the checks is to first do those that can
be satisfied by the index itself (so this covers addressing,
date/age, subject; this is one primary reason for maintaining an
index to start with).  But even implement something more basic
sooner: so long as short-circuiting works, even if conditions are
evaluated in exactly the order the user adds them on the form,
then the user can be aware of it, and add the indexable conditions
first, and always simply add any Body conditions last.  (ie: Most
programming languages won't reorder the conditions you write, and
this is important in a programming language, but not here, when the
conditions themselves have side-effects or early conditions guard
the latter ones).

FYI: Same lack of short-circuiting problem is there in Netscape 4.x.

I'd suggest an alternate title for this like:
Search match all/any speed-up thru short-circuiting by order or index.

Comment 3

[Jesse Ruderman]

Dup of bug 154867.

Comment 4

[Jesse Ruderman]

*** This bug has been marked as a duplicate of 154867 ***