Skip to main content

Search & Discovery

etchblok-test-api implements full-text search using an in-memory inverted index. This approach provides fast, token-based retrieval of bookmarks without the overhead of an external search engine, making it suitable for the application's current scale.

The Inverted Index Structure​

The core of the search functionality is the SearchIndex class located in app/services/search_service.py. It maintains an internal mapping (self._index) where each key is a unique token (word) and the value is a set of bookmark IDs containing that token.

class SearchIndex:
def __init__(self, repository: "BookmarkRepository") -> None:
self._repo = repository
self._index: Dict[str, Set[str]] = defaultdict(set)
self._rebuild()

On initialization, the index performs a full rebuild by fetching all bookmarks from the BookmarkRepository. This ensures that the in-memory state is synchronized with the persistent store whenever the service starts.

Tokenization and Preprocessing​

Before text is indexed or searched, it undergoes a tokenization process in the _tokenize method. This process ensures that searches are case-insensitive and focused on meaningful terms:

  1. Normalization: The text is converted to lowercase.
  2. Extraction: A regular expression [a-z0-9]+ is used to extract alphanumeric tokens.
  3. Filtering: Common "stop words" (e.g., "the", "and", "is") are removed to reduce index noise and improve relevance.

The _STOP_WORDS set is defined at the module level in app/services/search_service.py:

_STOP_WORDS: Set[str] = {"the", "a", "an", "and", "or", "but", "in", "on", "at", "to", "for", "is", "it"}

Search Execution and Ranking​

The search method implements an "AND" logic for multi-token queries. For a bookmark to match a query, it must contain all the tokens present in that query.

Intersection Logic​

The implementation starts with the set of IDs for the first token and iteratively performs an intersection with the sets for subsequent tokens:

candidate_ids: Set[str] = self._index.get(tokens[0], set()).copy()
for token in tokens[1:]:
candidate_ids &= self._index.get(token, set())

Relevance Ranking​

Once the matching bookmarks are retrieved from the repository, they are ranked using the _rank_results method. The ranking score is determined by the total number of times the query tokens appear in the bookmark's title and description combined:

def score(b: Bookmark) -> int:
text = f"{b.title} {b.description}".lower()
return sum(text.count(t) for t in tokens)

The results are then sorted in descending order of this score and truncated to the requested limit (defaulting to 20).

Lifecycle and Synchronization​

The SearchIndex is managed by the BookmarkService in app/services/bookmark_service.py. As a facade, BookmarkService ensures that the search index remains in sync with the database during write operations.

  • Creation: When create_bookmark is called, the new bookmark is immediately indexed via self._search.index_bookmark(bookmark).
  • Updates: When update_bookmark is called, the index is updated. The index_bookmark method handles this by first removing the old entries for that bookmark ID before re-indexing the updated title and description.
  • Deletion: While BookmarkService.delete_bookmark currently performs a soft-delete (trashing), the SearchIndex provides a remove_bookmark method that performs a full scan of the index to purge a bookmark ID from all token sets.

Design Tradeoffs​

The search implementation in etchblok-test-api involves several specific design choices:

  • In-Memory Nature: The index is entirely in-memory. While this provides extremely fast lookups, it means the index must be rebuilt from the database on every application restart.
  • AND-only Search: The requirement that all tokens must match simplifies the implementation but does not support "OR" queries or fuzzy matching.
  • Removal Performance: The _remove_bookmark_from_index method iterates over every token in the index to discard a bookmark ID. As the number of unique tokens grows, this operation becomes linearly more expensive.
  • Ranking Simplicity: The scoring mechanism treats matches in the title and description with equal weight, which may not always align with user expectations where title matches are typically more relevant.