Skip to content

LSIF: Fix reference pagination limits

Administrator requested to merge lsif-improve-ref-pagination into master

Created by: efritz

When testing with an index of momentjs/moment, we discovered that the index contains symbols with ~16k references (both reference-result and moniker-based). This caused a page to include tens of thousands of results that need to be resolved by the GraphQL API before a response is sent to the user. This was relatively efficient, but caused the UI to choke when it tried to render 32,000 elements in the references panel.

The old way we paginated references was to:

  • find ranges under the cursor
  • for each range:
    • append all reference results in the graph attached to that range to the result set
    • find all monikers attached to that range
    • for each moniker:
      • append the rows in the references table matching that moniker to the result set
      • if the moniker is an import, find the dump that defines the moniker and append the rows in its references table matching that moniker to the result set
      • (xrefs) find a batch of dumps that reference this package and identifier
        • for each dump in the batch, append the rows in their references table matching the moniker to the result set
  • return the above as the first page
  • for subsequent pages, repeat the last xrefs step

The new way we paginate references is to encode the phases of the result set into a state machine. The execution of each phase is dictated by the shape of the pagination cursor. The phases are:

  • find references in the current dump
  • find references in the definition dump
  • find references in different dumps of the same repo
  • find references in different dumps of different repos

Each phase can be executed partially (with a decreased limit), and partial phases can be executed more than once per request in order to fill an entire page.

Merge request reports