KNN Gist for geography

[robe]

A lot of people mistakenly think KNN gist exists for geography and are saddened when I tell them the bad news.

Feel free to shoot this down as a no-go Paul. I'm not sure what's involved with providing KNN gist for geography.

[pramsey]

It's a verrrry iffy proposition. KNN works by calculating the distances between the index keys. for 2d, those keys are in the same "space" as the objects they proxy for, but even there things get confusing as the boxes have to proxy for non-box things like lines/polygons.

Now, go into sphere-land. The objects are points/line/polygons traced on a sphere. The *keys* are three-space boxes in geocentric space that contain those objects. So, as with lines/polys in 2d space, the sort distance between the keys is *similar* to the real sort distance between the objects, it is not the *same*, and it's even harder to visualize and explain.

And for points, it's not exact either, since a KNN search would ideally put objects in their order relative to their spherical distance, the KNN sort on points would return objects based on their geocentric distances from one another.

I'll leave it to you to decide if this is a "no way". It'll never return exact correct results, for *any* geometry type, only approximations.

[robe]

Iffy sounds like an iffy "no way". Would this option be better than doing

SELECT ... ORDER BY a.geom_4326 <-> b.geom_4326

If not then I guess not worth the effort. The never return exact results doesn't bother me so much since for most cases, people use this as a first hope anyway and not the final. Anyway probably something to vote on rather than do blindly.

[pramsey]

This got done by strk, unless I miss my guess. It'll still be really iffy w/o recheck, but for points it should work fine. Good luck explaining the non-point behaviour to mere mortals.

[strk]

Me ? KNN ? Is something wrong with trac times ? This ticket is documented as being created 21 months ago. In no way I touched KNN more than 4 months ago (and I did the index assisted n-dimensional KNN). Paul, I think KNN was yours ?

[pramsey]

Ah, well you did the hard parts of it then, since the geography index is just the n-dimensional index using 3 dimensions.

[pramsey]

This got done at #2703