4 ms·

KNN indexing!

by jgavris 15y ago

KNN indexing!

samstokes 15y ago
Can anyone give an example use case for this? I'm not sure I fully understand what it means.
- netghost 15y ago
  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.
  - deleted 15y ago
    [deleted]
- wulczer 15y ago
  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 http://www.pgcon.org/2010/schedule/events/227.en.html
- rbranson 15y ago
  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.
- jgavris 15y ago
  take a look at these query plans - http://www.depesz.com/index.php/2010/12/11/waiting-for-9-1-knngist/ http://www.depesz.com/index.php/2010/12/11/waiting-for-9-1-k...
- samstokes 15y ago
  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".
  - kiwidrew 15y ago
    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?
    - samstokes 15y ago
      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!
      - kiwidrew 15y ago
        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.
- richardkmichael 15y ago
  There's this Accelerating Local Search talk this Friday (Sep-16). http://postgresopen.org/2011/schedule/presentations/42/ http://postgresopen.org/2011/schedule/presentations/42/

KNN indexing!

by jgavris 15y ago

KNN indexing!

samstokes 15y ago

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

netghost 15y ago
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.
- deleted 15y ago
  [deleted]
wulczer 15y ago
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 http://www.pgcon.org/2010/schedule/events/227.en.html
rbranson 15y ago
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.
jgavris 15y ago
take a look at these query plans - http://www.depesz.com/index.php/2010/12/11/waiting-for-9-1-knngist/ http://www.depesz.com/index.php/2010/12/11/waiting-for-9-1-k...
samstokes 15y ago
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".
- kiwidrew 15y ago
  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?
  - samstokes 15y ago
    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!
    - kiwidrew 15y ago
      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.
richardkmichael 15y ago
There's this Accelerating Local Search talk this Friday (Sep-16). http://postgresopen.org/2011/schedule/presentations/42/ http://postgresopen.org/2011/schedule/presentations/42/