Hacker News Reader

Comment by samstokes | Hacker News Reader

Can anyone give an example use case for this? I'm not sure I fully understand what it means.

Without it, SELECT * FROM table WHERE text_column LIKE '%word%' involves a full table scan. With KNN + pg_trgm, it's an index scan. That's huge.

In spatial queries, find the 5 restaurants closest to me. In full text search, find the 5 words closest to "fuschia" so you can spell check, or try to search for what you __think__ the user meant to type.

Here's the presentation from last year's PGCon, it's not exactly easy to follow, but has some hints on how this can be used:

http://www.pgcon.org/2010/schedule/events/227.en.html

Nice, thanks for all the examples and explanations!

Anyone know if it's possible to define a custom distance metric for use with this? We don't currently use full-text or spatial indices, but I can think of some cool things we could do with a generalised notion of "distance".

Yes, it is possible. Postgres supports custom data types and operators on those data types, and (using the GiST subsystem) you can create indexes using those custom operators.

Unfortunately, there is a caveat: this will more than likely require writing custom C code. I've never tried to implement GiST indexing for a new data type, so I don't know just how much effort would be required.

What kind of distances did you have in mind?

We have a table which essentially represents a shallow graph (rows in the table can have links to to one or more other rows in the table). It would probably be interesting if we could define a distance metric in terms of those links: "find all rows reachable in 3 links from this starting row".

This probably isn't ideally done by this sort of index, as it would be a pretty weird sort of distance metric, if it's even a valid one (most rows aren't connected, meaning the "distance" between most rows would be infinite, and our query would really be "WHERE distance < infinity"). But it's good to know there's some kind of support for it!

Ah, right. For the kNN/GiST support in Postgres, distance has to be defined in such a way that it is computable given only two data values; furthermore, I'm pretty sure it has to be both symmetric and satisfy the triangle inequality in order for the index to produce correct results.

There's this Accelerating Local Search talk this Friday (Sep-16).

http://postgresopen.org/2011/schedule/presentations/42/

take a look at these query plans - http://www.depesz.com/index.php/2010/12/11/waiting-for-9-1-k...

Reply on news.ycombinator.com