Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Fast Search Using PostgreSQL Trigram Indexes

about.gitlab.com

Post reply on HN
Print view View original

21–30 of 33 posts

Re: Fast Search Using PostgreSQL Trigram Indexes

#21

Post by mbenjaminsmith »

TheLogothete wrote: post #20
mbenjaminsmith wrote: post #19

Trigrams are a very straightforward solution to this but they have one major limitation: They break with misspellings / alternative spellings. For example the words "vodka" and "votka" share no trigrams yet are obviously very similar. I recently worked on this problem for a project and came up with a more robust solution using pre-computed Levenshtein indexes. You've probably heard of Levenshtein distance as a measur…

Or, you know, use a search engine. There are countless little things like that and out-of-the-box search in DBs will never catch up with.

The resulting product is fast, easy to tune (for my particular application) and handles every edge case and language I've thrown at it.

Do you have any specific concern you'd like to share or are you just generally dismissive of other people's hard work?

Re: Fast Search Using PostgreSQL Trigram Indexes

#22

Post by TheLogothete »

mbenjaminsmith wrote: post #21
TheLogothete wrote: post #20

Earlier quoted context omitted.

Or, you know, use a search engine. There are countless little things like that and out-of-the-box search in DBs will never catch up with.

The resulting product is fast, easy to tune (for my particular application) and handles every edge case and language I've thrown at it. Do you have any specific concern you'd like to share or are you just generally dismissive of other people's hard work?

I'm dismissive of pointless hard work.

Re: Fast Search Using PostgreSQL Trigram Indexes

#23

Post by oelmekki »

mbenjaminsmith wrote: post #19

Trigrams are a very straightforward solution to this but they have one major limitation: They break with misspellings / alternative spellings. For example the words "vodka" and "votka" share no trigrams yet are obviously very similar. I recently worked on this problem for a project and came up with a more robust solution using pre-computed Levenshtein indexes. You've probably heard of Levenshtein distance as a measur…

Super interesting approach, thanks for contributing it.

From what I see in your article, you used this for searching through mails, so I guess it works on a pretty decent volume of data, but just to confirm it: do you think it's viable on something like gitlab's multi-resources full text search? For reference, what is the size of this index for your mailbox? (assuming it's an usual contractor dev mailbox, with mainly lots of notification mails and discussions with daily customers)

PS: don't worry about other reactions, users have invaded our dev world, nowadays, the sad thing with having attractive salaries

Re: Fast Search Using PostgreSQL Trigram Indexes

#25

Post by bazzargh »

beachstartup wrote: post #12

ah yes, the old 're-implement the search engine inside the database' project, undoubtedly put up on the board because someone is tired of their get-the-data-from-the-database-to-the-search-engine process breaking constantly. next on the map: discovering how shitty dictionary management is, the joys of NLP, and abandoning the project entirely because you realize all this stuff has already been solved in 3 or 4 differe…

the joys of NLP ... this is a search index for Gitlab, that's used primarily to store code, not natural language.

Looking at its competitor, Github's search engine clearly has a base in NLP, and ditches many punctuation characters (https://help.github.com/articles/searching-code/) - which are way more important in code than they are in English - for example, I can't search for code containing "$/" when it should have "\Z/" to match the end of a string. So, right now I have ~250 repos checked out from our Github Enterprise so I can search them offline.

The queries I actually want to run are, pretty much, regexes. Those can be accelerated by trigram indexes like the one gitlab are using (see eg https://swtch.com/~rsc/regexp/regexp4.html), but apparently this isn't implemented by say, Elastisearch (Whereas prefix matching can be made more efficient by preparing your data at index time, wildcard and regular expression matching can be done only at query time. https://www.elastic.co/guide/en/elasticsearch/guide/current/...)

I'd agree with you if this wasn't code. I've seen terrible text search in the DB, and I've built document management systems where we integrated real search engines. But those horses aren't for this course.

Re: Fast Search Using PostgreSQL Trigram Indexes

#26

Post by YorickPeterse »

supergreg wrote: post #24

IIRC Google also used trigrams for their Code search engine. This allowed them to make a first filter before running a regex search on the resulting documents. Does gitlab support regex searches?

> Does gitlab support regex searches?

No, not at the moment.

Re: Fast Search Using PostgreSQL Trigram Indexes

#28

Post by jmilum »

mbenjaminsmith wrote: post #19

Trigrams are a very straightforward solution to this but they have one major limitation: They break with misspellings / alternative spellings. For example the words "vodka" and "votka" share no trigrams yet are obviously very similar. I recently worked on this problem for a project and came up with a more robust solution using pre-computed Levenshtein indexes. You've probably heard of Levenshtein distance as a measur…

vodka and votka do share trigrams: __v, _vo, and ka_, as the PG rules for generating them add two spaces at the beginning and one at the end.

Re: Fast Search Using PostgreSQL Trigram Indexes

#30

Post by elchief »

mbenjaminsmith wrote: post #19

Trigrams are a very straightforward solution to this but they have one major limitation: They break with misspellings / alternative spellings. For example the words "vodka" and "votka" share no trigrams yet are obviously very similar. I recently worked on this problem for a project and came up with a more robust solution using pre-computed Levenshtein indexes. You've probably heard of Levenshtein distance as a measur…

how about some in-database spelling auto-correction:

http://blog.databasepatterns.com/2014/08/postgresql-spelling...

Post reply on HN