search: call zoekt early #14093

stefanhengl · 2020-09-23T09:52:42Z

For global queries, we call zoekt before resolving and splitting repositories. The scope of this PR is limited to file and path results for literal search without version contexts.

Why?
traces of global queries shows that a significant amount of time is spent on handling large lists of repository references. Specifically, we spent a lot of time on:

resolving
splitting
serializing

For global queries, we can save time, because zoekt can simply search all shards without having to match them against a list of indexed repositories.

We still have to filter the results coming from zoekt to make sure the user sees only repositories she has access to.

keegancsmith

However, determineRepos can return an alert (ie a resolver), which doResults can handle, but zoekt.go cannot. For a cleaner implementation with futures I suggest we refactor doResults and all functions in its call-hierarchy to return simple errors which are then converted to alerts somewhere higher in the call-chain.

Agreed this is very strange that it returns a resolver. I agree with your suggested solution, it shouldn't be returning a resolver but maybe some informative error or even a third type which is more alert specific that zoekt could ignore?

What are your thoughts on landing this code? Do you feel comfortable with how this is implemented from a coupling/future maintainability perspective? I'm a little unsure. However, it feels like if we only access repos via a promise + we have this mode flag feels good. I wonder if there is a way to change this a bit to prevent mistakes when making other changes in the future and not being aware of mode?

keegancsmith · 2020-09-23T11:57:16Z

cmd/frontend/graphqlbackend/search_results.go

