]> Sergey Matveev's repositories - public-inbox.git/commitdiff
extmsg: use Xapian only for partial matches
authorEric Wong (Contractor, The Linux Foundation) <e@80x24.org>
Sun, 22 Apr 2018 08:01:48 +0000 (08:01 +0000)
committerEric Wong <e@80x24.org>
Sun, 22 Apr 2018 08:02:13 +0000 (08:02 +0000)
"LIKE" in SQLite (and other SQL implementations I've seen) is
expensive with nearly 3 million messages in the archives.

This caused some partial Message-ID lookups to take over 600ms
on my workstation (~300ms on a faster Xeon).  Cut that to below
under 30ms on average on my workstation by relying exclusively
on Xapian for partial Message-ID lookups as we have in the past.

Unlike in the past when we tried using Xapian to match partial
Message-IDs; we now optimize our indexing of Message-IDs to
break apart "words" in Message-IDs for searching, yielding
(hopefully) "good enough" accuracy for folks who get long URLs
broken across lines when copy+pasting.

We'll also drop the (in retrospect) pointless stripping of
"/[tTf]" suffixes for the partial match, since anybody who
hits that codepath would be hitting an invalid message ID.

Finally, limit wildcard expansion to prevent easy DoS vectors
on short terms.

And blame Pine and alpine for generating Message-IDs with
low-entropy prefixes :P

lib/PublicInbox/ExtMsg.pm
lib/PublicInbox/Msgmap.pm
lib/PublicInbox/Search.pm
lib/PublicInbox/SearchIdx.pm
t/cgi.t
t/msgmap.t
t/psgi_search.t
t/search.t

index 04cb40623de30f8105e5af1cb8c6254f2128607c..51e7799de8640929be9538713d3f2ee7e1b1081d 100644 (file)
@@ -26,6 +26,52 @@ our @EXT_URL = (
                'doc-url=/lurker&format=en.html&query=id:%s'
 );
 
+sub PARTIAL_MAX () { 100 }
+
+sub search_partial ($$) {
+       my ($srch, $mid) = @_;
+       my $opt = { limit => PARTIAL_MAX, mset => 2 };
+       my @try = ("m:$mid*");
+       my $chop = $mid;
+       if ($chop =~ s/(\W+)(\w*)\z//) {
+               my ($delim, $word) = ($1, $2);
+               if (length($word)) {
+                       push @try, "m:$chop$delim";
+                       push @try, "m:$chop$delim*";
+               }
+               push @try, "m:$chop";
+               push @try, "m:$chop*";
+       }
+
+       # break out long words individually to search for, because
+       # too many messages begin with "Pine.LNX." (or "alpine" or "nycvar")
+       if ($mid =~ /\w{9,}/) {
+               my @long = ($mid =~ m!(\w{3,})!g);
+               push(@try, join(' ', map { "m:$_" } @long));
+
+               # is the last element long enough to not trigger excessive
+               # wildcard matches?
+               if (length($long[-1]) > 8) {
+                       $long[-1] .= '*';
+                       push(@try, join(' ', map { "m:$_" } @long));
+               }
+       }
+
+       foreach my $m (@try) {
+               my $mset = eval { $srch->query($m, $opt) };
+               if (ref($@) eq 'Search::Xapian::QueryParserError') {
+                       # If Xapian can't handle the wildcard since it
+                       # has too many results.
+                       next;
+               }
+               my @mids = map {
+                       my $doc = $_->get_document;
+                       PublicInbox::SearchMsg->load_doc($doc)->mid;
+               } $mset->items;
+               return \@mids if scalar(@mids);
+       }
+}
+
 sub ext_msg {
        my ($ctx) = @_;
        my $cur = $ctx->{-inbox};
@@ -56,41 +102,23 @@ sub ext_msg {
        return exact($ctx, \@found, $mid) if @found;
 
        # fall back to partial MID matching
-       my $n_partial = 0;
        my @partial;
-
-       if (my $mm = $cur->mm) {
-               my $tmp_mid = $mid;
-               my $res = $mm->mid_prefixes($tmp_mid, 100);
-               if ($res && scalar(@$res)) {
-                       $n_partial += scalar(@$res);
-                       push @partial, [ $cur, $res ];
-               # fixup common errors:
-               } elsif ($tmp_mid =~ s,/[tTf],,) {
-                       $res = $mm->mid_prefixes($tmp_mid, 100);
-                       if ($res && scalar(@$res)) {
-                               $n_partial += scalar(@$res);
-                               push @partial, [ $cur, $res ];
-                       }
-               }
+       my $n_partial = 0;
+       my $srch = $cur->search;
+       my $mids = search_partial($srch, $mid) if $srch;
+       if ($mids) {
+               $n_partial = scalar(@$mids);
+               push @partial, [ $cur, $mids ];
        }
 
        # can't find a partial match in current inbox, try the others:
        if (!$n_partial && length($mid) >= 16) {
-               my $tmp_mid = $mid;
-again:
                foreach my $ibx (@ibx) {
-                       my $mm = $ibx->mm or next;
-                       my $res = $mm->mid_prefixes($tmp_mid, 100);
-                       if ($res && scalar(@$res)) {
-                               $n_partial += scalar(@$res);
-                               push @partial, [ $ibx, $res ];
-                               last if $n_partial >= 100;
-                       }
-               }
-               # fixup common errors:
-               if (!$n_partial && $tmp_mid =~ s,/[tTf],,) {
-                       goto again;
+                       $srch = $ibx->search or next;
+                       $mids = search_partial($srch, $mid) or next;
+                       $n_partial += scalar(@$mids);
+                       push @partial, [ $ibx, $mids];
+                       last if $n_partial >= PARTIAL_MAX;
                }
        }
 
@@ -103,6 +131,7 @@ again:
        if ($n_partial) {
                $code = 300;
                my $es = $n_partial == 1 ? '' : 'es';
+               $n_partial .= '+' if ($n_partial == PARTIAL_MAX);
                $s .= "\n$n_partial partial match$es found:\n\n";
                my $cur_name = $cur->{name};
                foreach my $pair (@partial) {
index 6e758c1aa789d19951829ef5e7f4262751c518e7..192e311aec2b1d459407e0853cfcecb26c2f0448 100644 (file)
@@ -36,7 +36,6 @@ sub dbh_new {
                ReadOnly => !$writable,
                sqlite_use_immediate_transaction => 1,
        });
-       $dbh->do('PRAGMA case_sensitive_like = ON');
        $dbh;
 }
 
@@ -151,23 +150,6 @@ sub minmax {
        ($min, $sth->fetchrow_array);
 }
 
-sub mid_prefixes {
-       my ($self, $pfx, $limit) = @_;
-
-       die "No prefix given" unless (defined $pfx && $pfx ne '');
-       $pfx =~ s/([%_])/\\$1/g;
-       $pfx .= '%';
-
-       $limit ||= 100;
-       $limit += 0; # force to integer
-       $limit ||= 100;
-
-       $self->{dbh}->selectcol_arrayref('SELECT mid FROM msgmap ' .
-                                        'WHERE mid LIKE ? ESCAPE ? ' .
-                                        "ORDER BY num DESC LIMIT $limit",
-                                        undef, $pfx, '\\');
-}
-
 sub mid_delete {
        my ($self, $mid) = @_;
        my $dbh = $self->{dbh};
index 7175ddc5a2e06c078ef10f1d7875e3eebd62d709..5aabda02f4a6b3c808b941da19132c4231589055 100644 (file)
@@ -260,6 +260,7 @@ sub qp {
        $qp->set_database($self->{xdb});
        $qp->set_stemmer($self->stemmer);
        $qp->set_stemming_strategy(STEM_SOME);
+       $qp->set_max_wildcard_expansion(100);
        $qp->add_valuerangeprocessor(
                Search::Xapian::NumberValueRangeProcessor->new(YYYYMMDD, 'd:'));
        $qp->add_valuerangeprocessor(
index 4dc81352f535568d7673cabb8d6ad6fff5cb859b..aeb363e03d1d57a7ccd3cc7c1ae408cf98d91a05 100644 (file)
@@ -331,6 +331,13 @@ sub add_message {
 
                foreach my $mid (@$mids) {
                        $tg->index_text($mid, 1, 'XM');
+
+                       # because too many Message-IDs are prefixed with
+                       # "Pine.LNX."...
+                       if ($mid =~ /\w{12,}/) {
+                               my @long = ($mid =~ /(\w{3,}+)/g);
+                               $tg->index_text(join(' ', @long), 1, 'XM');
+                       }
                        $tg->increase_termpos;
                }
                $smsg->{to} = $smsg->{cc} = '';
diff --git a/t/cgi.t b/t/cgi.t
index ef32a2845fee9f99a13d72c4ab093af17d48d1bc..bd92ca361047f886cbdbace18521774703863882 100644 (file)
--- a/t/cgi.t
+++ b/t/cgi.t
@@ -155,22 +155,16 @@ EOF
        $res = cgi_run("/test/blahblah\@example.com/raw");
        like($res->{body}, qr/Message-Id: <blahblah\@example\.com>/,
                "mid raw hit");
-       $res = cgi_run("/test/blahblah\@example.con/raw");
-       like($res->{head}, qr/Status: 300 Multiple Choices/, "mid raw miss");
 
        $res = cgi_run("/test/blahblah\@example.com/");
        like($res->{body}, qr/\A<html>/, "mid html hit");
        like($res->{head}, qr/Status: 200 OK/, "200 response");
-       $res = cgi_run("/test/blahblah\@example.con/");
-       like($res->{head}, qr/Status: 300 Multiple Choices/, "mid html miss");
 
        $res = cgi_run("/test/blahblah\@example.com/f/");
        like($res->{head}, qr/Status: 301 Moved/, "301 response");
        like($res->{head},
                qr!^Location: http://[^/]+/test/blahblah\@example\.com/\r\n!ms,
                '301 redirect location');
-       $res = cgi_run("/test/blahblah\@example.con/");
-       like($res->{head}, qr/Status: 300 Multiple Choices/, "mid html miss");
 
        $res = cgi_run("/test/new.html");
        like($res->{body}, qr/slashy%2Fasdf\@example\.com/,
index dce98f46b6f57e48a90653ceba659a3665db247d..4dddd0a81852b22c60601b1965d1e7b11224897c 100644 (file)
@@ -38,9 +38,6 @@ foreach my $mid (@mids) {
        is($d->num_for($mid), $mid2num{$mid}, "mid:$mid maps correctly");
 }
 
-is_deeply($d->mid_prefixes('a'), [qw(aa@cc aa@bb a@b)], "mid_prefixes match");
-is_deeply($d->mid_prefixes('A'), [], "mid_prefixes is case sensitive");
-
 is(undef, $d->last_commit, "last commit not set");
 my $lc = 'deadbeef' x 5;
 is(undef, $d->last_commit($lc), 'previous last commit (undef) returned');
index 2f033016ef8272d0699e2628ac212553a52822c3..a057a994f3cbe38f17962c59e8c4e7d1f7a9c7ca 100644 (file)
@@ -20,11 +20,14 @@ my $git_dir = "$tmpdir/a.git";
 is(0, system(qw(git init -q --bare), $git_dir), "git init (main)");
 my $rw = PublicInbox::SearchIdx->new($git_dir, 1);
 ok($rw, "search indexer created");
-my $data = <<'EOF';
+my $digits = '10010260936330';
+my $ua = 'Pine.LNX.4.10';
+my $mid = "$ua.$digits.2460-100000\@penguin.transmeta.com";
+my $data = <<"EOF";
 Subject: test
-Message-Id: <utf8@example>
-From: Ævar Arnfjörð Bjarmason <avarab@example>
-To: git@vger.kernel.org
+Message-ID: <$mid>
+From: Ævar Arnfjörð Bjarmason <avarab\@example>
+To: git\@vger.kernel.org
 
 EOF
 
@@ -37,8 +40,7 @@ foreach (reverse split(/\n\n/, $data)) {
        my $mime = Email::MIME->new(\$_);
        my $bytes = bytes::length($mime->as_string);
        my $doc_id = $rw->add_message($mime, $bytes, ++$num, 'ignored');
-       my $mid = $mime->header('Message-Id');
-       ok($doc_id, 'message added: '. $mid);
+       ok($doc_id, 'message added');
 }
 
 $rw->commit_txn_lazy;
@@ -72,6 +74,15 @@ test_psgi(sub { $www->call(@_) }, sub {
        $res = $cb->(POST('/test/?q=s:bogus&x=m'));
        is($res->code, 404, 'failed search result gives 404');
        is_deeply([], $warn, 'no warnings');
+
+       my $mid_re = qr/\Q$mid\E/o;
+       while (length($digits) > 8) {
+               $res = $cb->(GET("/test/$ua.$digits/"));
+               is($res->code, 300, 'partial match found while truncated');
+               like($res->content, qr/\b1 partial match found\b/);
+               like($res->content, $mid_re, 'found mid in response');
+               chop($digits);
+       }
 });
 
 done_testing();
index 004b7aa36ab3982ddd6d3cfcd810727e950ff425..54f2db906a04cd04d7cddda3bf175feed2e82c4f 100644 (file)
@@ -430,6 +430,36 @@ foreach my $f ("$git_dir/public-inbox/msgmap.sqlite3",
                "sharedRepository respected for $bn");
 }
 
+$ibx->with_umask(sub {
+       $rw_commit->();
+       my $digits = '10010260936330';
+       my $ua = 'Pine.LNX.4.10';
+       my $mid = "$ua.$digits.2460-100000\@penguin.transmeta.com";
+       is($ro->reopen->query("m:$digits", { mset => 1})->size, 0,
+               'no results yet');
+       my $pine = Email::MIME->create(
+               header_str => [
+                       Subject => 'blah',
+                       'Message-ID' => "<$mid>",
+                       From => 'torvalds@transmeta',
+                       To => 'list@example.com',
+               ],
+               body => ""
+       );
+       my $x = $rw->add_message($pine);
+       $rw->commit_txn_lazy;
+       is($ro->reopen->query("m:$digits", { mset => 1})->size, 1,
+               'searching only digit yielded result');
+
+       my $wild = $digits;
+       for my $i (1..6) {
+               chop($wild);
+               is($ro->query("m:$wild*", { mset => 1})->size, 1,
+                       "searching chopped($i) digit yielded result $wild ");
+       }
+       is($ro->query("m:Pine m:LNX m:10010260936330", {mset=>1})->size, 1);
+});
+
 done_testing();
 
 1;