Skip to content

LSIF: Better fix for quadratic query

Warren Gifford requested to merge ef/better-fix into master

Created by: efritz

@efritz and @chrismwendt did some more research into the nearest-commit query performance, and to explain my findings, I'm naming the queries we've tried so far:

  • Q(quadratic) the query that was quadratic due to distance within the CTE
  • Q(slow linear) the current query which is linear in the number of commits visited (added in https://github.com/sourcegraph/sourcegraph/pull/5980)
  • Q(fast bounded) always takes the same amount of time regardless of distance from the target commit
  • Q(fast linear) uses 2 selects within the recursive term to avoid a disjunction in the join within the CTE (that's what caused Q(slow linear) to be slow) (adding in this PR)
  • Q(fast linear flood) same, but without directionality

All queries:

image (25)

Without quadratic (to zoom in):

image (26)

The sudden drops occur when the walk reaches a merge-base where the other branch has a much shorter distance to the target commit.

Without slow-linear (to zoom in) with fast-bounded limit 1,000:

image (27)

Same, but with fast-bounded limit 10,000:

image (28)

Same, but with fast-linear-flood:

image

Script and data: chart.tar.gz

Previous perf improvement: https://github.com/sourcegraph/sourcegraph/pull/5980

Merge request reports