Opened 3 years ago

Closed 3 years ago

#4010 closed enhancement (fixed)

Sort nodes in circtree before descending for distance calculation

Reported by: pramsey Owned by: pramsey
Priority: medium Milestone: PostGIS 2.5.0
Component: postgis Version: master
Keywords: Cc:


As discovered in working on trying to get performant edge trees in planar space, there is a potentially very large speedup available in doing a tree-based distance calculation in sorting the tree nodes before descending into them, since doing so increases the odds of getting min/max constraints that will prune dead branches in later descents.

Applying the same idea to the CIRC_NODE trees used in geography calculations, a speed-up of 3x for a query of all countries against Canada was observed.

Change History (1)

comment:1 Changed 3 years ago by pramsey

Resolution: fixed
Status: newclosed

In 16371:

Apply node sorting before descent to CIRC_NODE trees for
faster calculation of geography distances.
Closes #4010

Note: See TracTickets for help on using tickets.