full-text-search 0.2.2.0 → 0.2.2.1
raw patch · 3 files changed
+57/−13 lines, 3 filesdep ~basePVP ok
version bump matches the API change (PVP)
Dependency ranges changed: base
API changes (from Hackage documentation)
Files
- Data/SearchEngine/Autosuggest.hs +50/−9
- changelog +3/−0
- full-text-search.cabal +4/−4
Data/SearchEngine/Autosuggest.hs view
@@ -72,7 +72,7 @@ -- { (t, ds ∩ ds_t) | t ∈ ts, ds ∩ ds_t ≠ ∅ } step_process (ts, ds, pre_ts) = (ts', ds', tdss', pre_ts) where- (tdss', ts', ds') = processAutosuggestQuery (ts, ds, pre_ts)+ (tdss', ts', ds') = processAutosuggestQuery se (ts, ds, pre_ts) -- If the number of docs results is huge then we may not want to bother -- and just return no results. Even the filtering of a huge number of@@ -127,7 +127,7 @@ SearchEngine doc key field feature -> [Term] -> Term -> [key] queryAutosuggestMatchingDocuments se@SearchEngine{searchIndex} precedingTerms partialTerm =- let (_, _, ds) = processAutosuggestQuery (mkAutosuggestQuery se precedingTerms partialTerm)+ let (_, _, ds) = processAutosuggestQuery se (mkAutosuggestQuery se precedingTerms partialTerm) in map (SI.getDocKey searchIndex) (DocIdSet.toList ds) -- | Given an incomplete prefix query, return a predicate that indicates whether@@ -140,7 +140,7 @@ SearchEngine doc key field feature -> [Term] -> Term -> (key -> Bool) queryAutosuggestPredicate se@SearchEngine{searchIndex} precedingTerms partialTerm =- let (_, _, ds) = processAutosuggestQuery (mkAutosuggestQuery se precedingTerms partialTerm)+ let (_, _, ds) = processAutosuggestQuery se (mkAutosuggestQuery se precedingTerms partialTerm) in (\ key -> maybe False (flip DocIdSet.member ds) (SI.lookupDocKeyDocId searchIndex key)) @@ -207,9 +207,42 @@ (precedingTerms', precedingDocHits) | null precedingTerms = ([], Nothing)- | otherwise = fmap (Just . DocIdSet.unions)+ | otherwise = fmap carefulUnions (lookupRawResults precedingTerms) + -- For the preceding terms, we compute the union of the sets of documents in+ -- which they appear. This means that a query like "Apple Blackberry C"+ -- will look for documents containing "Apple" or "Blackberry", then later+ -- intersect that set with documents containing completions of "C".+ --+ -- In general we want to use union rather than intersection here, because+ -- the preceding terms might contain some useful and some missing terms, and+ -- if we took the intersection we would end up with no results; thus we rely+ -- on scoring to rank the best matches highest.+ --+ -- However, this leads to an issue: if some of the terms are extremely+ -- common, we might end up taking unions of very large document sets, which+ -- is a performance disaster. We address this by unioning only sets smaller+ -- than the pre-filter limit (but falling back on the whole collection if+ -- all sets are too large). This means that:+ --+ -- * A query containing a mixture of common and uncommon preceding terms+ -- will be completed/ranked solely based on the uncommon terms. For+ -- example, "Apple Blackberry C" will be equivalent to "Blackberry C" if+ -- there are many apples.+ --+ -- * A query containing only common preceding terms will be+ -- completed/ranked as if only the final term was present. For example,+ -- "Apple Blackberry C" will be equivalent to "C" if there are many+ -- apples and blackberries.+ --+ carefulUnions :: [DocIdSet] -> Maybe DocIdSet+ carefulUnions dss+ | null dss' = Nothing+ | otherwise = Just (DocIdSet.unions dss')+ where+ dss' = filter (withinPrefilterLimit se) dss+ lookupRawResults :: [Term] -> ([TermId], [DocIdSet]) lookupRawResults ts = unzip $ catMaybes@@ -234,13 +267,20 @@ -- We will do this but additionally we will return all the non-empty -- intersections because they will be useful when scoring. -processAutosuggestQuery :: AutosuggestQuery ->+processAutosuggestQuery :: SearchEngine doc key field feature ->+ AutosuggestQuery -> ([(TermId, DocIdSet)], [TermId], DocIdSet)-processAutosuggestQuery (completionTerms, precedingDocHits, _) =+processAutosuggestQuery se (completionTerms, precedingDocHits, _)+ -- Check all the individual document sets are smaller than the pre-filter+ -- limit. If any are larger, their union must also be too large, so we return+ -- no results now rather than having to compute the union (which may be+ -- expensive) only for it to inevitably hit the limit.+ | all (withinPrefilterLimit se) docSets = ( completionTermAndDocSets , completionTerms' , allTermDocSet )+ | otherwise = ([], [], DocIdSet.empty) where -- We look up each candidate completion to find the set of documents -- it appears in, and filtering (intersecting) down to just those@@ -262,12 +302,13 @@ ] -- The remaining candidate completions- completionTerms' = [ w | (w, _ds_w) <- completionTermAndDocSets ]+ completionTerms' :: [TermId]+ docSets :: [DocIdSet]+ (completionTerms', docSets) = unzip completionTermAndDocSets -- The union of all these is this set of documents that form the results. allTermDocSet :: DocIdSet- allTermDocSet =- DocIdSet.unions [ ds_t | (_t, ds_t) <- completionTermAndDocSets ]+ allTermDocSet = DocIdSet.unions docSets filterAutosuggestQuery :: SearchEngine doc key field feature ->
changelog view
@@ -1,3 +1,6 @@+0.2.2.1 Adam Gundry <adam@well-typed.com> March 2023+ * Fix autosuggest query performance bug on large datasets+ 0.2.2.0 Adam Gundry <adam@well-typed.com> November 2022 * Add queryAutosuggestPredicate and queryAutosuggestMatchingDocuments * Compatibility with GHC 8.10 to 9.4 and new package versions
full-text-search.cabal view
@@ -1,5 +1,5 @@ name: full-text-search-version: 0.2.2.0+version: 0.2.2.1 synopsis: In-memory full text search engine description: An in-memory full text search engine library. It lets you run full-text queries on a collection of your documents.@@ -47,13 +47,13 @@ maintainer: Duncan Coutts <duncan@well-typed.com>, Adam Gundry <adam@well-typed.com> copyright: 2013-2014 Duncan Coutts, 2014 Well-Typed LLP,- 2014-2022 IRIS Connect Ltd.+ 2014-2023 IRIS Connect Ltd. category: Data, Text, Search build-type: Simple cabal-version: >=1.10 extra-source-files: changelog -tested-with: GHC ==8.10.7 || ==9.0.2 || ==9.2.4 || ==9.4.2+tested-with: GHC ==8.10.7 || ==9.0.2 || ==9.2.7 || ==9.4.4 || ==9.6.1 source-repository head type: git@@ -81,7 +81,7 @@ RecordWildCards, GeneralizedNewtypeDeriving, ScopedTypeVariables- build-depends: base >=4.5 && <5.9,+ build-depends: base >=4.5 && <4.19, array >=0.4 && <0.6, vector >=0.11 && <0.14, containers >=0.4 && <0.7,