Skip to content

LSIF: Fix empty pages due to bloom filter

Warren Gifford requested to merge lsif-bloom-filter-empty-page into master

Created by: efritz

When looking for global references, we open (in chunks for pagination) the dumps which we know to import a given package. This does not mean that they include the symbol that we're searching for. In order to determine this, we do an application-level bloom filter check to see (with very high likelihood) whether or not the identifier we're looking for is one that the dump imported.

This works well, but has the effect of removing nearly all or all of the dumps from a page of results. This is very weird from a user perspective: they ask for a page of references at cursor c and are given an empty result set and a new cursor c+1.

This PR changes this flow so that the server instead re-queries more data from the database until an entire page's worth of dumps have passed the bloom filter test. This may add zero or more additional db queries in the backend for a single request. I don't think this is pathological (this change makes it better as we don't send multiple empty pages back to the client), and we can measure and determine if we need to select more from the db in order to batch some of this together as a performance enhancement.

This is a prerequisite to the implementation of RFC 58.

Merge request reports

Loading