Sometimes you cannot find the group in the autofill dropdown for elasticsearch indexed groups

added advanced search groupglobal search priority3 severity3 typebug labels

It's not clear if this change would be frontend or backend . It would depend if the results are paginated and need to be sorted in the backend.

@DylanGriffith that looks like a backend bug. We use ILIKE without any ordering there:

[40] pry(main)> Namespace.search('abc123')
  Namespace Load (0.7ms)  SELECT "namespaces".* FROM "namespaces" WHERE ("namespaces"."name" ILIKE '%abc123%' OR "namespaces"."path" ILIKE '%abc123%')

Also, we could think about allowing searching by id. Currently it's almost impossible to pick one specific project if we have a lot of similar/identical names.

Looking at the screenshot in the issue: https://gitlab.com/gitlab-com/gl-infra/production/issues/1591#note_277425186 it seems like we aren't prioritizing names that have a perfect match.

I'm wondering if we could change the strategy here to use POSITION('abc123' in "namespace"."path") to have a data point to order from (the index of the substring) such as a perfect match would always yield 0 and thus be at the top.

I did a bit of research and it seems this approach would be valid if we can leverage GIN indexes and still do case insensitive search.

Looking at the structure.sql, it seems our GIN indexes are not built using lower(), which means they are case-sensitive. We circumvent that in by using ILIKE in the search query.

CREATE INDEX index_namespaces_on_name_trigram ON public.namespaces USING gin (name public.gin_trgm_ops);
CREATE INDEX index_namespaces_on_path_trigram ON public.namespaces USING gin (path public.gin_trgm_ops);

After some testing, it seems POSITION() never ends-up using any index, which makes it run as a SeqScan which would slow down the query a lot.

I'm looking at other solutions.

do an UNION, searching for <query>% then %<query>% and removing any dupplicates, ordering the first batch before the second batch.
rank by coverage, which I would define as len(column) - len(query) / len(column). A lower number would mean that there are less outstanding characters in the results.

So I've run the second solution on synthetic dataset and I think it would yields better results without incurring too much performance cost.

Most importantly, it would ensure a perfect match on top.

@dgruzd @changzhengliu WDYT?

Example 1

Query: "war"

Results

"coverage"	"title"	"show_id"
0	"War"	70061480
0.4	"Anwar"	70064205
0.4	"V Wars"	80236118
0.4	"Warda"	81035854
0.5714285714285714	"Warrior"	80193978
0.625	"Bawarchi"	60003405
0.625	"God of War"	80145625
0.625	"Skin Wars"	80109536
0.625	"War Horse"	70172928
0.6666666666666666	"King’s War"	80160391
0.6666666666666666	"Moms at War"	81172848
0.7	"3 Deewarein"	60034116
0.7	"Howards End"	60029366
0.7	"The Warning"	80232989
0.7	"War Machine"	80068327
0.7	"Warehoused"	80216215
0.7272727272727273	"Aashik Awara"	80157084
0.75	"Alien Warfare"	80232502
0.75	"Charité at War"	81081067
0.75	"Prelude to War"	60027945
0.75	"The 24 Hour War"	80158800
0.7692307692307693	"Apache Warrior"	80216003
0.7692307692307693	"My Dear Warrior"	81163776
0.7692307692307693	"Raja Natwarlal"	70303431
0.7692307692307693	"War on Everyone"	80103374
0.7857142857142857	"War Chhod Na Yaar"	70296742
0.8	"War Against Women"	81077862
0.8125	"Wartime Portraits"	80126566
0.8333333333333334	"American Warfighter"	81092328
0.8333333333333334	"World War II in Colour"	70254851
0.8421052631578947	"Skin Wars: Fresh Paint"	80179556
0.8421052631578947	"Solo: A Star Wars Story"	80220814
0.85	"Avengers: Infinity War"	80219127
0.85	"Enter the Warriors Gate"	80138681
0.85	"Ken Burns: The Civil War"	70202577
0.85	"Record of Grancrest War"	81086718
0.8571428571428571	"Blue Is the Warmest Color"	70275600
0.8636363636363636	"Arjun: The Warrior Prince"	70139073
0.8636363636363636	"Harriet the Spy: Blog Wars"	70142918
0.875	"Iliza Shlesinger: War Paint"	70278877
0.875	"PILI Fantasy: War of Dragons"	81094893
0.88	"Park Na-rae: Glamour Warning"	81053240
0.88	"Russell Howard: Recalibrate"	80189806
0.8846153846153846	"Bruno and Boots: The Wizzle War"	80191358
0.8888888888888888	"Benchwarmers 2: Breaking Balls"	81038225
0.8928571428571429	"Trigger Warning with Killer Mike"	80144442
0.896551724137931	"Defying the Nazis: The Sharps' War"	80103430
0.896551724137931	"Storage Wars: Northern Treasures"	80233419
0.9032258064516129	"Hari Kondabolu: Warn Your Relatives"	80213657
0.90625	"Star Wars: Episode VIII: The Last Jedi"	80192018
0.9142857142857143	"Solo: A Star Wars Story (Spanish Version)"	81046962
0.9142857142857143	"The War: A Film by Ken Burns and Lynn Novick"	70202579
0.9166666666666666	"Joe Mande’s Award-Winning Comedy Special"	80185321
0.9210526315789473	"Anthony Jeselnik: Fire in the Maternity Ward"	80227677
0.9285714285714286	"The Vietnam War: A Film by Ken Burns and Lynn Novick"	80997770
0.9411764705882353	"Attacking the Devil: Harold Evans and the Last Nazi War Crime"	80104330

Query plan:

