The right answer is choice #5: use PostGISPostGIS. An example from OpenGeo:
"Note the magic
<->
operator in theORDER BY
clause. This is where the magic occurs. The<->
is a “distance” operator, but it only makes use of the index when it appears in theORDER BY
clause. Between putting the operator in theORDER BY
and using aLIMIT
to truncate the result set, we can very very quickly (less than 10ms on a 2M record table, in this case) get the 10 nearest points to our test point."
(emphasis added)