1317543 - Improve history panel query speed

Status: RESOLVED FIXED

(Firefox for iOS :: Data Storage, enhancement, P3)

Description

[Richard Newman [:rnewman]]

With my full Sync history imported, it takes two seconds to populate this list. That's a lot for 100 items.

Comment 1

[Richard Newman [:rnewman]]

Some direction:

The reason the query is slow is that it walks history, filtering out deleted items, joining against domains and visits, grouping, paring out unvisited items… then finally orders and limits.

2|0|0|SCAN TABLE history
2|1|1|SEARCH TABLE domains USING INTEGER PRIMARY KEY (rowid=?)
2|2|2|SEARCH TABLE visits USING COVERING INDEX idx_visits_siteID_is_local_date (siteID=?)
1|0|0|SCAN SUBQUERY 2
1|0|0|USE TEMP B-TREE FOR GROUP BY
1|0|0|USE TEMP B-TREE FOR ORDER BY
4|0|0|SCAN TABLE favicon_sites USING COVERING INDEX sqlite_autoindex_favicon_sites_1
4|1|1|SEARCH TABLE favicons USING INTEGER PRIMARY KEY (rowid=?)
3|0|0|SCAN TABLE history USING COVERING INDEX sqlite_autoindex_history_2
3|1|1|SEARCH SUBQUERY 4 USING AUTOMATIC COVERING INDEX (siteID=?)
0|0|0|SCAN SUBQUERY 1
0|1|1|SEARCH SUBQUERY 3 USING AUTOMATIC COVERING INDEX (id=?)


When we have lots of history, what we should do is invert this: walk the visits table in descending order (which handily excludes unvisited history), searching into history/domains by ID, filtering by URL, and then fleshing out whatever else we need by joining back against the visits table and icons.

This should get us into an index walk on visits, rather than a table scan on history, and allow us to scale to very large quantities of history.

Note, however, that there are two kinds of history lookup: by visit descending, and by frecency with a URL/title match. The latter can still be improved (it's slow, but hard to tell), but won't benefit from walking the visits index.

Here's some code to explain a query within Firefox itself:


    private func explain(query: String, args: Args?) {
        db.runQuery("EXPLAIN QUERY PLAN " + query, args: args, factory: { row -> String in
            log.debug("\(row[0] as! Int)|\(row[2] as! Int)|\(row[2] as! Int)|\(row[3] as! String)")
            return ""
        })
    }


Used like this:

            ...
            let factory = SQLiteHistory.iconHistoryColumnFactory

            self.explain(sql, args: args)             // Tada!

            return db.runQuery(sql, args: args, factory: factory)

Comment 2

[Justin D'Arcangelo [:justindarc]]

Taking to investigate.

Comment 3

[Justin D'Arcangelo [:justindarc]]

For reference, here's the query:

SELECT
  historyID, url, title, guid, domain_id, domain, localVisitDate, remoteVisitDate, visitCount,
  iconID, iconURL, iconDate, iconType, iconWidth
FROM (
  SELECT
    historyID, url, title, guid, domain_id, domain, visitCount,
    max(localVisitDate) AS localVisitDate,
    max(remoteVisitDate) AS remoteVisitDate
  FROM (
    SELECT
      history.id AS historyID, history.url AS url, title, guid, domain_id, domain,
      COALESCE(max(case visits.is_local when 1 then visits.date else 0 end), 0) AS localVisitDate,
      COALESCE(max(case visits.is_local when 0 then visits.date else 0 end), 0) AS remoteVisitDate,
      COALESCE(count(visits.is_local), 0) AS visitCount
    FROM
      history
        INNER JOIN domains ON
          domains.id = history.domain_id
        INNER JOIN visits ON
          visits.siteID = history.id
    WHERE (history.is_deleted = 0)
    GROUP BY historyID
  )
  WHERE (visitCount > 0)
  GROUP BY historyID
  ORDER BY max(localVisitDate, remoteVisitDate) DESC
  LIMIT 100
) LEFT OUTER JOIN view_history_id_favicon ON historyID = view_history_id_favicon.id

Comment 4

[Justin D'Arcangelo [:justindarc]]

Attachment: WIP GitHub Pull Request

Richard, this PR is not by any means complete. However, I wanted to see if you could give it a try with your dataset and see if there's any noticeable improvement. Here's the explain plan for the query that populates the history panel using this patch:

2|0|0|SCAN TABLE favicon_sites USING COVERING INDEX sqlite_autoindex_favicon_sites_1
2|1|1|SEARCH TABLE favicons USING INTEGER PRIMARY KEY (rowid=?)
1|0|0|SCAN TABLE history USING COVERING INDEX sqlite_autoindex_history_2
1|1|1|SEARCH SUBQUERY 2 USING AUTOMATIC COVERING INDEX (siteID=?)
0|0|0|SCAN TABLE history
0|1|1|SEARCH TABLE domains USING INTEGER PRIMARY KEY (rowid=?)
0|2|2|SEARCH TABLE visits USING COVERING INDEX idx_visits_siteID_is_local_date (siteID=?)
0|3|3|SEARCH SUBQUERY 1 USING AUTOMATIC COVERING INDEX (id=?)
0|0|0|USE TEMP B-TREE FOR ORDER BY

Comment 5

[Justin D'Arcangelo [:justindarc]]

Attachment: GitHub Pull Request

I'm unable to flag :rnewman for review, but here's an updated PR that's in better shape than the last one.

Comment 6

[Richard Newman [:rnewman]]

My suggested approach:

Get SQLite to walk visits in descending date order. No need for a limit here.

Join that against history, grouping by site ID. This will introduce a btree in order to group, but the basic loop is still a walk on the visits index.

Limit this query.

Join that result to favicons.

The big change here is that instead of starting with history, and looking at visits to find which history is recent (and collecting a bunch of metadata!), we'd look at the visits index to find the most recent items in visit order.

Comment 7

[Richard Newman [:rnewman]]

Comment on attachment 8871891 [details] [review]
GitHub Pull Request

r+ with the printf tidied up!

Comment 8

[Justin D'Arcangelo [:justindarc]]

Landed on master:

https://github.com/mozilla-mobile/firefox-ios/commit/68c16e35d97091778034cc465304756334465c20

Landed on v8.x:

https://github.com/mozilla-mobile/firefox-ios/commit/bd907b5fe6582f260f71dc66b3254d4c1a997fdd