6 ms·

Using the linear distance operator in Postgres 12 to find the closest match

113 points by chmaynard 7y ago

zRedShift 7y ago
So it's using a K-D-B-Tree under the hood? SP-GiST, that is. https://en.wikipedia.org/wiki/K-D-B-tree https://en.wikipedia.org/wiki/K-D-B-tree
dtjohnnyb 7y ago
How many dimensions can you use this with efficiently? Could you use this to store embeddings from machine learning models and find nearest neighbours of various items, like aNNoy or faiss does?
- inertiatic 7y ago
  Super curious about this as well.
- mistrial9 7y ago
  this is a special case of reading the internal GIST spatial index used in PostGIS by the implentation code for operator '<->' , so no joy for N-dimensional search.. You can use a python library inside PostgreSQL using plPython, but supplying the coordinates to the evaluation is not going to be as compact and specialized as this
- deckar01 7y ago
  Its point structure supports 4 dimensions, but I'm not sure if the Z and M components are part of the distance calculation. https://postgis.net/docs/manual-3.0/ST_MakePoint.html https://postgis.net/docs/manual-3.0/ST_MakePoint.html Edit: The distance operations are 2D by default and it looks like there are only 3D variants. https://postgis.net/docs/manual-3.0/ST_3DDistance.html https://postgis.net/docs/manual-3.0/ST_3DDistance.html
