]> git.openstreetmap.org Git - nominatim.git/blob - nominatim/api/search/db_search_builder.py
Merge remote-tracking branch 'upstream/master'
[nominatim.git] / nominatim / api / search / db_search_builder.py
1 # SPDX-License-Identifier: GPL-3.0-or-later
2 #
3 # This file is part of Nominatim. (https://nominatim.org)
4 #
5 # Copyright (C) 2023 by the Nominatim developer community.
6 # For a full list of authors see the git log.
7 """
8 Convertion from token assignment to an abstract DB search.
9 """
10 from typing import Optional, List, Tuple, Iterator, Dict
11 import heapq
12
13 from nominatim.api.types import SearchDetails, DataLayer
14 from nominatim.api.search.query import QueryStruct, Token, TokenType, TokenRange, BreakType
15 from nominatim.api.search.token_assignment import TokenAssignment
16 import nominatim.api.search.db_search_fields as dbf
17 import nominatim.api.search.db_searches as dbs
18 import nominatim.api.search.db_search_lookups as lookups
19
20
21 def wrap_near_search(categories: List[Tuple[str, str]],
22                      search: dbs.AbstractSearch) -> dbs.NearSearch:
23     """ Create a new search that wraps the given search in a search
24         for near places of the given category.
25     """
26     return dbs.NearSearch(penalty=search.penalty,
27                           categories=dbf.WeightedCategories(categories,
28                                                             [0.0] * len(categories)),
29                           search=search)
30
31
32 def build_poi_search(category: List[Tuple[str, str]],
33                      countries: Optional[List[str]]) -> dbs.PoiSearch:
34     """ Create a new search for places by the given category, possibly
35         constraint to the given countries.
36     """
37     if countries:
38         ccs = dbf.WeightedStrings(countries, [0.0] * len(countries))
39     else:
40         ccs = dbf.WeightedStrings([], [])
41
42     class _PoiData(dbf.SearchData):
43         penalty = 0.0
44         qualifiers = dbf.WeightedCategories(category, [0.0] * len(category))
45         countries=ccs
46
47     return dbs.PoiSearch(_PoiData())
48
49
50 class SearchBuilder:
51     """ Build the abstract search queries from token assignments.
52     """
53
54     def __init__(self, query: QueryStruct, details: SearchDetails) -> None:
55         self.query = query
56         self.details = details
57
58
59     @property
60     def configured_for_country(self) -> bool:
61         """ Return true if the search details are configured to
62             allow countries in the result.
63         """
64         return self.details.min_rank <= 4 and self.details.max_rank >= 4 \
65                and self.details.layer_enabled(DataLayer.ADDRESS)
66
67
68     @property
69     def configured_for_postcode(self) -> bool:
70         """ Return true if the search details are configured to
71             allow postcodes in the result.
72         """
73         return self.details.min_rank <= 5 and self.details.max_rank >= 11\
74                and self.details.layer_enabled(DataLayer.ADDRESS)
75
76
77     @property
78     def configured_for_housenumbers(self) -> bool:
79         """ Return true if the search details are configured to
80             allow addresses in the result.
81         """
82         return self.details.max_rank >= 30 \
83                and self.details.layer_enabled(DataLayer.ADDRESS)
84
85
86     def build(self, assignment: TokenAssignment) -> Iterator[dbs.AbstractSearch]:
87         """ Yield all possible abstract searches for the given token assignment.
88         """
89         sdata = self.get_search_data(assignment)
90         if sdata is None:
91             return
92
93         near_items = self.get_near_items(assignment)
94         if near_items is not None and not near_items:
95             return # impossible compbination of near items and category parameter
96
97         if assignment.name is None:
98             if near_items and not sdata.postcodes:
99                 sdata.qualifiers = near_items
100                 near_items = None
101                 builder = self.build_poi_search(sdata)
102             elif assignment.housenumber:
103                 hnr_tokens = self.query.get_tokens(assignment.housenumber,
104                                                    TokenType.HOUSENUMBER)
105                 builder = self.build_housenumber_search(sdata, hnr_tokens, assignment.address)
106             else:
107                 builder = self.build_special_search(sdata, assignment.address,
108                                                     bool(near_items))
109         else:
110             builder = self.build_name_search(sdata, assignment.name, assignment.address,
111                                              bool(near_items))
112
113         if near_items:
114             penalty = min(near_items.penalties)
115             near_items.penalties = [p - penalty for p in near_items.penalties]
116             for search in builder:
117                 search_penalty = search.penalty
118                 search.penalty = 0.0
119                 yield dbs.NearSearch(penalty + assignment.penalty + search_penalty,
120                                      near_items, search)
121         else:
122             for search in builder:
123                 search.penalty += assignment.penalty
124                 yield search
125
126
127     def build_poi_search(self, sdata: dbf.SearchData) -> Iterator[dbs.AbstractSearch]:
128         """ Build abstract search query for a simple category search.
129             This kind of search requires an additional geographic constraint.
130         """
131         if not sdata.housenumbers \
132            and ((self.details.viewbox and self.details.bounded_viewbox) or self.details.near):
133             yield dbs.PoiSearch(sdata)
134
135
136     def build_special_search(self, sdata: dbf.SearchData,
137                              address: List[TokenRange],
138                              is_category: bool) -> Iterator[dbs.AbstractSearch]:
139         """ Build abstract search queries for searches that do not involve
140             a named place.
141         """
142         if sdata.qualifiers:
143             # No special searches over qualifiers supported.
144             return
145
146         if sdata.countries and not address and not sdata.postcodes \
147            and self.configured_for_country:
148             yield dbs.CountrySearch(sdata)
149
150         if sdata.postcodes and (is_category or self.configured_for_postcode):
151             penalty = 0.0 if sdata.countries else 0.1
152             if address:
153                 sdata.lookups = [dbf.FieldLookup('nameaddress_vector',
154                                                  [t.token for r in address
155                                                   for t in self.query.get_partials_list(r)],
156                                                  lookups.Restrict)]
157                 penalty += 0.2
158             yield dbs.PostcodeSearch(penalty, sdata)
159
160
161     def build_housenumber_search(self, sdata: dbf.SearchData, hnrs: List[Token],
162                                  address: List[TokenRange]) -> Iterator[dbs.AbstractSearch]:
163         """ Build a simple address search for special entries where the
164             housenumber is the main name token.
165         """
166         sdata.lookups = [dbf.FieldLookup('name_vector', [t.token for t in hnrs], lookups.LookupAny)]
167         expected_count = sum(t.count for t in hnrs)
168
169         partials = [t for trange in address
170                        for t in self.query.get_partials_list(trange)]
171
172         if expected_count < 8000:
173             sdata.lookups.append(dbf.FieldLookup('nameaddress_vector',
174                                                  [t.token for t in partials], lookups.Restrict))
175         elif len(partials) != 1 or partials[0].count < 10000:
176             sdata.lookups.append(dbf.FieldLookup('nameaddress_vector',
177                                                  [t.token for t in partials], lookups.LookupAll))
178         else:
179             sdata.lookups.append(
180                 dbf.FieldLookup('nameaddress_vector',
181                                 [t.token for t
182                                  in self.query.get_tokens(address[0], TokenType.WORD)],
183                                 lookups.LookupAny))
184
185         sdata.housenumbers = dbf.WeightedStrings([], [])
186         yield dbs.PlaceSearch(0.05, sdata, expected_count)
187
188
189     def build_name_search(self, sdata: dbf.SearchData,
190                           name: TokenRange, address: List[TokenRange],
191                           is_category: bool) -> Iterator[dbs.AbstractSearch]:
192         """ Build abstract search queries for simple name or address searches.
193         """
194         if is_category or not sdata.housenumbers or self.configured_for_housenumbers:
195             ranking = self.get_name_ranking(name)
196             name_penalty = ranking.normalize_penalty()
197             if ranking.rankings:
198                 sdata.rankings.append(ranking)
199             for penalty, count, lookup in self.yield_lookups(name, address):
200                 sdata.lookups = lookup
201                 yield dbs.PlaceSearch(penalty + name_penalty, sdata, count)
202
203
204     def yield_lookups(self, name: TokenRange, address: List[TokenRange])\
205                           -> Iterator[Tuple[float, int, List[dbf.FieldLookup]]]:
206         """ Yield all variants how the given name and address should best
207             be searched for. This takes into account how frequent the terms
208             are and tries to find a lookup that optimizes index use.
209         """
210         penalty = 0.0 # extra penalty
211         name_partials = self.query.get_partials_list(name)
212         name_tokens = [t.token for t in name_partials]
213
214         addr_partials = [t for r in address for t in self.query.get_partials_list(r)]
215         addr_tokens = [t.token for t in addr_partials]
216
217         partials_indexed = all(t.is_indexed for t in name_partials) \
218                            and all(t.is_indexed for t in addr_partials)
219         exp_count = min(t.count for t in name_partials) / (2**(len(name_partials) - 1))
220
221         if (len(name_partials) > 3 or exp_count < 8000) and partials_indexed:
222             yield penalty, exp_count, dbf.lookup_by_names(name_tokens, addr_tokens)
223             return
224
225         # Partial term to frequent. Try looking up by rare full names first.
226         name_fulls = self.query.get_tokens(name, TokenType.WORD)
227         if name_fulls:
228             fulls_count = sum(t.count for t in name_fulls)
229             # At this point drop unindexed partials from the address.
230             # This might yield wrong results, nothing we can do about that.
231             if not partials_indexed:
232                 addr_tokens = [t.token for t in addr_partials if t.is_indexed]
233                 penalty += 1.2 * sum(t.penalty for t in addr_partials if not t.is_indexed)
234             # Any of the full names applies with all of the partials from the address
235             yield penalty, fulls_count / (2**len(addr_partials)),\
236                   dbf.lookup_by_any_name([t.token for t in name_fulls],
237                                          addr_tokens, fulls_count > 10000)
238
239         # To catch remaining results, lookup by name and address
240         # We only do this if there is a reasonable number of results expected.
241         exp_count = exp_count / (2**len(addr_partials)) if addr_partials else exp_count
242         if exp_count < 10000 and all(t.is_indexed for t in name_partials):
243             lookup = [dbf.FieldLookup('name_vector', name_tokens, lookups.LookupAll)]
244             if addr_tokens:
245                 lookup.append(dbf.FieldLookup('nameaddress_vector', addr_tokens, lookups.LookupAll))
246             penalty += 0.35 * max(0, 5 - len(name_partials) - len(addr_tokens))
247             yield penalty, exp_count, lookup
248
249
250     def get_name_ranking(self, trange: TokenRange) -> dbf.FieldRanking:
251         """ Create a ranking expression for a name term in the given range.
252         """
253         name_fulls = self.query.get_tokens(trange, TokenType.WORD)
254         ranks = [dbf.RankedTokens(t.penalty, [t.token]) for t in name_fulls]
255         ranks.sort(key=lambda r: r.penalty)
256         # Fallback, sum of penalty for partials
257         name_partials = self.query.get_partials_list(trange)
258         default = sum(t.penalty for t in name_partials) + 0.2
259         return dbf.FieldRanking('name_vector', default, ranks)
260
261
262     def get_addr_ranking(self, trange: TokenRange) -> dbf.FieldRanking:
263         """ Create a list of ranking expressions for an address term
264             for the given ranges.
265         """
266         todo: List[Tuple[int, int, dbf.RankedTokens]] = []
267         heapq.heappush(todo, (0, trange.start, dbf.RankedTokens(0.0, [])))
268         ranks: List[dbf.RankedTokens] = []
269
270         while todo: # pylint: disable=too-many-nested-blocks
271             neglen, pos, rank = heapq.heappop(todo)
272             for tlist in self.query.nodes[pos].starting:
273                 if tlist.ttype in (TokenType.PARTIAL, TokenType.WORD):
274                     if tlist.end < trange.end:
275                         chgpenalty = PENALTY_WORDCHANGE[self.query.nodes[tlist.end].btype]
276                         if tlist.ttype == TokenType.PARTIAL:
277                             penalty = rank.penalty + chgpenalty \
278                                       + max(t.penalty for t in tlist.tokens)
279                             heapq.heappush(todo, (neglen - 1, tlist.end,
280                                                   dbf.RankedTokens(penalty, rank.tokens)))
281                         else:
282                             for t in tlist.tokens:
283                                 heapq.heappush(todo, (neglen - 1, tlist.end,
284                                                       rank.with_token(t, chgpenalty)))
285                     elif tlist.end == trange.end:
286                         if tlist.ttype == TokenType.PARTIAL:
287                             ranks.append(dbf.RankedTokens(rank.penalty
288                                                           + max(t.penalty for t in tlist.tokens),
289                                                           rank.tokens))
290                         else:
291                             ranks.extend(rank.with_token(t, 0.0) for t in tlist.tokens)
292                         if len(ranks) >= 10:
293                             # Too many variants, bail out and only add
294                             # Worst-case Fallback: sum of penalty of partials
295                             name_partials = self.query.get_partials_list(trange)
296                             default = sum(t.penalty for t in name_partials) + 0.2
297                             ranks.append(dbf.RankedTokens(rank.penalty + default, []))
298                             # Bail out of outer loop
299                             todo.clear()
300                             break
301
302         ranks.sort(key=lambda r: len(r.tokens))
303         default = ranks[0].penalty + 0.3
304         del ranks[0]
305         ranks.sort(key=lambda r: r.penalty)
306
307         return dbf.FieldRanking('nameaddress_vector', default, ranks)
308
309
310     def get_search_data(self, assignment: TokenAssignment) -> Optional[dbf.SearchData]:
311         """ Collect the tokens for the non-name search fields in the
312             assignment.
313         """
314         sdata = dbf.SearchData()
315         sdata.penalty = assignment.penalty
316         if assignment.country:
317             tokens = self.query.get_tokens(assignment.country, TokenType.COUNTRY)
318             if self.details.countries:
319                 tokens = [t for t in tokens if t.lookup_word in self.details.countries]
320                 if not tokens:
321                     return None
322             sdata.set_strings('countries', tokens)
323         elif self.details.countries:
324             sdata.countries = dbf.WeightedStrings(self.details.countries,
325                                                   [0.0] * len(self.details.countries))
326         if assignment.housenumber:
327             sdata.set_strings('housenumbers',
328                               self.query.get_tokens(assignment.housenumber,
329                                                     TokenType.HOUSENUMBER))
330         if assignment.postcode:
331             sdata.set_strings('postcodes',
332                               self.query.get_tokens(assignment.postcode,
333                                                     TokenType.POSTCODE))
334         if assignment.qualifier:
335             tokens = self.query.get_tokens(assignment.qualifier, TokenType.QUALIFIER)
336             if self.details.categories:
337                 tokens = [t for t in tokens if t.get_category() in self.details.categories]
338                 if not tokens:
339                     return None
340             sdata.set_qualifiers(tokens)
341         elif self.details.categories:
342             sdata.qualifiers = dbf.WeightedCategories(self.details.categories,
343                                                       [0.0] * len(self.details.categories))
344
345         if assignment.address:
346             sdata.set_ranking([self.get_addr_ranking(r) for r in assignment.address])
347         else:
348             sdata.rankings = []
349
350         return sdata
351
352
353     def get_near_items(self, assignment: TokenAssignment) -> Optional[dbf.WeightedCategories]:
354         """ Collect tokens for near items search or use the categories
355             requested per parameter.
356             Returns None if no category search is requested.
357         """
358         if assignment.near_item:
359             tokens: Dict[Tuple[str, str], float] = {}
360             for t in self.query.get_tokens(assignment.near_item, TokenType.NEAR_ITEM):
361                 cat = t.get_category()
362                 # The category of a near search will be that of near_item.
363                 # Thus, if search is restricted to a category parameter,
364                 # the two sets must intersect.
365                 if (not self.details.categories or cat in self.details.categories)\
366                    and t.penalty < tokens.get(cat, 1000.0):
367                     tokens[cat] = t.penalty
368             return dbf.WeightedCategories(list(tokens.keys()), list(tokens.values()))
369
370         return None
371
372
373 PENALTY_WORDCHANGE = {
374     BreakType.START: 0.0,
375     BreakType.END: 0.0,
376     BreakType.PHRASE: 0.0,
377     BreakType.WORD: 0.1,
378     BreakType.PART: 0.2,
379     BreakType.TOKEN: 0.4
380 }