Firefox/Projects/FTS and Awesomebar: Difference between revisions

← Older edit

Firefox/Projects/FTS and Awesomebar (view source)

Revision as of 22:20, 20 July 2010

1,621 bytes added , 20 July 2010

→‎Status

Adw

Confirmed users

764

edits

@@ Line 1: / Line 1: @@
 == Intro ==
-This project will attempt make Storage text searches faster, focusing on the awesomebar.
+This project will attempt to make Storage text searches faster, focusing on the awesomebar.
 SQLite supports indexed full text search (FTS) through its fts extensions.  Indexed FTS makes text searches fast:  Rather than looking at every record in the database to see if it contains a search string, target records are found by comparing the search string against an index.
-But the fts extensions aren't by default suitable for international text.  This project will try to make them suitable so we can use FTS to improve Firefox features that rely on Storage text searches for all of our users.
 A good first target feature is the awesomebar.  It is highly visible, and since it makes extensive use of text searches, it stands to benefit from this work.
-Note that full text search does not mean that we store the entire text of pages.  We will use it to store page titles, URLs, tags, etc., as we already do now, only lookup will be fast.
+(Note that full text search does not mean that we store the entire text of pages.  We will use it to store page titles, URLs, tags, etc., as we already do now, only lookup will be fast.)
 * Champion, lead: adw
@@ Line 15: / Line 13: @@
 == Status ==
-TAKING OFF
+STALLED, GOING DOWN, PEOPLE SCREAMING
+==== 2010/04/07 ====
+After a few weeks of exploration, it's not clear as I had hoped it would be that FTS can provide faster awesomebar searches on the desktop.  The awesomebar's default SQL query (one of several it performs) makes good use of indexes, and while I don't fully understand why, its execution seems to take constant time independent of data set size.  Prefix searches with FTS are slow; to mitigate, I investigated partitioning the FTS table into many tables, each containing no more than 1000 rows.  Individual table lookups were fast with this scheme, but the overhead of searching dozens of tables conspired to make the aggregate query slower than the awesomebar's default query.  Perhaps there is a way to game this tradeoff between partitioning and overhead that more tinkering would reveal.
+There may be other areas of Firefox where FTS can help -- search terms in the Places query API, for example.
+On hold for now.
+==== Week of 2010/03/15 ====
+* Progress in hooking up the awesomebar to FTS for the purpose of performance testing.
+** Exact matches are quite fast, i.e., matching whole words.  Finding the records in a places database with 34000 history entries that match a whole word is on the order of 10 ms.  Noticably faster than the current awesomebar.
+** However, prefix searches, i.e., searching for words that start with a given string, can be quite slow.  For common prefixes, they can be even slower than a full table scan.  (See also [http://www.mail-archive.com/sqlite-users@sqlite.org/msg29729.html this mail].)  Prefixing searching is of course the real-world case.
+** If prefix searches are really slower than full table scans, then this project is done.
+** So I'm currently trying ways of optimizing prefix searches.  Partitioning the FTS tables and doing multiple queries is showing some promise.
-The work below was all done during the week of 2010/03/08.
+==== Week of 2010/03/08 ====
 * Gecko has some facilities for i18n word boundary analysis under the  [http://mxr.mozilla.org/mozilla-central/source/intl/lwbrk/ intl/lwbrk/] directory.