]> git.ipfire.org Git - thirdparty/sqlite.git/commit
Change prefix search from O(N*M) to O(NlogM). The previous code
authorshess <shess@noemail.net>
Fri, 7 Dec 2007 23:47:53 +0000 (23:47 +0000)
committershess <shess@noemail.net>
Fri, 7 Dec 2007 23:47:53 +0000 (23:47 +0000)
commitb6a75606ed995f51626c1d0f542f5f0377e1adea
tree03616843e4149b05377ccb8e05a8e1400c906c84
parente5fe690d75d9b98e91428d949deb7e53622b1010
Change prefix search from O(N*M) to O(NlogM).  The previous code
linearly merged the doclists, so as the accumulated list got large,
things got slow (the M term, a fucntion of the number of documents in
the index).  This change does pairwise merges until a single doclist
remains.  A test search of 't*' against a database of RFC text
improves from 1m16s to 4.75s. (CVS 4599)

FossilOrigin-Name: feef1b15d645d638b4a05742f214b0445fa7e176
ext/fts3/fts3.c
manifest
manifest.uuid