browser/components/urlbar/docs/ranking.rst

   1 =======
   2 Ranking
   3 =======
   4
   5 Before results appear in the UrlbarView, they are fetched from providers.
   6
   7 Each `UrlbarProvider <https://firefox-source-docs.mozilla.org/browser/urlbar/overview.html#urlbarprovider>`_
   8 implements its own internal ranking and returns sorted results.
   9
  10 Externally all the results are ranked by the `UrlbarMuxer <https://searchfox.org/mozilla-central/source/browser/components/urlbar/UrlbarMuxerUnifiedComplete.sys.mjs>`_
  11 according to an hardcoded list of groups and sub-grups.
  12
  13 .. NOTE:: Preferences can influence the groups order, for example by putting
  14   Firefox Suggest before Search Suggestions.
  15
  16 The Places provider, responsible to return history and bookmark results, uses
  17 an internal ranking algorithm called Frecency.
  18
  19 Frecency implementation
  20 =======================
  21
  22 Frecency is a term derived from `frequency` and `recency`, its scope is to provide a
  23 ranking algorithm that gives importance both to how often a page is accessed and
  24 when it was last visited.
  25 Additionally, it accounts for the type of each visit through a bonus system.
  26
  27 To account for `recency`, a bucketing system is implemented.
  28 If a page has been visited later than the bucket cutoff, it gets the weight
  29 associated with that bucket:
  30
  31 - Up to 4 days old - weight 100 - ``places.frecency.firstBucketCutoff/Weight``
  32 - Up to 14 days old - weight 70 - ``places.frecency.secondBucketCutoff/Weight``
  33 - Up to 31 days old - weight 50 - ``places.frecency.thirdBucketCutoff/Weight``
  34 - Up to 90 days old - weight 30 - ``places.frecency.fourthBucketCutoff/Weight``
  35 - Anything else - weight 10 - ``places.frecency.defaultBucketWeight``
  36
  37 To account for `frequency`, the total number of visits to a page is used to
  38 calculate the final score.
  39
  40 The type of each visit is taken into account using specific bonuses:
  41
  42 Default bonus
  43   Any unknown type gets a default bonus. This is expected to be unused.
  44   Pref ``places.frecency.defaultVisitBonus`` current value: 0.
  45 Embed
  46   Used for embedded/framed visits not due to user actions. These visits today
  47   are stored in memory and never participate to frecency calculation.
  48   Thus this is currently unused.
  49   Pref ``places.frecency.embedVisitBonus`` current value: 0.
  50 Framed Link
  51   Used for cross-frame visits due to user action.
  52   Pref ``places.frecency.framedLinkVisitBonus`` current value: 0.
  53 Download
  54   Used for download visits. It’s important to support link coloring for these
  55   visits, but they are not necessarily useful address bar results (the Downloads
  56   view can do a better job with  these), so their frecency can be low.
  57   Pref ``places.frecency.downloadVisitBonus`` current value: 0.
  58 Reload
  59   Used for reload visits (refresh same page). Low because it should not be
  60   possible to influence frecency by multiple reloads.
  61   Pref ``places.frecency.reloadVisitBonus`` current value: 0.
  62 Redirect Source
  63   Used when the page redirects to another one.
  64   It’s a low value because we give more importance to the final destination,
  65   that is what the user actually visits, especially for permanent redirects.
  66   Pref ``places.frecency.redirectSourceVisitBonus`` current value: 25.
  67 Temporary Redirect
  68   Used for visits resulting from a temporary redirect (HTTP 307).
  69   Pref ``places.frecency.tempRedirectVisitBonus`` current value: 40.
  70 Permanent Redirect
  71   Used for visits resulting from a permanent redirect (HTTP 301). This is the
  72   new supposed destination for a url, thus the bonus is higher than temporary.
  73   In this case it may be advisable to just pick the bonus for the source visit.
  74   Pref ``places.frecency.permRedirectVisitBonus`` current value: 50.
  75 Bookmark
  76   Used for visits generated from bookmark views.
  77   Pref ``places.frecency.bookmarkVisitBonus`` current value: 75.
  78 Link
  79   Used for normal visits, for example when clicking on a link.
  80   Pref ``places.frecency.linkVisitBonus`` current value: 100.
  81 Typed
  82   Intended to be used for pages typed by the user, in reality it is used when
  83   the user picks a url from the UI (history views or the Address Bar).
  84   Pref ``places.frecency.typedVisitBonus`` current value: 2000.
  85
  86 The above bonuses are applied to visits, in addition to that there are also a
  87 few bonuses applied in case a page is not visited at all, both of these bonuses
  88 can be applied at the same time:
  89
  90 Unvisited bookmarked page
  91   Used for pages that are bookmarked but unvisited.
  92   Pref ``places.frecency.unvisitedBookmarkBonus`` current value: 140.
  93 Unvisited typed page
  94   Used for pages that were typed and now are bookmarked (otherwise they would
  95   be orphans).
  96   Pref ``places.frecency.unvisitedTypedBonus`` current value: 200.
  97
  98 Two special frecency values are also defined:
  99
 100 - ``-1`` represents a just inserted entry in the database, whose score has not
 101   been calculated yet.
 102 - ``0`` represents an entry for which a new value should not be calculated,
 103   because it has a poor user value (e.g. place: queries) among search results.
 104
 105 Finally, because calculating a score from all of the visits every time a new
 106 visit is added would be expensive, only a sample of the last 10
 107 (pref ``places.frecency.numVisits``) visits is used.
 108
 109 How frecency for a page is calculated
 110 -------------------------------------
 111
 112 .. mermaid::
 113     :align: center
 114     :caption: Frecency calculation flow
 115
 116     flowchart TD
 117         start[URL]
 118         a0{Has visits?}
 119         a1[Get last 10 visit]
 120         a2[bonus = unvisited_bonus + bookmarked + typed]
 121         a3{bonus > 0?}
 122         end0[Frecency = 0]
 123         end1["frecency = age_bucket_weight * (bonus / 100)"]
 124         a4[Sum points of all sampled visits]
 125         a5{points > 0?}
 126         end2[frecency = -1]
 127         end3["Frecency = visit_count * (points / sample_size)"]
 128         subgraph sub [Per each visit]
 129             sub0[bonus = visit_type_bonus]
 130             sub1{bookmarked?}
 131             sub2[add bookmark bonus]
 132             sub3["score = age_bucket_weight * (bonus / 100)"]
 133             sub0 --> sub1
 134             sub1 -- yes --> sub2
 135             sub1 -- no --> sub3
 136             sub2 --> sub3;
 137         end
 138         start --> a0
 139         a0 -- no --> a2
 140         a2 --> a3
 141         a3 -- no --> end0
 142         a3 -- yes --> end1
 143         a0 -- yes --> a1
 144         a1 --> sub
 145         sub --> a4
 146         a4 --> a5
 147         a5 -- no --> end2
 148         a5 -- yes --> end3
 149
 150 1. If the page is visited, get a sample of ``NUM_VISITS`` most recent visits.
 151 2. For each visit get a transition bonus, depending on the visit type.
 152 3. If the page is bookmarked, add to the bonus an additional bookmark bonus.
 153 4. If the bonus is positive, get a bucket weight depending on the visit date.
 154 5. Calculate points for the visit as ``age_bucket_weight * (bonus / 100)``.
 155 6. Sum points for all the sampled visits.
 156 7. If the points sum is zero, return a ``-1`` frecency, it will still appear in the UI.
 157    Otherwise, frecency is ``visitCount * points / NUM_VISITS``.
 158 8. If the page is unvisited and not bookmarked, or it’s a bookmarked place-query,
 159    return a ``0`` frecency, to hide it from the UI.
 160 9. If it’s bookmarked, add the bookmark bonus.
 161 10. If it’s also a typed page, add the typed bonus.
 162 11. Frecency is ``age_bucket_weight * (bonus / 100)``
 163
 164 When frecency for a page is calculated
 165 --------------------------------------
 166
 167 Operations that may influence the frecency score are:
 168
 169 * Adding visits
 170 * Removing visits
 171 * Adding bookmarks
 172 * Removing bookmarks
 173 * Changing the url of a bookmark
 174
 175 Frecency is recalculated:
 176
 177 * Immediately, when a new visit is added. The user expectation here is that the
 178   page appears in search results after being visited. This is also valid for
 179   any History API that allows to add visits.
 180 * In background on idle times, in any other case. In most cases having a
 181   temporarily stale value is not a problem, the main concern would be privacy
 182   when removing history of a page, but removing whole history will either
 183   completely remove the page or, if it's bookmarked, it will still be relevant.
 184   In this case, when a change influencing frecency happens, the ``recalc_frecency``
 185   database field for the page is set to ``1``.
 186
 187 Recalculation is done by the `PlacesFrecencyRecalculator <https://searchfox.org/mozilla-central/source/toolkit/components/places/PlacesFrecencyRecalculator.sys.mjs>`_ module.
 188 The Recalculator is notified when ``PlacesUtils.history.shouldStartFrecencyRecalculation``
 189 value changes from false to true, that means there's values to recalculate.
 190 A DeferredTask is armed, that will look for a user idle opportunity
 191 in the next 5 minutes, otherwise it will run when that time elapses.
 192 Once all the outdated values have been recalculated
 193 ``PlacesUtils.history.shouldStartFrecencyRecalculation`` is set back to false
 194 until the next operation invalidating a frecency.
 195 The recalculation task is also armed on the ``idle-daily`` notification.
 196
 197 When the task is executed, it recalculates frecency of a chunk of pages. If
 198 there are more pages left to recalculate, the task is re-armed. After frecency
 199 of a page is recalculated, its ``recalc_frecency`` field is set back to ``0``.
 200
 201 Frecency is also decayed daily during the ``idle-daily`` notification, by
 202 multiplying all the scores by a decay rate  of ``0.975`` (half-life of 28 days).
 203 This guarantees entries not receiving new visits or bookmarks lose relevancy.
 204
 205
 206 Adaptive Input History
 207 ======================
 208
 209 Input History (also known as Adaptive History) is a feature that allows to
 210 find urls that the user previously picked. To do so, it associates search strings
 211 with picked urls.
 212
 213 Adaptive results are usually presented before frecency derived results, making
 214 them appear as having an infinite frecency.
 215
 216 When the user types a given string, and picks a result from the address bar, that
 217 relation is stored and increases a use_count field for the given string.
 218 The use_count field asymptotically approaches a max of ``10`` (the update is
 219 done as ``use_count * .9 + 1``).
 220
 221 On querying, all the search strings that start with the input string are matched,
 222 a rank is calculated per each page as ``ROUND(MAX(use_count) * (1 + (input = :search_string)), 1)``,
 223 so that results perfectly matching the search string appear at the top.
 224 Results with the same rank are additionally sorted by descending frecency.
 225
 226 On daily idles, when frecency is decayed, also input history gets decayed, in
 227 particular the use_count field is multiplied by a decay rate  of ``0.975``.
 228 After decaying, any entry that has a ``use_count < 0.975^90 (= 0.1)`` is removed,
 229 thus entries are removed if unused for 90 days.