@@ -1729,12 +1735,14 @@ func (r *searchResolver) doResults(ctx context.Context, forceOnlyResultType stri

 	args := search.TextParameters{
 		PatternInfo:     p,
-		Repos:           resolved.repoRevs,


cool, makes sense you removed this. Is it possible that replacing this with just a chan may lead to issues where we try and read this channel more than once? Should we be using a little promise wrapper that has an idempotent implementation?

IE should we remove Repos from TextParameters completely and replace it with something promise like only?

I have updated the PR, now with Repos removed from TextParameters completely. I still have to make the new Get context-aware, though.

keegancsmith · 2020-09-23T12:01:42Z

cmd/frontend/graphqlbackend/search_results.go

+	}
+	args.Repos = resolved.repoRevs
+	if r.isGlobalSearch() {
+		args.RepoPromise <- resolved.repoRevs


you could just always send on this channel?

keegancsmith · 2020-09-23T12:04:10Z

cmd/frontend/graphqlbackend/search_results.go

+		wg.Add(1)
+		goroutine.Go(func() {
+			defer wg.Done()
+			agg.doFilePathSearch(ctx, &argsIndexed)


right now this ctx will be canceled if we return due to error while resolving repos. This is good, but feels like something we could regress on in the future. Maybe to just be explicit we should have a context.WithCancel in this conditional to keep that behaviour.

keegancsmith · 2020-09-23T12:04:49Z

cmd/frontend/graphqlbackend/zoekt.go

@@ -292,14 +294,21 @@ var errNoResultsInTimeout = errors.New("no results found in specified timeout")
 // case of finding partial or full results in the given timeout).
 func zoektSearch(ctx context.Context, args *search.TextParameters, repos *indexedRepoRevs, typ indexedRequestType, since func(t time.Time) time.Duration) (fm []*FileMatchResolver, limitHit bool, reposLimitHit map[string]struct{}, err error) {
 	if len(repos.repoRevs) == 0 {
-		return nil, false, nil, nil
+		if args == nil || args.Mode != search.ZoektGlobalSearch {


maybe combine this with the above line? Also why would args be nil? Just in tests? Maybe we should fix those tests.

yeah, its the tests ;-) Let me see if I can change the tests instead.

Edit: I was wrong. It is not just the tests. NewIndexedSearchRequest will return args=nil if for some reason we decide to return early.

keegancsmith · 2020-09-23T12:07:42Z

cmd/frontend/graphqlbackend/zoekt.go

+		select {
+		case <-ctx.Done():
+			return nil, false, nil, ctx.Err()
+		case repos := <-args.RepoPromise:


I wonder if in this case we can set something which does the same thing as GetRepoInputRev, then we can potentially get rid of the branching between ZoektGlobalSearch in the for loop over resp.Files below.

eg maybe we set a function var getRepoInputRev(*zoekt.FileMatch) (repo *types.Repo, revs []string, ok bool)?

internal/search/types.go

codecov · 2020-09-24T10:23:45Z

Codecov Report

Merging #14093 into main will decrease coverage by 1.14%.
The diff coverage is 68.57%.

@@            Coverage Diff             @@
##             main   #14093      +/-   ##
==========================================
- Coverage   47.73%   46.58%   -1.15%     
==========================================
  Files        1524     1524              
  Lines       77640    77747     +107     
  Branches     6934     6934              
==========================================
- Hits        37058    36218     -840     
- Misses      36963    37902     +939     
- Partials     3619     3627       +8

Flag	Coverage Δ		*Carryforward flag
#go	`51.89% <68.57%> (+0.03%)`	⬆️
#storybook	`?`
#typescript	`33.91% <ø> (-3.98%)`	⬇️	Carriedforward from d082943
#unit	`33.91% <ø> (ø)`		Carriedforward from d082943

*This pull request uses carry forward flags. Click here to find out more.

Impacted Files	Coverage Δ
cmd/frontend/graphqlbackend/search_pagination.go	`47.16% <0.00%> (-0.55%)`	⬇️
cmd/frontend/graphqlbackend/search_symbols.go	`9.60% <0.00%> (-0.13%)`	⬇️
cmd/frontend/graphqlbackend/search_results.go	`52.85% <65.11%> (+0.83%)`	⬆️
cmd/frontend/graphqlbackend/zoekt.go	`74.55% <68.29%> (-2.21%)`	⬇️
cmd/frontend/graphqlbackend/search_repositories.go	`74.69% <71.42%> (-1.26%)`	⬇️
cmd/frontend/graphqlbackend/search.go	`66.61% <75.00%> (+0.05%)`	⬆️
cmd/frontend/graphqlbackend/textsearch.go	`67.21% <76.00%> (+1.22%)`	⬆️
cmd/frontend/graphqlbackend/search_suggestions.go	`72.11% <100.00%> (ø)`
internal/search/types.go	`30.43% <100.00%> (+30.43%)`	⬆️
...nterprise/cmd/frontend/auth/httpheader/provider.go	`0.00% <0.00%> (-20.00%)`	⬇️
... and 777 more

keegancsmith

LGTM. I may send up some commits in another PR for you to take a look at around simplifying the promise. Tell me what ya think :)

keegancsmith · 2020-09-29T08:01:02Z

cmd/frontend/graphqlbackend/search_pagination.go

@@ -251,16 +251,21 @@ func repoIsLess(i, j *types.Repo) bool {
 //    2 above (in the worst case scenario).
 //
 func paginatedSearchFilesInRepos(ctx context.Context, args *search.TextParameters, pagination *searchPaginationInfo) (*searchCursor, []SearchResultResolver, *searchResultsCommon, error) {
+	repos, err := args.RepoPromise.Get(ctx)
+	if err != nil {
+		log15.Info("paginatedSearchFilesInRepos: context error while getting repos.")


shouldn't we be returning an error here?

Not 100%. sure. The comment in line 270 implies we shouldn't, although I find it a bit strange.

// Timeouts are reported through searchResultsCommon so don't report an error for them

edit: returning an error now

keegancsmith · 2020-09-29T08:02:47Z

cmd/frontend/graphqlbackend/search_results.go

@@ -1464,7 +1464,7 @@ func (r *searchResolver) determineRepos(ctx context.Context, tr *trace.Trace, st
 // diff and commit searches where more than repoLimit repos need to be searched.
 func alertOnSearchLimit(resultTypes []string, args *search.TextParameters) ([]string, *searchAlert) {
 	limits := searchLimits()
-
+	repos, _ := args.RepoPromise.Get(context.Background())


why can we ignore the error?

The only error that can come back is a context error which at this point (inside alertOnSearchLimit) seemed irrelevant to me.

Edit: And, we don't have a context here, so we cannot even get a context error ;-)

keegancsmith · 2020-09-29T08:04:54Z

cmd/frontend/graphqlbackend/zoekt.go

-	finalQuery := zoektquery.NewAnd(&zoektquery.RepoBranches{Set: repos.repoBranches}, queryExceptRepos)
+	var finalQuery zoektquery.Q
+	if args.Mode == search.ZoektGlobalSearch {
+		finalQuery = zoektquery.NewAnd(&zoektquery.Branch{Pattern: "HEAD", Exact: true}, queryExceptRepos)


some code comments here I think would be useful for future travellers :)

keegancsmith · 2020-09-29T08:06:59Z

internal/search/types.go

+// Get returns the repository revisions. It blocks until the promise resolves or
+// the context is canceled. Further calls to Get will always return the original
+// results, IE err will stay nil even if the context expired between the first
+// and the second call.


should also document that if the first calls ctx finishes while resolving, then we will always return that ctx.Error

keegancsmith · 2020-09-29T08:23:17Z

@stefanhengl now that I played with the promise code I have some extra feedback. How do we resolve an error in the promise? I think we need a way to cancel the promise with error if resolving fails. See below it just needs to also store the error in resolve to work. The implementation below always respects the past in ctx and doesn't need a New method since it will init the channel when needed

diff --git a/internal/search/types.go b/internal/search/types.go
index a911a8822f..a58d28ab46 100644
--- a/internal/search/types.go
+++ b/internal/search/types.go
@@ -82,20 +82,22 @@ const (
 // channel. However, unlike a channel, a RepoPromise can only be set once, but
 // consumed many times. Use Resolve to set the value, and Get to get the value.
 type RepoPromise struct {
-	closeOnce sync.Once
-	repoChan  chan []*RepositoryRevisions
+	initOnce sync.Once
+	done     chan struct{}
 
-	resolveOnce sync.Once
-	repos       []*RepositoryRevisions
-
-	err error
+	reposOnce sync.Once
+	repos     []*RepositoryRevisions
 }
 
 // NewRepoPromise returns an unresolved promise.
 func NewRepoPromise() *RepoPromise {
-	return &RepoPromise{
-		repoChan: make(chan []*RepositoryRevisions, 1),
-	}
+	return &RepoPromise{}
+}
+
+func (rp *RepoPromise) init() {
+	rp.initOnce.Do(func() {
+		rp.done = make(chan struct{})
+	})
 }
 
 // Get returns the repository revisions. It blocks until the promise resolves or
@@ -103,22 +105,22 @@ func NewRepoPromise() *RepoPromise {
 // results, IE err will stay nil even if the context expired between the first
 // and the second call.
 func (rp *RepoPromise) Get(ctx context.Context) ([]*RepositoryRevisions, error) {
-	rp.resolveOnce.Do(func() {
-		select {
-		case <-ctx.Done():
-			rp.err = ctx.Err()
+	rp.init()
+	select {
+	case <-ctx.Done():
+		return nil, ctx.Err()
 
-		case rp.repos = <-rp.repoChan:
-		}
-	})
-	return rp.repos, rp.err
+	case <-rp.done:
+		return rp.repos, nil
+	}
 }
 
 // Resolve returns a promise that is resolved with a given value.
 func (rp *RepoPromise) Resolve(repos []*RepositoryRevisions) *RepoPromise {
-	rp.closeOnce.Do(func() {
-		rp.repoChan <- repos
-		close(rp.repoChan)
+	rp.reposOnce.Do(func() {
+		rp.init()
+		rp.repos = repos
+		close(rp.done)
 	})
 	return rp
 }

To make it clearer, we could even factor the promise out with interface and then create a type safe wrapper.

keegancsmith · 2020-09-29T08:28:31Z

Can't help myself since this is fun code to write, but here is an interface{} based promise

type Promise struct {
	initOnce sync.Once
	done     chan struct{}

	valueOnce sync.Once
	value     interface{}
}

func (p *Promise) init() {
	p.initOnce.Do(func() { p.done = make(chan struct{}) })
}

func (p *Promise) Resolve(v interface{}) {
	p.valueOnce.Do(func() {
		p.init()
		p.value = v
		close(p.done)
	})
}

func (p *Promise) Get(ctx context.Context) (interface{}, error) {
	p.init()
	select {
	case <-ctx.Done():
		return nil, ctx.Err()

	case <-p.done:
		return p.value, nil
	}
}

sourcegraph-bot · 2020-09-29T08:32:41Z

Notifying subscribers in CODENOTIFY files for diff d082943...a9d31f1.

Notify	File(s)
@keegancsmith	cmd/frontend/graphqlbackend/search.go cmd/frontend/graphqlbackend/search_pagination.go cmd/frontend/graphqlbackend/search_repositories.go cmd/frontend/graphqlbackend/search_repositories_test.go cmd/frontend/graphqlbackend/search_results.go cmd/frontend/graphqlbackend/search_results_test.go cmd/frontend/graphqlbackend/search_suggestions.go cmd/frontend/graphqlbackend/search_suggestions_test.go cmd/frontend/graphqlbackend/search_symbols.go cmd/frontend/graphqlbackend/search_test.go cmd/frontend/graphqlbackend/textsearch.go cmd/frontend/graphqlbackend/textsearch_test.go cmd/frontend/graphqlbackend/zoekt.go cmd/frontend/graphqlbackend/zoekt_test.go internal/search/types.go internal/search/types_test.go

stefanhengl · 2020-09-29T11:29:39Z

internal/search/types.go

+// will stay nil even if the context expired between the first and the second
+// call.
+func (p *Promise) Get(ctx context.Context) (interface{}, error) {
+	p.getOnce.Do(func() {


we need getOnce to make sure that we don't run the select block twice. In case the context is canceled AND p.done is closed, the select block will randomly return either nil or ctx.Err().

you don't need the getOnce. you can always select on p.done, don't need to only do it once. Thats the reason why in the promise impl I did I switched away from sending the value down the channel and instead just relied on done channel.

stefanhengl · 2020-09-29T11:31:23Z

internal/search/types.go

+}
+
+// Resolve returns a promise that is resolved with a given value.
+func (p *Promise) Resolve(v interface{}) *Promise {


Returning *Promise from Resolve is not really necessary, but it lets us write code like this p:=&Promise{}.Resolve which is nice.

update promise implementation

stefanhengl · 2020-09-29T12:26:40Z

@keegancsmith I slightly modified your suggestion for an interface{} based promise, hence running by you again.

keegancsmith

Lets get this out. One inline comment about the promise impl. Nice stuff

keegancsmith · 2020-09-29T15:36:42Z

internal/search/types.go

+// will stay nil even if the context expired between the first and the second
+// call.
+func (p *Promise) Get(ctx context.Context) (interface{}, error) {
+	p.getOnce.Do(func() {


you don't need the getOnce. you can always select on p.done, don't need to only do it once. Thats the reason why in the promise impl I did I switched away from sending the value down the channel and instead just relied on done channel.

stefanhengl changed the title ~~Sh/call zoekt early~~ search: call zoekt early Sep 23, 2020

stefanhengl requested a review from keegancsmith September 23, 2020 10:01

keegancsmith reviewed Sep 23, 2020

View reviewed changes

stefanhengl force-pushed the sh/call-zoekt-early branch from c9affa3 to 546bc22 Compare September 24, 2020 10:20

stefanhengl marked this pull request as ready for review September 25, 2020 10:02

keegancsmith approved these changes Sep 29, 2020

View reviewed changes

stefanhengl force-pushed the sh/call-zoekt-early branch from 7bbfc34 to fe46b9a Compare September 29, 2020 08:33

stefanhengl commented Sep 29, 2020

View reviewed changes

stefanhengl added 17 commits September 29, 2020 14:10

POC for calling zoekt early

ce2371c

fix tests

ee17e08

docstrings

aa2ca59

don't send to channel if not global search

973710f

iota

1a9a173

replace Repos with a promise

dceabe8

Get() -> Get(ctx)

d2e0791

catch if args is nil

965efcb

get rid of branching in for loop over resp.Files

6d68651

enable ZoektGlobalSearch only for file & path

aa18f00

clean up

f90a435

add docstrings

db652f9

add tests

9d9086c

add child context to protect against regression

6d0be36

address PR coments

88b0315

address PR comments

cf7e164

update promise implementation

update tests

ed669b6

resolve merge conflicts

76e7d26

stefanhengl force-pushed the sh/call-zoekt-early branch from 902264e to 76e7d26 Compare September 29, 2020 12:14

update comment

a9d31f1

stefanhengl requested a review from keegancsmith September 29, 2020 12:26

keegancsmith approved these changes Sep 29, 2020

View reviewed changes

stefanhengl merged commit 969b03d into main Sep 30, 2020

stefanhengl deleted the sh/call-zoekt-early branch September 30, 2020 06:09

sourcegraph-bot mentioned this pull request Sep 30, 2020

Update Sourcegraph Docker insiders images sourcegraph/deploy-sourcegraph#985

Merged

1 task

lguychard mentioned this pull request Oct 2, 2020

Slow search when regexp is enabled, fast when not #14351

Closed

rvantonder mentioned this pull request Nov 17, 2020

search backend fix: repohasfile honored for global search #15894

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

search: call zoekt early #14093

search: call zoekt early #14093

stefanhengl commented Sep 23, 2020 •

edited

Loading

keegancsmith left a comment

keegancsmith Sep 23, 2020

stefanhengl Sep 23, 2020

keegancsmith Sep 23, 2020

keegancsmith Sep 23, 2020

keegancsmith Sep 23, 2020

stefanhengl Sep 23, 2020

stefanhengl Sep 24, 2020

keegancsmith Sep 23, 2020

codecov bot commented Sep 24, 2020 •

edited

Loading

keegancsmith left a comment

keegancsmith Sep 29, 2020

stefanhengl Sep 29, 2020

stefanhengl Sep 29, 2020

keegancsmith Sep 29, 2020

stefanhengl Sep 29, 2020

stefanhengl Sep 29, 2020

keegancsmith Sep 29, 2020

stefanhengl Sep 29, 2020

keegancsmith Sep 29, 2020

keegancsmith commented Sep 29, 2020

keegancsmith commented Sep 29, 2020

sourcegraph-bot commented Sep 29, 2020 •

edited

Loading

stefanhengl Sep 29, 2020

keegancsmith Sep 29, 2020

stefanhengl Sep 29, 2020

stefanhengl commented Sep 29, 2020 •

edited

Loading

keegancsmith left a comment

keegancsmith Sep 29, 2020

search: call zoekt early #14093

search: call zoekt early #14093

Conversation

stefanhengl commented Sep 23, 2020 • edited Loading

keegancsmith left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

codecov bot commented Sep 24, 2020 • edited Loading

Codecov Report

keegancsmith left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

keegancsmith commented Sep 29, 2020

keegancsmith commented Sep 29, 2020

sourcegraph-bot commented Sep 29, 2020 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

stefanhengl commented Sep 29, 2020 • edited Loading

keegancsmith left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

stefanhengl commented Sep 23, 2020 •

edited

Loading

codecov bot commented Sep 24, 2020 •

edited

Loading

sourcegraph-bot commented Sep 29, 2020 •

edited

Loading

stefanhengl commented Sep 29, 2020 •

edited

Loading