* Re: [9fans] rfork(RFPROC) and ffork()
2005-10-30 1:18 ` Paul Lalonde
@ 2005-10-30 6:52 ` Skip Tavakkolian
2005-10-30 10:14 ` Francisco J Ballesteros
` (2 subsequent siblings)
3 siblings, 0 replies; 39+ messages in thread
From: Skip Tavakkolian @ 2005-10-30 6:52 UTC (permalink / raw)
To: 9fans
> I used to keep all my mail this way using MH; it worked well up to
> the point where directories got so full that directory operations
> were taking too long (I remember a nasty n^2 sort in the early days
> of linux). If Plan9's file handling is up to it, I'm in favour of
> this approach. Just remember that it has to work well with 10's of
> thousands of emails in a directory - search is making organization
> obsolete. Heck, some of us didn't manage organization before search
> made it obsolete.
for complex queries, grep's speed is very good; i keep lots of messages
around. regarding searching/organization, if google could integrate
their search engine with a scanner/paper shredder, i would start getting
organized tomorrow.
cpu% time mgrep plalonde MH
I used to keep all my mail this way using MH; it worked well up to
/mail/fs/mbox/1796
0.12u 1.19s 2.87r mgrep plalonde MH
cpu% cat /bin/mgrep
#! /bin/rc
if (test ($#* -lt 1) -o ($#* -gt 2)) {
echo 'usage: mgrep [from] regex'
exit
}
if (test ! -d /mail/fs/mbox) {
echo '/mail/fs/mbox does not exist'
exit
}
if (~ $#* 1) {
grep $1 /mail/fs/mbox/*/body
exit $?
}
for (i in `{grep $1 /mail/fs/mbox/*/from}) {
d=`{basename -d $i}
if (grep $2 $d/body) {
echo $d
}
}
^ permalink raw reply [flat|nested] 39+ messages in thread* Re: [9fans] rfork(RFPROC) and ffork()
2005-10-30 1:18 ` Paul Lalonde
2005-10-30 6:52 ` Skip Tavakkolian
@ 2005-10-30 10:14 ` Francisco J Ballesteros
2005-10-30 15:17 ` Russ Cox
2005-10-31 4:06 ` [9fans] Scaleable mail repositories Lyndon Nerenberg
3 siblings, 0 replies; 39+ messages in thread
From: Francisco J Ballesteros @ 2005-10-30 10:14 UTC (permalink / raw)
To: Fans of the OS Plan 9 from Bell Labs
To avoid huge directories, we "archive" mails. Archiving acutally moves
mails, say, from a whole month, into a mbox.Month directory. After months
using this approach, I´ve seen no problem regarding slow downs on big
directories.
The need for OEXCL can be avoided by storing each mail in a directory named
with a random number. In our case, the dir contains a "text" file
that can be open in
acme/omero to read the mail, and one file (or dir, if it´s a mail) per attach.
Only the real system mbox has to be OEXCL, to prevent races between
incomming mail and mail2fs processes. httlp
If there's interest in trying this, I can move the mail2fs cleanup to a higher
place in my todo list.
hth
On 10/30/05, Paul Lalonde <plalonde@telus.net> wrote:
> I used to keep all my mail this way using MH; it worked well up to
> the point where directories got so full that directory operations
> were taking too long (I remember a nasty n^2 sort in the early days
> of linux). If Plan9's file handling is up to it, I'm in favour of
> this approach. Just remember that it has to work well with 10's of
> thousands of emails in a directory - search is making organization
> obsolete. Heck, some of us didn't manage organization before search
> made it obsolete.
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [9fans] rfork(RFPROC) and ffork()
2005-10-30 1:18 ` Paul Lalonde
2005-10-30 6:52 ` Skip Tavakkolian
2005-10-30 10:14 ` Francisco J Ballesteros
@ 2005-10-30 15:17 ` Russ Cox
2005-10-30 23:00 ` Dave Eckhardt
2005-10-31 4:06 ` [9fans] Scaleable mail repositories Lyndon Nerenberg
3 siblings, 1 reply; 39+ messages in thread
From: Russ Cox @ 2005-10-30 15:17 UTC (permalink / raw)
To: Fans of the OS Plan 9 from Bell Labs
> I used to keep all my mail this way using MH; it worked well up to
> the point where directories got so full that directory operations
> were taking too long (I remember a nasty n^2 sort in the early days
> of linux). If Plan9's file handling is up to it, I'm in favour of
> this approach. Just remember that it has to work well with 10's of
> thousands of emails in a directory - search is making organization
> obsolete. Heck, some of us didn't manage organization before search
> made it obsolete.
Given that the current mbox file format doesn't scale well to tens
of thousands of emails, I'm not worried about the fact that the
file system doesn't either.
Russ
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [9fans] rfork(RFPROC) and ffork()
2005-10-30 15:17 ` Russ Cox
@ 2005-10-30 23:00 ` Dave Eckhardt
2005-10-30 23:14 ` George Michaelson
` (2 more replies)
0 siblings, 3 replies; 39+ messages in thread
From: Dave Eckhardt @ 2005-10-30 23:00 UTC (permalink / raw)
To: Fans of the OS Plan 9 from Bell Labs
> Given that the current mbox file format doesn't scale well to
> tens of thousands of emails, I'm not worried about the fact that
> the file system doesn't either.
The standard hack (did MH ever pick this up?) is to split the
directory, e.g., message 32456 is stored in 32/456 or 3/2/456.
The huge storage/locality win for separating out large attachments
if you have venti-like storage (or want to cache virus-scan results)
may well justify tearing the file apart on nextpart boundaries--my
only concern is that the process be 100% reversible by upas when you
ask. Heck, it could be as simple as "each message is 1 directory,
containing chunks stored one per file, named by integers, and the
original message is formed by cat'ing the chunks in numerical order".
That would let the storing agent decide whether the nextpart boundary
foo belongs in the same chunk as the bits or in its own micro-chunk.
Dave Eckhardt
P.S. At present upas does the >From thing, which isn't reversible.
^ permalink raw reply [flat|nested] 39+ messages in thread* Re: [9fans] rfork(RFPROC) and ffork()
2005-10-30 23:00 ` Dave Eckhardt
@ 2005-10-30 23:14 ` George Michaelson
2005-10-31 2:15 ` erik quanstrom
2005-10-31 4:20 ` Lyndon Nerenberg
2 siblings, 0 replies; 39+ messages in thread
From: George Michaelson @ 2005-10-30 23:14 UTC (permalink / raw)
To: Fans of the OS Plan 9 from Bell Labs
On Sun, 30 Oct 2005 18:00:19 -0500
Dave Eckhardt <davide+p9@cs.cmu.edu> wrote:
> > Given that the current mbox file format doesn't scale well to
> > tens of thousands of emails, I'm not worried about the fact that
> > the file system doesn't either.
>
> The standard hack (did MH ever pick this up?) is to split the
> directory, e.g., message 32456 is stored in 32/456 or 3/2/456.
nmh didn't pick it up. I wish, oh how I wish it had.
-George
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [9fans] rfork(RFPROC) and ffork()
2005-10-30 23:00 ` Dave Eckhardt
2005-10-30 23:14 ` George Michaelson
@ 2005-10-31 2:15 ` erik quanstrom
2005-10-31 2:33 ` geoff
2005-10-31 3:23 ` Skip Tavakkolian
2005-10-31 4:20 ` Lyndon Nerenberg
2 siblings, 2 replies; 39+ messages in thread
From: erik quanstrom @ 2005-10-31 2:15 UTC (permalink / raw)
To: 9fans, Dave Eckhardt
at the risk of repeating myself, this is what i was
trying to get at earlier. i don't think that inventing
"filesystem mime" for performance reasons makes sense.
what percentage of email even has attachments?
never mind a having a strictly reversable function such that
f*(f(email)) → email. in order to preserve the basic difference between
multipart/alternative and multipart/mixed, one would need a
metadata file containing that information. in some sort of new format.
- erik
Dave Eckhardt <davide+p9@cs.cmu.edu> writes
|
| > Given that the current mbox file format doesn't scale well to
| > tens of thousands of emails, I'm not worried about the fact that
| > the file system doesn't either.
|
| The standard hack (did MH ever pick this up?) is to split the
| directory, e.g., message 32456 is stored in 32/456 or 3/2/456.
|
| The huge storage/locality win for separating out large attachments
| if you have venti-like storage (or want to cache virus-scan results)
| may well justify tearing the file apart on nextpart boundaries--my
| only concern is that the process be 100% reversible by upas when you
| ask. Heck, it could be as simple as "each message is 1 directory,
| containing chunks stored one per file, named by integers, and the
| original message is formed by cat'ing the chunks in numerical order".
| That would let the storing agent decide whether the nextpart boundary
| foo belongs in the same chunk as the bits or in its own micro-chunk.
|
| Dave Eckhardt
|
| P.S. At present upas does the >From thing, which isn't reversible.
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [9fans] rfork(RFPROC) and ffork()
2005-10-30 23:00 ` Dave Eckhardt
2005-10-30 23:14 ` George Michaelson
2005-10-31 2:15 ` erik quanstrom
@ 2005-10-31 4:20 ` Lyndon Nerenberg
2005-10-31 21:31 ` Dave Eckhardt
2 siblings, 1 reply; 39+ messages in thread
From: Lyndon Nerenberg @ 2005-10-31 4:20 UTC (permalink / raw)
To: Fans of the OS Plan 9 from Bell Labs
On Oct 30, 2005, at 3:00 PM, Dave Eckhardt wrote:
> Heck, it could be as simple as "each message is 1 directory,
> containing chunks stored one per file, named by integers, and the
> original message is formed by cat'ing the chunks in numerical order".
> That would let the storing agent decide whether the nextpart boundary
> foo belongs in the same chunk as the bits or in its own micro-chunk.
This turns out to be a pessimization. At MD I prototyped this in one
of our servers, and it ended up being noticeably slower than storing
the entire message in one file and maintaining a cache of the MIME
structure.
--lyndon
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [9fans] rfork(RFPROC) and ffork()
2005-10-31 4:20 ` Lyndon Nerenberg
@ 2005-10-31 21:31 ` Dave Eckhardt
0 siblings, 0 replies; 39+ messages in thread
From: Dave Eckhardt @ 2005-10-31 21:31 UTC (permalink / raw)
To: Fans of the OS Plan 9 from Bell Labs
>> Heck, it could be as simple as "each message is 1 directory,
>> containing chunks stored one per file, named by integers, and the
>> original message is formed by cat'ing the chunks in numerical
>> order".
> This turns out to be a pessimization.
Of what?
One possible goal (not the only consideration) would be for
the N copies of a monster attachment received by your N
users to occupy space==1 instead of space==N. Cyrus IMAP
does this in certain circumstances. Fossil+Venti will do
it automatically, but only (at present) if the attachment
is aligned the same way in each user's mailbox, which it
frequently won't be...or if it's stored out of line in a
separate file, which would align it the same way for all N
users.
Maybe it's not worth worrying about.
Dave Eckhardt
^ permalink raw reply [flat|nested] 39+ messages in thread
* [9fans] Scaleable mail repositories.
2005-10-30 1:18 ` Paul Lalonde
` (2 preceding siblings ...)
2005-10-30 15:17 ` Russ Cox
@ 2005-10-31 4:06 ` Lyndon Nerenberg
2005-10-31 10:55 ` C H Forsyth
3 siblings, 1 reply; 39+ messages in thread
From: Lyndon Nerenberg @ 2005-10-31 4:06 UTC (permalink / raw)
To: Fans of the OS Plan 9 from Bell Labs
On Oct 29, 2005, at 6:18 PM, Paul Lalonde wrote:
> I used to keep all my mail this way using MH; it worked well up to
> the point where directories got so full that directory operations
> were taking too long (I remember a nasty n^2 sort in the early days
> of linux). If Plan9's file handling is up to it, I'm in favour of
> this approach. Just remember that it has to work well with 10's of
> thousands of emails in a directory - search is making organization
> obsolete. Heck, some of us didn't manage organization before
> search made it obsolete.
The trick to making this work well is to do what the Cyrus IMAP
server does: use the MH style one-message-per-file layout, and keep
an index cache of the commonly accessed items (from, to, date, mime
structure). It's fast, and it scales very well. When I was at
Messaging Direct we sold a commercial version of the Cyrus server.
We later designed our own IMAP server, but we kept the Cyrus file and
cache layout as it was still the fastest and most scalable solution
to the problem.
--lyndon
^ permalink raw reply [flat|nested] 39+ messages in thread* Re: [9fans] Scaleable mail repositories.
2005-10-31 4:06 ` [9fans] Scaleable mail repositories Lyndon Nerenberg
@ 2005-10-31 10:55 ` C H Forsyth
2005-10-31 12:32 ` erik quanstrom
2005-10-31 15:30 ` jmk
0 siblings, 2 replies; 39+ messages in thread
From: C H Forsyth @ 2005-10-31 10:55 UTC (permalink / raw)
To: 9fans
[-- Attachment #1: Type: text/plain, Size: 516 bytes --]
i don't understand why, now that it's easy to write file servers
(compared to unix days), it's necessary to store the mail messages
as actual separate files or directories. the main problem with
upas/fs i find is that it rewrites the file instead of treating it
as append-only, and it reads the whole thing into memory (in a moderately
bulky format); rather than maintaining a separate index file or files,
and loading as needed. both the storage and index structure can
then be made suitable for the task.
[-- Attachment #2: Type: message/rfc822, Size: 3962 bytes --]
From: Lyndon Nerenberg <lyndon@orthanc.ca>
To: Fans of the OS Plan 9 from Bell Labs <9fans@cse.psu.edu>
Subject: [9fans] Scaleable mail repositories.
Date: Sun, 30 Oct 2005 20:06:37 -0800
Message-ID: <D99CBD3A-2049-4C0C-913F-93151D7D56EE@orthanc.ca>
On Oct 29, 2005, at 6:18 PM, Paul Lalonde wrote:
> I used to keep all my mail this way using MH; it worked well up to
> the point where directories got so full that directory operations
> were taking too long (I remember a nasty n^2 sort in the early days
> of linux). If Plan9's file handling is up to it, I'm in favour of
> this approach. Just remember that it has to work well with 10's of
> thousands of emails in a directory - search is making organization
> obsolete. Heck, some of us didn't manage organization before
> search made it obsolete.
The trick to making this work well is to do what the Cyrus IMAP
server does: use the MH style one-message-per-file layout, and keep
an index cache of the commonly accessed items (from, to, date, mime
structure). It's fast, and it scales very well. When I was at
Messaging Direct we sold a commercial version of the Cyrus server.
We later designed our own IMAP server, but we kept the Cyrus file and
cache layout as it was still the fastest and most scalable solution
to the problem.
--lyndon
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [9fans] Scaleable mail repositories.
2005-10-31 10:55 ` C H Forsyth
@ 2005-10-31 12:32 ` erik quanstrom
2005-11-01 19:56 ` rog
2005-10-31 15:30 ` jmk
1 sibling, 1 reply; 39+ messages in thread
From: erik quanstrom @ 2005-10-31 12:32 UTC (permalink / raw)
To: 9fans, C H Forsyth
on the other hand, what is the downside of keeping one message
per file? the upside is that no indexing is required.
- erik
C H Forsyth <forsyth@vitanuova.com> writes
|
| --upas-vddxtudmbktypqdrugeyxvxyrl
|
| i don't understand why, now that it's easy to write file servers
| (compared to unix days), it's necessary to store the mail messages
| as actual separate files or directories. the main problem with
| upas/fs i find is that it rewrites the file instead of treating it
| as append-only, and it reads the whole thing into memory (in a moderately
| bulky format); rather than maintaining a separate index file or files,
| and loading as needed. both the storage and index structure can
| then be made suitable for the task.
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [9fans] Scaleable mail repositories.
2005-10-31 12:32 ` erik quanstrom
@ 2005-11-01 19:56 ` rog
2005-11-01 22:29 ` Francisco J Ballesteros
0 siblings, 1 reply; 39+ messages in thread
From: rog @ 2005-11-01 19:56 UTC (permalink / raw)
To: 9fans
> on the other hand, what is the downside of keeping one message
> per file? the upside is that no indexing is required.
i'd say that an advantage of going for an indexed scheme is that one
could potentially index attributes other than message number.
i've never got around to biting the bullet on this, but i've long
thought that it would be very nice to have a version of upas/fs which
could offer different views onto the same mailbox. one could
implement a clone-file style filesystem where each line directory
holds a some subset of the messages in the overall mailbox, determined
by writing a control message, e.g. a regexp restriction on a given
header line. suitable indexing, and a little extra acme support could
make this a smooth experience.
i keep many of my old mail messages around, and it's painful to search
through them - i usually end up using grep -n, and plumbing the
mailbox file into acme, which has at least the advantage that it
doesn't use up all my memory. however it's not a particularly
pleasant experience, and i'd love to see something better.
BTW, one advantage of a file-per-message format is that it enables
straightforward annotation of messages without relying on
mailbox-to-index-file consistency. i don't know how others use mail,
but i'd find some sort of annotation useful (e.g. read/unread, intent
to reply), and maybe this is a possible reason for changing the
storage format. i'm not sure though. reading many files and
directories will inevitably slow things down (a quick estimate on my
current 23MB mbox shows that it would take just over 4 times as many
9P transactions to read the whole thing if each message were stored as
the a separate file).
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [9fans] Scaleable mail repositories.
2005-11-01 19:56 ` rog
@ 2005-11-01 22:29 ` Francisco J Ballesteros
2005-11-08 19:56 ` rog
0 siblings, 1 reply; 39+ messages in thread
From: Francisco J Ballesteros @ 2005-11-01 22:29 UTC (permalink / raw)
To: Fans of the OS Plan 9 from Bell Labs
Why search just mail? If you store your mail as files and put in place
a search engine, the views and searches you want to make will work
for it all.
On 11/1/05, rog@vitanuova.com <rog@vitanuova.com> wrote:
> > on the other hand, what is the downside of keeping one message
> > per file? the upside is that no indexing is required.
>
> i'd say that an advantage of going for an indexed scheme is that one
> could potentially index attributes other than message number.
>
> i've never got around to biting the bullet on this, but i've long
> thought that it would be very nice to have a version of upas/fs which
> could offer different views onto the same mailbox. one could
> implement a clone-file style filesystem where each line directory
> holds a some subset of the messages in the overall mailbox, determined
> by writing a control message, e.g. a regexp restriction on a given
> header line. suitable indexing, and a little extra acme support could
> make this a smooth experience.
>
> i keep many of my old mail messages around, and it's painful to search
> through them - i usually end up using grep -n, and plumbing the
> mailbox file into acme, which has at least the advantage that it
> doesn't use up all my memory. however it's not a particularly
> pleasant experience, and i'd love to see something better.
>
> BTW, one advantage of a file-per-message format is that it enables
> straightforward annotation of messages without relying on
> mailbox-to-index-file consistency. i don't know how others use mail,
> but i'd find some sort of annotation useful (e.g. read/unread, intent
> to reply), and maybe this is a possible reason for changing the
> storage format. i'm not sure though. reading many files and
> directories will inevitably slow things down (a quick estimate on my
> current 23MB mbox shows that it would take just over 4 times as many
> 9P transactions to read the whole thing if each message were stored as
> the a separate file).
>
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [9fans] Scaleable mail repositories.
2005-11-01 22:29 ` Francisco J Ballesteros
@ 2005-11-08 19:56 ` rog
2005-11-08 23:22 ` Joel Salomon
` (2 more replies)
0 siblings, 3 replies; 39+ messages in thread
From: rog @ 2005-11-08 19:56 UTC (permalink / raw)
To: 9fans
> Why search just mail? If you store your mail as files and put in place
> a search engine, the views and searches you want to make will work
> for it all.
that would be nice, but i think it's a bit ambitious for what i'm
looking at currently. the search engine would have to be quite
intelligent:
1) it would have to be triggered on the arrival of new mail (otherwise
newly arrived messages would not be held in the index)
2) it would have to know which parts of the file system contained
mail messages and MIME parse them (assuming the mail files
were stored in raw format, which seems necessary for digital
signature verification, not to mention efficiency of delivery
and storage).
having just had a brief glance at the description of Google Desktop,
it appears that it probably does all these things. in fact, given the
special parsing necessary to index different kinds of data, it's
probably irrelevant what format the mailbox is in - it's dealable
with.
i have to say that some kind of "google desktop for plan 9" would be
lovely, but going for mail first is perhaps a more immediately
realisable target.
the first step, anyway, in both cases, is writing the code to do the
inverted index.
i thought i'd write an external search algorithm - i'm most of the way
through an extendable hash implementation (which seems simple and
quick for insertion, but things get more complex when dealing with
large values, and on deletion; i'm not sure of the best way to deal
with block allocation; and more seriously, maybe it's essential to
have an algorithm that can do range (e.g. prefix) lookups). any
elegant (read *small*!), nicely implemented, open source libraries out
there that might fit the bill? a good description of an appropriate
algorithm would do just as well...
^ permalink raw reply [flat|nested] 39+ messages in thread* Re: [9fans] Scaleable mail repositories.
2005-11-08 19:56 ` rog
@ 2005-11-08 23:22 ` Joel Salomon
2005-11-09 0:51 ` Caerwyn Jones
2005-11-09 3:32 ` erik quanstrom
2 siblings, 0 replies; 39+ messages in thread
From: Joel Salomon @ 2005-11-08 23:22 UTC (permalink / raw)
To: Fans of the OS Plan 9 from Bell Labs
On 11/8/05, rog@vitanuova.com <rog@vitanuova.com> wrote:
> i have to say that some kind of "google desktop for plan 9" would be
> lovely, but going for mail first is perhaps a more immediately
> realisable target.
>
Gmail for Plan 9, then?
--Joel
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [9fans] Scaleable mail repositories.
2005-11-08 19:56 ` rog
2005-11-08 23:22 ` Joel Salomon
@ 2005-11-09 0:51 ` Caerwyn Jones
2005-11-09 0:55 ` Russ Cox
2005-11-09 3:32 ` erik quanstrom
2 siblings, 1 reply; 39+ messages in thread
From: Caerwyn Jones @ 2005-11-09 0:51 UTC (permalink / raw)
To: Fans of the OS Plan 9 from Bell Labs
> any elegant (read *small*!), nicely implemented, open source libraries out
> there that might fit the bill?
i've had some success at work using lucene (http://lucene.apache.org).
i'd recommend it. i have thought about implementing it in limbo, but
have yet to get around to it.
on inferno i use an inverted index i wrote based on a btree. it's on
my website, called lexis. i've indexed over 5 years of plain text
emails, one per file, and can usually find anything in seconds. it
supports ranges and is general enough to support file annotations,
categories and binary relations.
-caerwyn
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [9fans] Scaleable mail repositories.
2005-11-09 0:51 ` Caerwyn Jones
@ 2005-11-09 0:55 ` Russ Cox
0 siblings, 0 replies; 39+ messages in thread
From: Russ Cox @ 2005-11-09 0:55 UTC (permalink / raw)
To: Fans of the OS Plan 9 from Bell Labs
> on inferno i use an inverted index i wrote based on a btree. it's on
> my website, called lexis. i've indexed over 5 years of plain text
> emails, one per file, and can usually find anything in seconds. it
> supports ranges and is general enough to support file annotations,
> categories and binary relations.
seconds is too long. it's really bothering me that gmail takes
seconds to answer my mail searches. i feel like it used to be
much faster. if i had a reasonable local interface with a fast
search i'd think about switching back.
russ
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [9fans] Scaleable mail repositories.
2005-11-08 19:56 ` rog
2005-11-08 23:22 ` Joel Salomon
2005-11-09 0:51 ` Caerwyn Jones
@ 2005-11-09 3:32 ` erik quanstrom
2 siblings, 0 replies; 39+ messages in thread
From: erik quanstrom @ 2005-11-09 3:32 UTC (permalink / raw)
To: 9fans, rog
i don't think it would be that bad.
in 1996 in my former life as an IBMer we put up 30 million documents
plus the OpenText web index up on the web. we were using OpenText's
"pat" engine "cpl" (aka "cpl") and some other full-text search software to run the
queries. if you haven't heard of these, don't feel bad. they're pretty unremarkable
and no longer exist. performance absolutely bit. partially becuase the interface
between the driver and the engine was xml. (go figure. tim bray was the big
man at opentext.) but the main reason was that the index was set up for
grep-like searches, doing the matching directly against the (patricia-tree'd) text.
i've come to think that's backwards. i think you should scan the corpus for a
list if unique stemmed terms. (run running Run Run! all considered the same term)
and assign each term an index number. each document can be represnted as a
string of unique index numbers which can be indexed using normal techniques.
a search would first convert the terms to index numbers and then do the search.
regular expressions could be applied to the /term/ list*, not the corpus.
you could prototype this with 3 tables (term_tab, doc_term_xref, doc_tab)
from almost any databaseish thing that allows concurrent updates and queries.
obviously there's some generality lost. (proximity searches, whitespace/newline matching.)
but, i think this would get you 80% of what you would want at 20% of the complexity.
so many things to program, so little time.
- erik "mr vaporware" quanstrom
* my quick-and-dirty term check of my own email archive gives ~33000 terms.
(this is a big overcount.)
; cat */* | \
tr 'A-Z' 'a-z' | \
sed 's/[][;:"{}~`!@#$%^&*()+=|\\/?<>,.]/ /g' | \
grep -v '[^a-z0-9]$' | \
awk '
{
for (i=1; i<=NF;i++) {
l = length($i);
if (l>1 && l<15)
A[$i]++
}
}
END {
n=0;
for(i in A) {
n++;
printf("%d %s\n", A[i], i);
}
print n
}' |wc -l
33558
rog@vitanuova.com writes
| i thought i'd write an external search algorithm - i'm most of the way
| through an extendable hash implementation (which seems simple and
| quick for insertion, but things get more complex when dealing with
| large values, and on deletion; i'm not sure of the best way to deal
| with block allocation; and more seriously, maybe it's essential to
| have an algorithm that can do range (e.g. prefix) lookups). any
| elegant (read *small*!), nicely implemented, open source libraries out
| there that might fit the bill? a good description of an appropriate
| algorithm would do just as well...
^ permalink raw reply [flat|nested] 39+ messages in thread
* Re: [9fans] Scaleable mail repositories.
2005-10-31 10:55 ` C H Forsyth
2005-10-31 12:32 ` erik quanstrom
@ 2005-10-31 15:30 ` jmk
1 sibling, 0 replies; 39+ messages in thread
From: jmk @ 2005-10-31 15:30 UTC (permalink / raw)
To: 9fans
you spoiled it. i was waiting to see how long it took for the
community to come up with that.
On Mon Oct 31 05:57:02 EST 2005, forsyth@vitanuova.com wrote:
> i don't understand why, now that it's easy to write file servers
> (compared to unix days), it's necessary to store the mail messages
> as actual separate files or directories. the main problem with
> upas/fs i find is that it rewrites the file instead of treating it
> as append-only, and it reads the whole thing into memory (in a moderately
> bulky format); rather than maintaining a separate index file or files,
> and loading as needed. both the storage and index structure can
> then be made suitable for the task.
^ permalink raw reply [flat|nested] 39+ messages in thread