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 Conversion 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.token: t.count 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                                                  list(partials), lookups.Restrict))
 175         elif len(partials) != 1 or list(partials.values())[0] < 10000:
 176             sdata.lookups.append(dbf.FieldLookup('nameaddress_vector',
 177                                                  list(partials), lookups.LookupAll))
 178         else:
 179             addr_fulls = [t.token for t
 180                           in self.query.get_tokens(address[0], TokenType.WORD)]
 181             if len(addr_fulls) > 5:
 182                 return
 183             sdata.lookups.append(
 184                 dbf.FieldLookup('nameaddress_vector', addr_fulls, lookups.LookupAny))
 185
 186         sdata.housenumbers = dbf.WeightedStrings([], [])
 187         yield dbs.PlaceSearch(0.05, sdata, expected_count)
 188
 189
 190     def build_name_search(self, sdata: dbf.SearchData,
 191                           name: TokenRange, address: List[TokenRange],
 192                           is_category: bool) -> Iterator[dbs.AbstractSearch]:
 193         """ Build abstract search queries for simple name or address searches.
 194         """
 195         if is_category or not sdata.housenumbers or self.configured_for_housenumbers:
 196             ranking = self.get_name_ranking(name)
 197             name_penalty = ranking.normalize_penalty()
 198             if ranking.rankings:
 199                 sdata.rankings.append(ranking)
 200             for penalty, count, lookup in self.yield_lookups(name, address):
 201                 sdata.lookups = lookup
 202                 yield dbs.PlaceSearch(penalty + name_penalty, sdata, count)
 203
 204
 205     def yield_lookups(self, name: TokenRange, address: List[TokenRange])\
 206                           -> Iterator[Tuple[float, int, List[dbf.FieldLookup]]]:
 207         """ Yield all variants how the given name and address should best
 208             be searched for. This takes into account how frequent the terms
 209             are and tries to find a lookup that optimizes index use.
 210         """
 211         penalty = 0.0 # extra penalty
 212         name_partials = {t.token: t for t in self.query.get_partials_list(name)}
 213
 214         addr_partials = [t for r in address for t in self.query.get_partials_list(r)]
 215         addr_tokens = list({t.token for t in addr_partials})
 216
 217         partials_indexed = all(t.is_indexed for t in name_partials.values()) \
 218                            and all(t.is_indexed for t in addr_partials)
 219         exp_count = min(t.count for t in name_partials.values()) / (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(list(name_partials.keys()), 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             if len(name_partials) == 1:
 230                 penalty += min(0.5, max(0, (exp_count - 50 * fulls_count) / (2000 * fulls_count)))
 231             if partials_indexed:
 232                 penalty += 1.2 * sum(t.penalty for t in addr_partials if not t.is_indexed)
 233
 234             yield penalty,fulls_count / (2**len(addr_tokens)), \
 235                   self.get_full_name_ranking(name_fulls, addr_partials,
 236                                              fulls_count > 30000 / max(1, len(addr_tokens)))
 237
 238         # To catch remaining results, lookup by name and address
 239         # We only do this if there is a reasonable number of results expected.
 240         exp_count = exp_count / (2**len(addr_tokens)) if addr_tokens else exp_count
 241         if exp_count < 10000 and all(t.is_indexed for t in name_partials.values()):
 242             penalty += 0.35 * max(1 if name_fulls else 0.1,
 243                                   5 - len(name_partials) - len(addr_tokens))
 244             yield penalty, exp_count,\
 245                   self.get_name_address_ranking(list(name_partials.keys()), addr_partials)
 246
 247
 248     def get_name_address_ranking(self, name_tokens: List[int],
 249                                  addr_partials: List[Token]) -> List[dbf.FieldLookup]:
 250         """ Create a ranking expression looking up by name and address.
 251         """
 252         lookup = [dbf.FieldLookup('name_vector', name_tokens, lookups.LookupAll)]
 253
 254         addr_restrict_tokens = []
 255         addr_lookup_tokens = []
 256         for t in addr_partials:
 257             if t.is_indexed:
 258                 if t.addr_count > 20000:
 259                     addr_restrict_tokens.append(t.token)
 260                 else:
 261                     addr_lookup_tokens.append(t.token)
 262
 263         if addr_restrict_tokens:
 264             lookup.append(dbf.FieldLookup('nameaddress_vector',
 265                                           addr_restrict_tokens, lookups.Restrict))
 266         if addr_lookup_tokens:
 267             lookup.append(dbf.FieldLookup('nameaddress_vector',
 268                                           addr_lookup_tokens, lookups.LookupAll))
 269
 270         return lookup
 271
 272
 273     def get_full_name_ranking(self, name_fulls: List[Token], addr_partials: List[Token],
 274                               use_lookup: bool) -> List[dbf.FieldLookup]:
 275         """ Create a ranking expression with full name terms and
 276             additional address lookup. When 'use_lookup' is true, then
 277             address lookups will use the index, when the occurences are not
 278             too many.
 279         """
 280         # At this point drop unindexed partials from the address.
 281         # This might yield wrong results, nothing we can do about that.
 282         if use_lookup:
 283             addr_restrict_tokens = []
 284             addr_lookup_tokens = []
 285             for t in addr_partials:
 286                 if t.is_indexed:
 287                     if t.addr_count > 20000:
 288                         addr_restrict_tokens.append(t.token)
 289                     else:
 290                         addr_lookup_tokens.append(t.token)
 291         else:
 292             addr_restrict_tokens = [t.token for t in addr_partials if t.is_indexed]
 293             addr_lookup_tokens = []
 294
 295         return dbf.lookup_by_any_name([t.token for t in name_fulls],
 296                                       addr_restrict_tokens, addr_lookup_tokens)
 297
 298
 299     def get_name_ranking(self, trange: TokenRange,
 300                          db_field: str = 'name_vector') -> dbf.FieldRanking:
 301         """ Create a ranking expression for a name term in the given range.
 302         """
 303         name_fulls = self.query.get_tokens(trange, TokenType.WORD)
 304         ranks = [dbf.RankedTokens(t.penalty, [t.token]) for t in name_fulls]
 305         ranks.sort(key=lambda r: r.penalty)
 306         # Fallback, sum of penalty for partials
 307         name_partials = self.query.get_partials_list(trange)
 308         default = sum(t.penalty for t in name_partials) + 0.2
 309         return dbf.FieldRanking(db_field, default, ranks)
 310
 311
 312     def get_addr_ranking(self, trange: TokenRange) -> dbf.FieldRanking:
 313         """ Create a list of ranking expressions for an address term
 314             for the given ranges.
 315         """
 316         todo: List[Tuple[int, int, dbf.RankedTokens]] = []
 317         heapq.heappush(todo, (0, trange.start, dbf.RankedTokens(0.0, [])))
 318         ranks: List[dbf.RankedTokens] = []
 319
 320         while todo: # pylint: disable=too-many-nested-blocks
 321             neglen, pos, rank = heapq.heappop(todo)
 322             for tlist in self.query.nodes[pos].starting:
 323                 if tlist.ttype in (TokenType.PARTIAL, TokenType.WORD):
 324                     if tlist.end < trange.end:
 325                         chgpenalty = PENALTY_WORDCHANGE[self.query.nodes[tlist.end].btype]
 326                         if tlist.ttype == TokenType.PARTIAL:
 327                             penalty = rank.penalty + chgpenalty \
 328                                       + max(t.penalty for t in tlist.tokens)
 329                             heapq.heappush(todo, (neglen - 1, tlist.end,
 330                                                   dbf.RankedTokens(penalty, rank.tokens)))
 331                         else:
 332                             for t in tlist.tokens:
 333                                 heapq.heappush(todo, (neglen - 1, tlist.end,
 334                                                       rank.with_token(t, chgpenalty)))
 335                     elif tlist.end == trange.end:
 336                         if tlist.ttype == TokenType.PARTIAL:
 337                             ranks.append(dbf.RankedTokens(rank.penalty
 338                                                           + max(t.penalty for t in tlist.tokens),
 339                                                           rank.tokens))
 340                         else:
 341                             ranks.extend(rank.with_token(t, 0.0) for t in tlist.tokens)
 342                         if len(ranks) >= 10:
 343                             # Too many variants, bail out and only add
 344                             # Worst-case Fallback: sum of penalty of partials
 345                             name_partials = self.query.get_partials_list(trange)
 346                             default = sum(t.penalty for t in name_partials) + 0.2
 347                             ranks.append(dbf.RankedTokens(rank.penalty + default, []))
 348                             # Bail out of outer loop
 349                             todo.clear()
 350                             break
 351
 352         ranks.sort(key=lambda r: len(r.tokens))
 353         default = ranks[0].penalty + 0.3
 354         del ranks[0]
 355         ranks.sort(key=lambda r: r.penalty)
 356
 357         return dbf.FieldRanking('nameaddress_vector', default, ranks)
 358
 359
 360     def get_search_data(self, assignment: TokenAssignment) -> Optional[dbf.SearchData]:
 361         """ Collect the tokens for the non-name search fields in the
 362             assignment.
 363         """
 364         sdata = dbf.SearchData()
 365         sdata.penalty = assignment.penalty
 366         if assignment.country:
 367             tokens = self.get_country_tokens(assignment.country)
 368             if not tokens:
 369                 return None
 370             sdata.set_strings('countries', tokens)
 371         elif self.details.countries:
 372             sdata.countries = dbf.WeightedStrings(self.details.countries,
 373                                                   [0.0] * len(self.details.countries))
 374         if assignment.housenumber:
 375             sdata.set_strings('housenumbers',
 376                               self.query.get_tokens(assignment.housenumber,
 377                                                     TokenType.HOUSENUMBER))
 378         if assignment.postcode:
 379             sdata.set_strings('postcodes',
 380                               self.query.get_tokens(assignment.postcode,
 381                                                     TokenType.POSTCODE))
 382         if assignment.qualifier:
 383             tokens = self.get_qualifier_tokens(assignment.qualifier)
 384             if not tokens:
 385                 return None
 386             sdata.set_qualifiers(tokens)
 387         elif self.details.categories:
 388             sdata.qualifiers = dbf.WeightedCategories(self.details.categories,
 389                                                       [0.0] * len(self.details.categories))
 390
 391         if assignment.address:
 392             if not assignment.name and assignment.housenumber:
 393                 # housenumber search: the first item needs to be handled like
 394                 # a name in ranking or penalties are not comparable with
 395                 # normal searches.
 396                 sdata.set_ranking([self.get_name_ranking(assignment.address[0],
 397                                                          db_field='nameaddress_vector')]
 398                                   + [self.get_addr_ranking(r) for r in assignment.address[1:]])
 399             else:
 400                 sdata.set_ranking([self.get_addr_ranking(r) for r in assignment.address])
 401         else:
 402             sdata.rankings = []
 403
 404         return sdata
 405
 406
 407     def get_country_tokens(self, trange: TokenRange) -> List[Token]:
 408         """ Return the list of country tokens for the given range,
 409             optionally filtered by the country list from the details
 410             parameters.
 411         """
 412         tokens = self.query.get_tokens(trange, TokenType.COUNTRY)
 413         if self.details.countries:
 414             tokens = [t for t in tokens if t.lookup_word in self.details.countries]
 415
 416         return tokens
 417
 418
 419     def get_qualifier_tokens(self, trange: TokenRange) -> List[Token]:
 420         """ Return the list of qualifier tokens for the given range,
 421             optionally filtered by the qualifier list from the details
 422             parameters.
 423         """
 424         tokens = self.query.get_tokens(trange, TokenType.QUALIFIER)
 425         if self.details.categories:
 426             tokens = [t for t in tokens if t.get_category() in self.details.categories]
 427
 428         return tokens
 429
 430
 431     def get_near_items(self, assignment: TokenAssignment) -> Optional[dbf.WeightedCategories]:
 432         """ Collect tokens for near items search or use the categories
 433             requested per parameter.
 434             Returns None if no category search is requested.
 435         """
 436         if assignment.near_item:
 437             tokens: Dict[Tuple[str, str], float] = {}
 438             for t in self.query.get_tokens(assignment.near_item, TokenType.NEAR_ITEM):
 439                 cat = t.get_category()
 440                 # The category of a near search will be that of near_item.
 441                 # Thus, if search is restricted to a category parameter,
 442                 # the two sets must intersect.
 443                 if (not self.details.categories or cat in self.details.categories)\
 444                    and t.penalty < tokens.get(cat, 1000.0):
 445                     tokens[cat] = t.penalty
 446             return dbf.WeightedCategories(list(tokens.keys()), list(tokens.values()))
 447
 448         return None
 449
 450
 451 PENALTY_WORDCHANGE = {
 452     BreakType.START: 0.0,
 453     BreakType.END: 0.0,
 454     BreakType.PHRASE: 0.0,
 455     BreakType.WORD: 0.1,
 456     BreakType.PART: 0.2,
 457     BreakType.TOKEN: 0.4
 458 }