Maaf, ini bukan jawaban SQL, tetapi cara untuk mendapatkan kinerja yang dapat diprediksi dengan asumsi batasan tertentu pada data Anda.
Seberapa sering data berubah? Jika memungkinkan, dapatkah Anda menghitung terlebih dahulu grafik setiap entitas 5 tetangga terdekat, dan menggunakannya untuk mempercepat pemilihan Anda.?
Jika data ini sebagian besar hanya dapat dibaca, maka...
Seberapa merata titik-titik ini didistribusikan? Jika distribusinya cukup merata dan diketahui dengan baik, maka Anda dapat menggulung pemetaan spasial Anda sendiri dengan memasukkan setiap koordinat dan indeks ke dalam tabel hash.
Jika Anda tidak perlu memiliki data dalam database, pindahkan ke file yang dipetakan memori untuk pencarian hash yang cepat. (Catatan 70m harus mudah masuk ke memori).
Saya telah menggunakan arsitektur ini untuk menghasilkan pencarian sub-milidetik untuk iklan bergambar dan relevansi mesin telusur.
==Elaborasi==
Anda cukup membuat kotak kotak berukuran tetap (seperti papan catur), dan Anda memetakan setiap titik ke dalam kotak, dan Anda membuat daftar objek yang dimiliki penyihir ke dalam setiap kotak kotak -- jika Anda menyesuaikan ukuran masing-masing kotak kotak dengan benar, Anda seharusnya memiliki rata-rata 5-50 poin di setiap kotak -- Ini pada prinsipnya adalah pohon segi empat tetapi tanpa pohon untuk penyederhanaan.
Untuk setiap ember yang kosong setelah Anda menyebarkan semua data dalam ember, Anda menambahkan informasi ember terdekat mana yang berisi data.
Anda sekarang dapat memberi nomor pada setiap ember garis kiri-ke-kanan-baris-ny sehingga setiap ember memiliki nomor unik yang dapat dihitung dari koordinat -- dan Anda memasukkan setiap ember ke dalam tabel hash, atau jika ruang memungkinkan sama seperti tabel pencarian lurus.
Sekarang ketika Anda memiliki kueri, Anda cukup menghitung ember mana yang akan dipetakan, dan Anda akan mendapatkan daftar objek di ember itu, atau Anda akan mendapatkan ember 'kosong' yang berisi pointer ke ember terdekat yang memiliki konten .
Itu akan memberi Anda daftar kandidat pertama objek yang Anda cari, dan sekarang Anda hanya perlu menjalankannya dan melihat mana yang paling dekat.
Dalam 99% kasus itu - tetapi jika Anda khawatir tentang itu (a) ada beberapa kondisi di ember berikutnya yang sebenarnya lebih dekat, maka cukup periksa 8 ember di sekitarnya, dan lihat apakah Anda bisa temukan lebih dekat di sana.
Jika sekarang Anda juga ingin mendapatkan daftar semua objek yang terdekat, maka hitung juga jaringan sederhana dari 5 tetangga terdekat untuk setiap objek, sehingga Anda akan mendapatkan struktur data seperti A->{B,C,D ,E,F}, B->{A,D,G,H,I}, C->{A,J,K,G,M}....
Itu akan membentuk jaringan sederhana yang sekarang dapat Anda lintasi dengan variasi Dijkstra di sini untuk mendapatkan semua titik yang berdekatan dengan titik terdekat Anda.
Membangun struktur data akan memakan waktu, tetapi setelah selesai, dan dilakukan pencarian yang benar dan mengembalikan kumpulan data dapat dilakukan dalam waktu kurang dari milidetik (tidak termasuk http atau komunikasi off-box karena)
Semoga membantu.