- changelink 7y ago
  Postgres has a extension called cube (https://www.postgresql.org/docs/9.6/cube.html https://www.postgresql.org/docs/9.6/cube.html) that can be used for up to 150 dimensions (which is a compile-time limit, you can have more if you compile Postgres yourself). It's a pretty cool extension that does distance between points, intersections between n-dimensional cubes (hence the name), different distance metrics etc. It'd be perfect for storing and searching through large amounts of n-dimensional embeddings, I'm guessing it's used for that already.
  - orf 7y ago
    Fun fact, there’s a bug in the implementation where you can create cubes with much higher dimensions because one constructor doesn’t do the check. Still wouldn’t recommend it though.
  - kaivi 7y ago
    In my experience, the cube extension is unusable for >10M x 128D vectors without PCA. I'm using Faiss now with ~500M vectors, and it works great!
    - phelmig 7y ago
      With how many dimensions are you using Faiss with 100m+ vectors? I’m currently looking a solution to handle 1024 dimensions for ~100m items.
      - kaivi 7y ago
        On one index I'm using OPQ16_64,IVF262144_HNSW32,PQ16 with 128 dimensions initially. 1024 dimensions is a lot! Could you elaborate on what application requires that many? If it's a DNN layer output, your data must be sparse, so dimensionality reduction won't affect your recall if tuned properly.
        phelmig 7y ago
        It's actually a DNN layer output. I haven't considered dimensionality reduction, yet. Thanks for pointing my there, I'll look into it. Probably thats the better way to go. Thanks a lot for your reply!
- blr246 7y ago
  I had the same initial thought based on the title. Unfortunately, the answer is no. The article discusses a low-dimensional KNN problem. The curse of dimensionality guides intuition that the methods here likely will not apply to extremely high-dimensional problems. faiss actually comes with a lot of excellent documentation that describes the problems unique to KNN on embedding vectors. In particular, for extremely large datasets, most of the tractable methods are approximations that make use of clustering, quantization, and centriod-difference tricks to make computation efficient. See https://github.com/facebookresearch/faiss/wiki/Faiss-indexes https://github.com/facebookresearch/faiss/wiki/Faiss-indexes and related links for more information.
jonatron 7y ago
I find it strange that Postgres has features like these, but lacks bit_count, which is required for hamming distance. It's easy to write a C-Language User Defined Function, but then you can't use RDS.
- takeda 7y ago
  One of greatest things about Postgres is its extension system which is meant for things like this. RDS not supporting custom extension is RDS problem and frankly I wouldn't recommend using RDS. You are losing a lot of functionality, upgrades are tougher etc. Postgres maintenance is quite low the hardest part is probably running and RDS doesn't save you from that. Anyway this feature discussed (searching based on a distance) is part of PostGIS extension they are demonstrating here SP-GiST index.
  - Znafon 7y ago
    > RDS not supporting custom extension is RDS problem and frankly I wouldn't recommend using RDS. We are using RDS and would like to have a standard PostgreSQL instead. Is there some community supported AMIs that could help us to get started quickly?
    - vosper 7y ago
      > We are using RDS and would like to have a standard PostgreSQL instead. Having not used Postgres RDS, what about it makes you want to have a standard Postgres instead?
      - Znafon 7y ago
        I think RDS has some very strong pros: - not so bad pricing - good defaults - no need to worry regarding the backups and easy disaster recovery - some monitoring out of the box - support TLS with a valid cert out of the box - easy replication I'm not an ops so not having to worry about the operational aspects of our datastore was great. Here are some pain-points we have, I'm probably forgetting some but those were really painful: - You don't have a superadmin access, we had several issues where some tables, sequences or objects where associated with a user we wanted to delete and this was really hard, I think we were supposed to change the owner of each objects one by one. [0] shows the issue. In the end, we solved it by dumping the database, deleting the user, recreating the database. Thankfully, this wasn't in prod. - Many extensions cannot be installed, for example Timescale. It's a bit sad having PostgreSQL and not being able to take full advantage of it. What I regret about those is that there is nothing you can do, for the first point I looked everywhere and many have this issue but there is nothing you can do to solve it easily, there is posts both on StackOverflow and PostgreSQL mailing list but no easy solution, you have to track one by one the object whose owner you want to delete and reassign them. For the second, it means you can't use many useful extensions like Timescale or anything not yet released. If there was some AMI with PostgreSQL already installed and correctly configured on which we could just connect an EBS, we could migrate very easily. [0] https://stackoverflow.com/questions/44718654/cant-delete-postgresql-user-who-poses-a-security-risk/44718983#44718983 https://stackoverflow.com/questions/44718654/cant-delete-pos...
mlthoughts2018 7y ago
If there is going to be any system capable of supporting creating something like The Matrix, it’s going to be Postgres. Tries to eat all application logic by suggested move in database, use language extensions. I’ve only ever found it to be a false promise. You get locked inside the db and can’t create application logic outside the db, and the internal language extensions are super poor solutions for this if you need multiple environments, multiple packages, different versions of the same extension-based app. I love Postgres as a db, but I feel like all the viral marketing for moving to internal db app logic, especially with extensions, is a big trap, and the tutorials & blog posts give you some really superficial use cases to motivate it, and in reality you’re speeding toward a cliff.
- kid_atticus 7y ago
  I'd say the real value of the 'application-like' capabilities of Postgres is for analytics and offline tasks where there may not even be an application to 'eat'. This article is a great example, anyone can get this working on their laptop easily and just feed new data into the structure they have created and trust that it will just work. Now, if this is powering some actual business logic then that's can cause problems since now your application is tightly coupled to a specific implementation in a specific database technology that may or may not be testable, versioned, or observable. But if you're a data hacker trying to answer questions, produce a report, or tease out features for a ML model having a such a robust easy to manage tool in your toolbelt is super useful. Application Postgres and Analytics Postgres are really different animals, it's pretty cool that one piece of software can do both so well and be so many different things to different people, but yeah I agree you can into real trouble if you use the wrong part of the tool for the job.
- CuriouslyC 7y ago
  If you have a problem that is never going to be google scale, and you have people who are familiar with postgres, you can deliver applications that are a fraction of the code with superior performance. The only problem with db-centric applications is the tooling, which is inferior to standard application tooling at this point, in terms of version control and testability. Given the hype train building around postgres as a platform, I expect this is going to change pretty quickly.
miles-po 7y ago
While the unindexed time is impressive for the lack of index, the GIST and SP-GIST times are not 0.939 sec and 0.358 sec. All times are in milliseconds. GIST returns in slightly less than 1ms, not 1s. SP-GIST returns in slightly more than 1/3 of a millisecond. Performance for GIST and SP-GIST are in fact three orders of magnitude better than what the author summarized!
Sniffnoy 7y ago
I'm a little confused as to what this does. Is this just Euclidean distance, or is it meant to be used for longitude/latitude? The article doesn't make it clear.
- mistrial9 7y ago
  this is distance in units of degree 'Euclidean' .. not so great, except that the answer is expected to be the "closest" point, which tends to be smaller and need less precision.. not useful for measurement in meters
copperx 7y ago
Is there any way to get the closest driving distance in Postgres without relying on some API? I haven't done anything like this, bit it is possible to use the data from OpenStreetMap locally along with Postgres to e.g. sort results by shortest driving distance? Maybe there's an extension? I'm just curious.
- shabble 7y ago
  You might want pgrouting[1], if you can find access to appropriate datasets for your routing (road) network. [1] http://workshop.pgrouting.org/2.5/en/chapters/advanced.html#routing-for-vehicles http://workshop.pgrouting.org/2.5/en/chapters/advanced.html#...
  - copperx 7y ago
    That's really great, thanks.

113 points by chmaynard 7y ago

So it's using a K-D-B-Tree under the hood? SP-GiST, that is. https://en.wikipedia.org/wiki/K-D-B-tree https://en.wikipedia.org/wiki/K-D-B-tree

dtjohnnyb 7y ago

How many dimensions can you use this with efficiently? Could you use this to store embeddings from machine learning models and find nearest neighbours of various items, like aNNoy or faiss does?

inertiatic 7y ago
Super curious about this as well.
mistrial9 7y ago
this is a special case of reading the internal GIST spatial index used in PostGIS by the implentation code for operator '<->' , so no joy for N-dimensional search.. You can use a python library inside PostgreSQL using plPython, but supplying the coordinates to the evaluation is not going to be as compact and specialized as this
deckar01 7y ago
Its point structure supports 4 dimensions, but I'm not sure if the Z and M components are part of the distance calculation. https://postgis.net/docs/manual-3.0/ST_MakePoint.html https://postgis.net/docs/manual-3.0/ST_MakePoint.html Edit: The distance operations are 2D by default and it looks like there are only 3D variants. https://postgis.net/docs/manual-3.0/ST_3DDistance.html https://postgis.net/docs/manual-3.0/ST_3DDistance.html
changelink 7y ago
Postgres has a extension called cube (https://www.postgresql.org/docs/9.6/cube.html https://www.postgresql.org/docs/9.6/cube.html) that can be used for up to 150 dimensions (which is a compile-time limit, you can have more if you compile Postgres yourself). It's a pretty cool extension that does distance between points, intersections between n-dimensional cubes (hence the name), different distance metrics etc. It'd be perfect for storing and searching through large amounts of n-dimensional embeddings, I'm guessing it's used for that already.
- orf 7y ago
  Fun fact, there’s a bug in the implementation where you can create cubes with much higher dimensions because one constructor doesn’t do the check. Still wouldn’t recommend it though.
- kaivi 7y ago
  In my experience, the cube extension is unusable for >10M x 128D vectors without PCA. I'm using Faiss now with ~500M vectors, and it works great!
  - phelmig 7y ago
    With how many dimensions are you using Faiss with 100m+ vectors? I’m currently looking a solution to handle 1024 dimensions for ~100m items.
    - kaivi 7y ago
      On one index I'm using OPQ16_64,IVF262144_HNSW32,PQ16 with 128 dimensions initially. 1024 dimensions is a lot! Could you elaborate on what application requires that many? If it's a DNN layer output, your data must be sparse, so dimensionality reduction won't affect your recall if tuned properly.
      - phelmig 7y ago
        It's actually a DNN layer output. I haven't considered dimensionality reduction, yet. Thanks for pointing my there, I'll look into it. Probably thats the better way to go. Thanks a lot for your reply!
blr246 7y ago
I had the same initial thought based on the title. Unfortunately, the answer is no. The article discusses a low-dimensional KNN problem. The curse of dimensionality guides intuition that the methods here likely will not apply to extremely high-dimensional problems. faiss actually comes with a lot of excellent documentation that describes the problems unique to KNN on embedding vectors. In particular, for extremely large datasets, most of the tractable methods are approximations that make use of clustering, quantization, and centriod-difference tricks to make computation efficient. See https://github.com/facebookresearch/faiss/wiki/Faiss-indexes https://github.com/facebookresearch/faiss/wiki/Faiss-indexes and related links for more information.

jonatron 7y ago

I find it strange that Postgres has features like these, but lacks bit_count, which is required for hamming distance. It's easy to write a C-Language User Defined Function, but then you can't use RDS.

takeda 7y ago
One of greatest things about Postgres is its extension system which is meant for things like this. RDS not supporting custom extension is RDS problem and frankly I wouldn't recommend using RDS. You are losing a lot of functionality, upgrades are tougher etc. Postgres maintenance is quite low the hardest part is probably running and RDS doesn't save you from that. Anyway this feature discussed (searching based on a distance) is part of PostGIS extension they are demonstrating here SP-GiST index.
- Znafon 7y ago
  > RDS not supporting custom extension is RDS problem and frankly I wouldn't recommend using RDS. We are using RDS and would like to have a standard PostgreSQL instead. Is there some community supported AMIs that could help us to get started quickly?
  - vosper 7y ago
    > We are using RDS and would like to have a standard PostgreSQL instead. Having not used Postgres RDS, what about it makes you want to have a standard Postgres instead?
    - Znafon 7y ago
      I think RDS has some very strong pros: - not so bad pricing - good defaults - no need to worry regarding the backups and easy disaster recovery - some monitoring out of the box - support TLS with a valid cert out of the box - easy replication I'm not an ops so not having to worry about the operational aspects of our datastore was great. Here are some pain-points we have, I'm probably forgetting some but those were really painful: - You don't have a superadmin access, we had several issues where some tables, sequences or objects where associated with a user we wanted to delete and this was really hard, I think we were supposed to change the owner of each objects one by one. [0] shows the issue. In the end, we solved it by dumping the database, deleting the user, recreating the database. Thankfully, this wasn't in prod. - Many extensions cannot be installed, for example Timescale. It's a bit sad having PostgreSQL and not being able to take full advantage of it. What I regret about those is that there is nothing you can do, for the first point I looked everywhere and many have this issue but there is nothing you can do to solve it easily, there is posts both on StackOverflow and PostgreSQL mailing list but no easy solution, you have to track one by one the object whose owner you want to delete and reassign them. For the second, it means you can't use many useful extensions like Timescale or anything not yet released. If there was some AMI with PostgreSQL already installed and correctly configured on which we could just connect an EBS, we could migrate very easily. [0] https://stackoverflow.com/questions/44718654/cant-delete-postgresql-user-who-poses-a-security-risk/44718983#44718983 https://stackoverflow.com/questions/44718654/cant-delete-pos...

mlthoughts2018 7y ago

If there is going to be any system capable of supporting creating something like The Matrix, it’s going to be Postgres. Tries to eat all application logic by suggested move in database, use language extensions. I’ve only ever found it to be a false promise. You get locked inside the db and can’t create application logic outside the db, and the internal language extensions are super poor solutions for this if you need multiple environments, multiple packages, different versions of the same extension-based app. I love Postgres as a db, but I feel like all the viral marketing for moving to internal db app logic, especially with extensions, is a big trap, and the tutorials & blog posts give you some really superficial use cases to motivate it, and in reality you’re speeding toward a cliff.

kid_atticus 7y ago
I'd say the real value of the 'application-like' capabilities of Postgres is for analytics and offline tasks where there may not even be an application to 'eat'. This article is a great example, anyone can get this working on their laptop easily and just feed new data into the structure they have created and trust that it will just work. Now, if this is powering some actual business logic then that's can cause problems since now your application is tightly coupled to a specific implementation in a specific database technology that may or may not be testable, versioned, or observable. But if you're a data hacker trying to answer questions, produce a report, or tease out features for a ML model having a such a robust easy to manage tool in your toolbelt is super useful. Application Postgres and Analytics Postgres are really different animals, it's pretty cool that one piece of software can do both so well and be so many different things to different people, but yeah I agree you can into real trouble if you use the wrong part of the tool for the job.
CuriouslyC 7y ago
If you have a problem that is never going to be google scale, and you have people who are familiar with postgres, you can deliver applications that are a fraction of the code with superior performance. The only problem with db-centric applications is the tooling, which is inferior to standard application tooling at this point, in terms of version control and testability. Given the hype train building around postgres as a platform, I expect this is going to change pretty quickly.

miles-po 7y ago

While the unindexed time is impressive for the lack of index, the GIST and SP-GIST times are not 0.939 sec and 0.358 sec. All times are in milliseconds. GIST returns in slightly less than 1ms, not 1s. SP-GIST returns in slightly more than 1/3 of a millisecond. Performance for GIST and SP-GIST are in fact three orders of magnitude better than what the author summarized!

Sniffnoy 7y ago

I'm a little confused as to what this does. Is this just Euclidean distance, or is it meant to be used for longitude/latitude? The article doesn't make it clear.

mistrial9 7y ago
this is distance in units of degree 'Euclidean' .. not so great, except that the answer is expected to be the "closest" point, which tends to be smaller and need less precision.. not useful for measurement in meters

copperx 7y ago

Is there any way to get the closest driving distance in Postgres without relying on some API? I haven't done anything like this, bit it is possible to use the data from OpenStreetMap locally along with Postgres to e.g. sort results by shortest driving distance? Maybe there's an extension? I'm just curious.

shabble 7y ago
You might want pgrouting[1], if you can find access to appropriate datasets for your routing (road) network. [1] http://workshop.pgrouting.org/2.5/en/chapters/advanced.html#routing-for-vehicles http://workshop.pgrouting.org/2.5/en/chapters/advanced.html#...
- copperx 7y ago
  That's really great, thanks.