commit c7d5c20f64c454f13fa18d596ade8c4bff2027a9
author manukh <manukh@chromium.org> Thu Oct 06 21:40:59 2022
committer Chromium LUCI CQ <chromium-scoped@luci-project-accounts.iam.gserviceaccount.com> Thu Oct 06 21:40:59 2022
tree 4002e0b571fe64b9c93b4eba908e15480ee96a28
parent 80d0f4e3c58baf9cb31d3afe5e7bceab9f92e608

[omnibox] [bookmark-paths] Add path index.

**Background**

`TitledUrlIndex` has an index mapping terms in bookmark titles and URLs
to the set of bookmarks containing those terms. This makes it quick to
find bookmarks title or URL matching a term.

The omnibox bookmark paths feature began matching bookmark paths as
well. E.g., the input 'myFolder google' can suggest a google bookmark in
a folder named 'myFolder'.

Before the bookmark paths feature, nodes returned had to title or URL
match every term in the input. We used the index to lookup title or URL
matches per term, and intersect those matches per term.

After the bookmark paths feature, nodes have to title, URL, or path
match every term in the input. We can no longer exclude nodes that don't
title or URL match a term since they may path match instead. Since we
don't index paths, we had to give the benefit of the doubt, and union
the the matches per term. We'd later iterate through them and make sure
all input terms are contained in their title, URL, or path.

Unioning the per term matches resulted in many more nodes than
intersecting. E.g., inputs containing 'www' or 'bookmark bar' would
return every bookmark (or up to a threshold). Processing this many more
(about 20x) nodes is expensive. We tried various optimizations, but none
were sufficient to reduce latency by 20x.

**This CL**

This CL indexes paths. This allows us to check if any of the input terms
are not contained in any paths; and if so, use intersection instead of
union. This guarantees the same results as before, because if an input
term wasn't contained in any paths, all returned nodes had to contain
that term in their titles or URLs. E.g., if the input is 'x y z', and
there are no folders containing 'x', we can simply return the nodes
title or URL matching 'x', rather than the union of nodes title or URL
matching any of 'x', 'y', or 'z'.

This doesn't require a full index (i.e. path term -> bookmarks) like we
have with titles and URLs; we just need a small index (path term -> # of
occurrences in paths). This is sufficient to check if each input term is
in any path. We track the # of occurrences so we can remove indexed
terms when folders are renamed or deleted. Unlike a full path index,
this index does not need to be updated when bookmarks or folders are
moved; it's only updated on folder creation, deletion, and rename.

This is feature guarded by `BookmarkIndexPaths`.

Adds metrics:
- Bookmarks.Memory.IndexMemoryAtStartup
    Will verify the index size isn't expensive.
- Bookmarks.UpdateTitledUrlIndex.[Add|Remove]
    Will measure the  latency of updating the existing title and URL
    index.
- Bookmarks.UpdateTitledUrlIndex.[Add|Remove]Path
    Will measure the  latency of updating the new path index.

Bug: 1129524, 1252537, 1143217
Change-Id: Ia743d284a5eb5d53cf0b9361f2eb6c1f1a21444c
Reviewed-on: https://chromium-review.googlesource.com/c/chromium/src/+/3932363
Reviewed-by: Scott Violet <sky@chromium.org>
Commit-Queue: manuk hovanesian <manukh@chromium.org>
Cr-Commit-Position: refs/heads/main@{#1056026}