"Sort  (cost=64.34..64.49 rows=62 width=398) (actual time=0.127..0.129 rows=56 loops=1)"
"  Sort Key: ((((length(replace((title)::text, ' '::text, ''::text)) - 3))::double precision / (length(replace((title)::text, ' '::text, ''::text)))::double precision)), title"
"  Sort Method: quicksort  Memory: 56kB"
"  ->  Bitmap Heap Scan on netflix_shows  (cost=3.48..62.49 rows=62 width=398) (actual time=0.020..0.098 rows=56 loops=1)"
"        Recheck Cond: ((title)::text ~~* '%war%'::text)"
"        Heap Blocks: exact=49"
"        ->  Bitmap Index Scan on netflix_shows_title_idx  (cost=0.00..3.46 rows=62 width=0) (actual time=0.010..0.010 rows=56 loops=1)"
"              Index Cond: ((title)::text ~~* '%war%'::text)"
"Planning Time: 0.089 ms"
"Execution Time: 0.146 ms"

References

Dataset: $1959864

I'm looking at how we could add that logic to our fuzzy_search algorithm, as it uses multiple columns to do the search. I think a simple min(...) of all each column's coverage would do it just fine for ranking purposes.

I'm pretty sure we'll want to put that under a feature flag.

@mbergeron that's a good option. What do you think about adding to that query something like ORDER BY title = 'war' DESC, ... to be sure that even if we have a lot of results with the same length an exact match would always be on top?

@dgruzd the problem I'm facing right now is that we can't control the searched fields from the API, which are:

Namespace: name, path
Project: name, path, description or routes.name, routes.path, description

That can make weird scenarios where search in the description will always yield a low ranking, because of the size of the searched text.

Another problem I'm facing is that the API exposes a sorting mechanism for the consumer, such as the order of the ranking is overridden (we could probably add a :rank/:match to circumvent this)

I'm wondering if we could supply hints to the API to restrict the search (IMO we only want to search by path_with_namespace here) and go from there?

Bummer, I'm afraid this approach cannot work when there are multiple search columns: we are matching with OR so as soon as there is a valid hit on any column, the rank is computed for all the columns, even if the text doesn't match in it.

@dgruzd @DylanGriffith This problem looks like a good rabit hole. I'm starting to think that we should simply implement the pagination logic in the front-end and be done with this.

I'll push my current code so you can take a look at the implementation, but I don't think we'll be able to use it.

The search results are actually good (too large even), but the problem is that we only show the top 11.

@mbergeron what do you think about adding an ability to search by id? I think it could help a lot with this specific problem and it might be useful in other parts of our application.

@dgruzd I think this is where we'll end up, but I'd go with something more legible, and that matches what the dropdown shows.

I had a talk with @DylanGriffith yesterday about that, and improving the API might be a better way to go.

With that said, I took a look at the routes table, and this seems like the best candidate for this use-case, as it contains a collection of unique paths for each type of entity.

I think I'll simply change the front-end to use the AutocompleteController instead of the API.

added devopssystems label

added Category:Global Search label

mentioned in issue #201689 (closed)

mentioned in issue #204691 (closed)

mentioned in issue #206855 (closed)

mentioned in issue #207791 (closed)

mentioned in issue #208652 (closed)

changed milestone to %12.10

added [deprecated] Accepting merge requests label

assigned to @mbergeron

removed [deprecated] Accepting merge requests label

In general I think this bug happens across many auto complete dropdowns in GitLab. We should probably put exact matches at the top of the list to ensure it's always possible to find anything.

This is something I've also experienced whenever you want to mention another user for instance.

I'll take a look.

@changzhengliu I have a question regarding the Namespace field in there. It seems to me this should be a Group field, as I don't see any use-case of using a User's namespace, as there is no permission model on it.

Who would be the best person to chime in here?

@DylanGriffith may know it.

@mbergeron I'm not sure I fully understand. I don't see any reason we can't index a user's personal namespace. This whitelist isn't really about the group as much as it is about the projects within the group. Basically this whitelist means that all projects within this group will be indexed in Elasticsearch. As such they'll get all the search features available when the project is indexed in Elasticsearch (advanced search syntax etc.).

What you may be pointing out, legitimately, though, is that there is no way in GitLab's UI to search in a user's namespace and can only scope searches to groups or projects. That is true but if we enable indexing for all of a user's projects they could still do project scoped advanced search in all of their projects.

Basically I don't think there is much of a good reason to limit this to groups since it does work fine for any kind of namespace. With that said I'm not totally clear what you meant by "there is no permission model on it".

What you may be pointing out, legitimately, though, is that there is no way in GitLab's UI to search in a user's namespace and can only scope searches to groups or projects. That is true but if we enable indexing for all of a user's projects they could still do project scoped advanced search in all of their projects.

Exactly, that means we have to gate this endpoint for admin only and that limits the re-usability of it in order to prevent leaking all of the usernames.

I think I understand your point — I'm trying to get an idea on how this feature is used. I felt like this was mainly a Gitlab.com operational filter, such as we can roll-out the usage of this, and as such, I think that whitelisting user's namespaces is pretty much irrelevant.

@DylanGriffith does that better explain my thoughts?

@DylanGriffith FYI I've figured out how to do it gracefully, and we'll be able to use generic Namespaces.

Note to self: creating the routes.path GIN index took 40s for 5M entries.

mentioned in merge request !29043 (merged)

closed

added devopsdata stores label and removed devopssystems label

Sometimes you cannot find the group in the autofill dropdown for elasticsearch indexed groups

Designs

Child items ...

Activity

Example 1

References