Mengoptimalkan Pencarian Lokasi Toko Berbasis Kedekatan pada Host Web Bersama?

11

Saya punya proyek di mana saya perlu membangun pencari lokasi toko untuk klien.

Saya menggunakan tipe posting khusus " restaurant-location" dan saya telah menulis kode untuk melakukan geocode alamat yang disimpan dalam postmeta menggunakan Google Geocoding API (inilah tautan yang melakukan geocode Gedung Putih AS di JSON dan saya telah menyimpan lintang dan bujur kembali ke bidang khusus.

Saya telah menulis get_posts_by_geo_distance()fungsi yang mengembalikan daftar posting sesuai urutan yang paling dekat secara geografis menggunakan rumus yang saya temukan dalam tayangan slide di posting ini . Anda dapat memanggil fungsi saya seperti itu (saya mulai dengan lat "panjang" sumber "):

include "wp-load.php";

$source_lat = 30.3935337;
$source_long = -86.4957833;

$results = get_posts_by_geo_distance(
    'restaurant-location',
    'geo_latitude',
    'geo_longitude',
    $source_lat,
    $source_long);

echo '<ul>';
foreach($results as $post) {
    $edit_url = get_edit_url($post->ID);
    echo "<li>{$post->distance}: <a href=\"{$edit_url}\" target=\"_blank\">{$post->location}</a></li>";
}
echo '</ul>';
return;

Inilah fungsinya get_posts_by_geo_distance()sendiri:

function get_posts_by_geo_distance($post_type,$lat_key,$lng_key,$source_lat,$source_lng) {
    global $wpdb;
    $sql =<<<SQL
SELECT
    rl.ID,
    rl.post_title AS location,
    ROUND(3956*2*ASIN(SQRT(POWER(SIN(({$source_lat}-abs(lat.lat))*pi()/180/2),2)+
    COS({$source_lat}*pi()/180)*COS(abs(lat.lat)*pi()/180)*
    POWER(SIN(({$source_lng}-lng.lng)*pi()/180/2),2))),3) AS distance
FROM
    wp_posts rl
    INNER JOIN (SELECT post_id,CAST(meta_value AS DECIMAL(11,7)) AS lat FROM wp_postmeta lat WHERE lat.meta_key='{$lat_key}') lat ON lat.post_id = rl.ID
    INNER JOIN (SELECT post_id,CAST(meta_value AS DECIMAL(11,7)) AS lng FROM wp_postmeta lng WHERE lng.meta_key='{$lng_key}') lng ON lng.post_id = rl.ID
WHERE
    rl.post_type='{$post_type}' AND rl.post_name<>'auto-draft'
ORDER BY
    distance
SQL;
    $sql = $wpdb->prepare($sql,$source_lat,$source_lat,$source_lng);
    return $wpdb->get_results($sql);
}

Kekhawatiran saya adalah bahwa SQL adalah tentang tidak dioptimalkan yang Anda dapatkan. MySQL tidak dapat memesan berdasarkan indeks apa pun yang tersedia karena geo sumber dapat diubah dan tidak ada set sumber geo terbatas untuk cache. Saat ini saya bingung bagaimana cara mengoptimalkannya.

Mempertimbangkan apa yang telah saya lakukan, pertanyaannya adalah: Bagaimana cara mengoptimalkan kasus penggunaan ini?

Tidak penting bahwa saya menyimpan semua yang telah saya lakukan jika solusi yang lebih baik membuat saya membuangnya. Saya terbuka untuk mempertimbangkan hampir semua solusi kecuali untuk yang membutuhkan melakukan sesuatu seperti menginstal server Sphinx atau apa pun yang memerlukan konfigurasi MySQL yang disesuaikan. Pada dasarnya solusinya harus dapat bekerja pada instalasi WordPress vanilla biasa. (Yang mengatakan, alangkah baiknya jika ada yang ingin mendaftar solusi alternatif untuk orang lain yang mungkin bisa menjadi lebih maju dan untuk anak cucu.)

Sumber Ditemukan

FYI, saya melakukan sedikit riset tentang hal ini daripada meminta Anda melakukan penelitian lagi atau daripada meminta Anda memposting tautan-tautan ini sebagai jawaban, saya akan melanjutkan dan memasukkannya.

Mengenai Pencarian Sphinx

MikeSchinkel
sumber

Jawaban:

6

Apa presisi yang Anda butuhkan? Jika pencarian di negara bagian / nasional mungkin Anda bisa melakukan pencarian lat-lon ke zip dan telah menghitung jarak dari daerah zip ke daerah zip restoran. Jika Anda membutuhkan jarak akurat, itu bukan pilihan yang baik.

Anda harus melihat ke solusi Geohash , dalam artikel Wikipedia ada tautan ke perpustakaan PHP untuk menyandikan dekode panjang ke geohash.

Di sini Anda memiliki artikel yang bagus menjelaskan mengapa dan bagaimana mereka menggunakannya di Google App Engine (kode Python tetapi mudah diikuti.) Karena kebutuhan untuk menggunakan geohash di GAE Anda dapat menemukan beberapa pustaka dan contoh python yang baik.

Seperti yang dijelaskan oleh posting blog ini , keuntungan menggunakan geohash adalah Anda dapat membuat indeks pada tabel MySQL di bidang itu.

MikeSchinkel
sumber
Terima kasih atas sarannya di GeoHash! Saya pasti akan memeriksanya tetapi berangkat ke WordCamp Savannah dalam satu jam jadi tidak bisa sekarang. Ini adalah pelacak restoran untuk wisatawan yang mengunjungi kota, jadi 0,1 mil mungkin merupakan ketepatan minimum. Idealnya akan lebih baik dari itu. Saya akan mengedit tautan Anda!
MikeSchinkel
Jika Anda akan menampilkan hasilnya di peta google, Anda dapat menggunakan apinya untuk melakukan sorting code.google.com/apis/maps/documentation/mapsdata/…
Karena ini adalah jawaban yang paling menarik, saya akan menerimanya walaupun saya belum punya waktu untuk meneliti dan mencobanya.
MikeSchinkel
9

Ini mungkin sudah terlambat untuk Anda, tetapi saya tetap akan menjawab, dengan jawaban yang sama seperti yang saya berikan pada pertanyaan terkait ini , sehingga pengunjung di masa mendatang dapat merujuk kedua pertanyaan.

Saya tidak akan menyimpan nilai-nilai ini di tabel metadata posting, atau setidaknya tidak hanya di sana. Anda ingin meja dengan post_id, lat, lonkolom, sehingga Anda dapat menempatkan indeks lat, londan query pada itu. Ini seharusnya tidak terlalu sulit untuk tetap up to date dengan kait di pos simpan dan perbarui.

Saat Anda query database, Anda mendefinisikan kotak pembatas di sekitar titik awal, sehingga Anda bisa melakukan kueri yang efisien untuk semua lat, lonpasangan antara perbatasan utara-selatan dan timur-barat kotak.

Setelah Anda mendapatkan hasil yang dikurangi ini, Anda dapat melakukan perhitungan jarak yang lebih maju (arah mengemudi aktual atau sebenarnya) untuk menyaring lokasi yang berada di sudut kotak pembatas dan karenanya lebih jauh dari yang Anda inginkan.

Di sini Anda menemukan contoh kode sederhana yang berfungsi di area admin. Anda perlu membuat sendiri tabel database tambahan. Kode ini dipesan dari yang paling menarik hingga yang paling tidak menarik.

<?php
/*
Plugin Name: Monkeyman geo test
Plugin URI: http://www.monkeyman.be
Description: Geolocation test
Version: 1.0
Author: Jan Fabry
*/

class Monkeyman_Geo
{
    public function __construct()
    {
        add_action('init', array(&$this, 'registerPostType'));
        add_action('save_post', array(&$this, 'saveLatLon'), 10, 2);

        add_action('admin_menu', array(&$this, 'addAdminPages'));
    }

    /**
     * On post save, save the metadata in our special table
     * (post_id INT, lat DECIMAL(10,5), lon DECIMAL (10,5))
     * Index on lat, lon
     */
    public function saveLatLon($post_id, $post)
    {
        if ($post->post_type != 'monkeyman_geo') {
            return;
        }
        $lat = floatval(get_post_meta($post_id, 'lat', true));
        $lon = floatval(get_post_meta($post_id, 'lon', true));

        global $wpdb;
        $result = $wpdb->replace(
            $wpdb->prefix . 'monkeyman_geo',
            array(
                'post_id' => $post_id,
                'lat' => $lat,
                'lon' => $lon,
            ),
            array('%s', '%F', '%F')
        );
    }

    public function addAdminPages()
    {
        add_management_page( 'Quick location generator', 'Quick generator', 'edit_posts', __FILE__  . 'generator', array($this, 'doGeneratorPage'));
        add_management_page( 'Location test', 'Location test', 'edit_posts', __FILE__ . 'test', array($this, 'doTestPage'));

    }

    /**
     * Simple test page with a location and a distance
     */
    public function doTestPage()
    {
        if (!array_key_exists('search', $_REQUEST)) {
            $default_lat = ini_get('date.default_latitude');
            $default_lon = ini_get('date.default_longitude');

            echo <<<EOF
<form action="" method="post">
    <p>Center latitude: <input size="10" name="center_lat" value="{$default_lat}"/>
        <br/>Center longitude: <input size="10" name="center_lon" value="{$default_lon}"/>
        <br/>Max distance (km): <input size="5" name="max_distance" value="100"/></p>
    <p><input type="submit" name="search" value="Search!"/></p>
</form>
EOF;
            return;
        }
        $center_lon = floatval($_REQUEST['center_lon']);
        $center_lat = floatval($_REQUEST['center_lat']);
        $max_distance = floatval($_REQUEST['max_distance']);

        var_dump(self::getPostsUntilDistanceKm($center_lon, $center_lat, $max_distance));
    }

    /**
     * Get all posts that are closer than the given distance to the given location
     */
    public static function getPostsUntilDistanceKm($center_lon, $center_lat, $max_distance)
    {
        list($north_lat, $east_lon, $south_lat, $west_lon) = self::getBoundingBox($center_lat, $center_lon, $max_distance);

        $geo_posts = self::getPostsInBoundingBox($north_lat, $east_lon, $south_lat, $west_lon);

        $close_posts = array();
        foreach ($geo_posts as $geo_post) {
            $post_lat = floatval($geo_post->lat);
            $post_lon = floatval($geo_post->lon);
            $post_distance = self::calculateDistanceKm($center_lat, $center_lon, $post_lat, $post_lon);
            if ($post_distance < $max_distance) {
                $close_posts[$geo_post->post_id] = $post_distance;
            }
        }
        return $close_posts;
    }

    /**
     * Select all posts ids in a given bounding box
     */
    public static function getPostsInBoundingBox($north_lat, $east_lon, $south_lat, $west_lon)
    {
        global $wpdb;
        $sql = $wpdb->prepare('SELECT post_id, lat, lon FROM ' . $wpdb->prefix . 'monkeyman_geo WHERE lat < %F AND lat > %F AND lon < %F AND lon > %F', array($north_lat, $south_lat, $west_lon, $east_lon));
        return $wpdb->get_results($sql, OBJECT_K);
    }

    /* Geographical calculations: distance and bounding box */

    /**
     * Calculate the distance between two coordinates
     * http://stackoverflow.com/questions/365826/calculate-distance-between-2-gps-coordinates/1416950#1416950
     */
    public static function calculateDistanceKm($a_lat, $a_lon, $b_lat, $b_lon)
    {
        $d_lon = deg2rad($b_lon - $a_lon);
        $d_lat = deg2rad($b_lat - $a_lat);
        $a = pow(sin($d_lat/2.0), 2) + cos(deg2rad($a_lat)) * cos(deg2rad($b_lat)) * pow(sin($d_lon/2.0), 2);
        $c = 2 * atan2(sqrt($a), sqrt(1-$a));
        $d = 6367 * $c;

        return $d;
    }

    /**
     * Create a box around a given point that extends a certain distance in each direction
     * http://www.colorado.edu/geography/gcraft/warmup/aquifer/html/distance.html
     *
     * @todo: Mind the gap at 180 degrees!
     */
    public static function getBoundingBox($center_lat, $center_lon, $distance_km)
    {
        $one_lat_deg_in_km = 111.321543; // Fixed
        $one_lon_deg_in_km = cos(deg2rad($center_lat)) * 111.321543; // Depends on latitude

        $north_lat = $center_lat + ($distance_km / $one_lat_deg_in_km);
        $south_lat = $center_lat - ($distance_km / $one_lat_deg_in_km);

        $east_lon = $center_lon - ($distance_km / $one_lon_deg_in_km);
        $west_lon = $center_lon + ($distance_km / $one_lon_deg_in_km);

        return array($north_lat, $east_lon, $south_lat, $west_lon);
    }

    /* Below this it's not interesting anymore */

    /**
     * Generate some test data
     */
    public function doGeneratorPage()
    {
        if (!array_key_exists('generate', $_REQUEST)) {
            $default_lat = ini_get('date.default_latitude');
            $default_lon = ini_get('date.default_longitude');

            echo <<<EOF
<form action="" method="post">
    <p>Number of posts: <input size="5" name="post_count" value="10"/></p>
    <p>Center latitude: <input size="10" name="center_lat" value="{$default_lat}"/>
        <br/>Center longitude: <input size="10" name="center_lon" value="{$default_lon}"/>
        <br/>Max distance (km): <input size="5" name="max_distance" value="100"/></p>
    <p><input type="submit" name="generate" value="Generate!"/></p>
</form>
EOF;
            return;
        }
        $post_count = intval($_REQUEST['post_count']);
        $center_lon = floatval($_REQUEST['center_lon']);
        $center_lat = floatval($_REQUEST['center_lat']);
        $max_distance = floatval($_REQUEST['max_distance']);

        list($north_lat, $east_lon, $south_lat, $west_lon) = self::getBoundingBox($center_lat, $center_lon, $max_distance);


        add_action('save_post', array(&$this, 'setPostLatLon'), 5);
        $precision = 100000;
        for ($p = 0; $p < $post_count; $p++) {
            self::$currentRandomLat = mt_rand($south_lat * $precision, $north_lat * $precision) / $precision;
            self::$currentRandomLon = mt_rand($west_lon * $precision, $east_lon * $precision) / $precision;

            $location = sprintf('(%F, %F)', self::$currentRandomLat, self::$currentRandomLon);

            $post_data = array(
                'post_status' => 'publish',
                'post_type' => 'monkeyman_geo',
                'post_content' => 'Point at ' . $location,
                'post_title' => 'Point at ' . $location,
            );

            var_dump(wp_insert_post($post_data));
        }
    }

    public static $currentRandomLat = null;
    public static $currentRandomLon = null;

    /**
     * Because I didn't know how to save meta data with wp_insert_post,
     * I do it here
     */
    public function setPostLatLon($post_id)
    {
        add_post_meta($post_id, 'lat', self::$currentRandomLat);
        add_post_meta($post_id, 'lon', self::$currentRandomLon);
    }

    /**
     * Register a simple post type for us
     */
    public function registerPostType()
    {
        register_post_type(
            'monkeyman_geo',
            array(
                'label' => 'Geo Location',
                'labels' => array(
                    'name' => 'Geo Locations',
                    'singular_name' => 'Geo Location',
                    'add_new' => 'Add new',
                    'add_new_item' => 'Add new location',
                    'edit_item' => 'Edit location',
                    'new_item' => 'New location',
                    'view_item' => 'View location',
                    'search_items' => 'Search locations',
                    'not_found' => 'No locations found',
                    'not_found_in_trash' => 'No locations found in trash',
                    'parent_item_colon' => null,
                ),
                'description' => 'Geographical locations',
                'public' => true,
                'exclude_from_search' => false,
                'publicly_queryable' => true,
                'show_ui' => true,
                'menu_position' => null,
                'menu_icon' => null,
                'capability_type' => 'post',
                'capabilities' => array(),
                'hierarchical' => false,
                'supports' => array(
                    'title',
                    'editor',
                    'custom-fields',
                ),
                'register_meta_box_cb' => null,
                'taxonomies' => array(),
                'permalink_epmask' => EP_PERMALINK,
                'rewrite' => array(
                    'slug' => 'locations',
                ),
                'query_var' => true,
                'can_export' => true,
                'show_in_nav_menus' => true,
            )
        );
    }
}

$monkeyman_Geo_instance = new Monkeyman_Geo();
Jan Fabry
sumber
@ Jan : Terima kasih atas jawabannya. Apakah Anda pikir Anda dapat memberikan beberapa kode aktual yang menunjukkan ini diterapkan?
MikeSchinkel
@ Mike: Itu tantangan yang menarik, tapi di sini ada beberapa kode yang bisa digunakan.
Jan Fabry
@ Jan Fabry: Keren! Saya akan memeriksanya ketika saya kembali ke proyek itu.
MikeSchinkel
1

Saya terlambat ke pesta yang satu ini, tapi melihat kembali ke sini, get_post_metaini benar-benar masalah di sini, daripada query SQL yang Anda gunakan.

Saya baru-baru ini harus melakukan pencarian geo yang serupa di situs yang saya jalankan, dan daripada menggunakan tabel meta untuk menyimpan lat dan lon (yang membutuhkan dua gabungan terbaik untuk mencari dan, jika Anda menggunakan get_post_meta, dua database tambahan kueri per lokasi), saya membuat tabel baru dengan tipe data TITIK geometri terindeks spasial.

Permintaan saya sangat mirip dengan milik Anda, dengan MySQL melakukan banyak pengangkatan (saya mengabaikan fungsi trigonometri dan menyederhanakan semuanya menjadi ruang dua dimensi, karena cukup dekat untuk keperluan saya):

function nearby_property_listings( $number = 5 ) {
    global $client_location, $wpdb;

    //sanitize public inputs
    $lat = (float)$client_location['lat'];  
    $lon = (float)$client_location['lon']; 

    $sql = $wpdb->prepare( "SELECT *, ROUND( SQRT( ( ( ( Y(geolocation) - $lat) * 
                                                       ( Y(geolocation) - $lat) ) *
                                                         69.1 * 69.1) +
                                                  ( ( X(geolocation) - $lon ) * 
                                                       ( X(geolocation) - $lon ) * 
                                                         53 * 53 ) ) ) as distance
                            FROM {$wpdb->properties}
                            ORDER BY distance LIMIT %d", $number );

    return $wpdb->get_results( $sql );
}

di mana $ client_location adalah nilai yang dikembalikan oleh layanan pencarian geo IP publik (saya menggunakan geoio.com, tetapi ada sejumlah yang serupa.)

Ini mungkin tampak sulit, tetapi dalam mengujinya, secara konsisten mengembalikan 5 lokasi terdekat dari tabel 80.000 baris dalam waktu 0,4 detik.

Sampai MySQL meluncurkan fungsi DISTANCE yang sedang diusulkan, ini sepertinya cara terbaik yang saya temukan untuk mengimplementasikan pencarian lokasi.

EDIT: Menambahkan struktur tabel untuk tabel khusus ini. Ini adalah set daftar properti, jadi mungkin atau mungkin tidak mirip dengan use case lainnya.

CREATE TABLE IF NOT EXISTS `rh_properties` (
  `listingId` int(10) unsigned NOT NULL,
  `listingType` varchar(60) collate utf8_unicode_ci NOT NULL,
  `propertyType` varchar(60) collate utf8_unicode_ci NOT NULL,
  `status` varchar(20) collate utf8_unicode_ci NOT NULL,
  `street` varchar(64) collate utf8_unicode_ci NOT NULL,
  `city` varchar(24) collate utf8_unicode_ci NOT NULL,
  `state` varchar(5) collate utf8_unicode_ci NOT NULL,
  `zip` decimal(5,0) unsigned zerofill NOT NULL,
  `geolocation` point NOT NULL,
  `county` varchar(64) collate utf8_unicode_ci NOT NULL,
  `bedrooms` decimal(3,2) unsigned NOT NULL,
  `bathrooms` decimal(3,2) unsigned NOT NULL,
  `price` mediumint(8) unsigned NOT NULL,
  `image_url` varchar(255) collate utf8_unicode_ci NOT NULL,
  `description` mediumtext collate utf8_unicode_ci NOT NULL,
  `link` varchar(255) collate utf8_unicode_ci NOT NULL,
  PRIMARY KEY  (`listingId`),
  KEY `geolocation` (`geolocation`(25))
)

The geolocationkolom adalah satu-satunya hal yang relevan untuk tujuan di sini; itu terdiri dari koordinat x (lon), y (lat) yang baru saja saya cari dari alamat setelah mengimpor nilai baru ke dalam basis data.

lempengan emas
sumber
Terima kasih atas tindak lanjutnya. Saya benar-benar mencoba untuk menghindari menambahkan tabel tetapi akhirnya menambahkan tabel juga, meskipun mencoba membuatnya lebih umum daripada use-case tertentu. Lebih jauh, saya tidak menggunakan tipe data POINT karena saya ingin tetap menggunakan tipe data standar yang lebih baik; Ekstensi geo MySQL membutuhkan sedikit pembelajaran agar merasa nyaman. Karena itu, dapatkah Anda memperbarui jawaban Anda dengan DDL untuk tabel yang Anda gunakan? Saya pikir itu akan menjadi pelajaran bagi orang lain yang membaca ini di masa depan.
MikeSchinkel
0

Cukup pra-hitung jarak antara semua entitas. Saya akan menyimpannya dalam tabel database sendiri, dengan kemampuan untuk mengindeks nilai.

hakre
sumber
Itu jumlah yang praktis tak terbatas dari catatan ...
MikeSchinkel
Infinte? Saya hanya melihat n ^ 2 di sini, itu bukan infinte. Apalagi dengan semakin banyak entri, prakalkulturasi harus semakin dipertimbangkan.
hakre
Praktis tak terbatas. Diberikan Lat / Long pada ketelitian 7 tempat desimal yang akan memberikan 6.41977E + 17 catatan. Ya, kami tidak memiliki banyak, tetapi kami akan memiliki lebih dari apa pun yang masuk akal.
MikeSchinkel
Infinite adalah istilah yang didefinisikan dengan baik, dan menambahkan kata sifat padanya tidak banyak berubah. Tapi saya tahu apa yang Anda maksud, Anda pikir ini terlalu banyak untuk dihitung. Jika Anda tidak menambahkan dengan lancar sejumlah besar lokasi baru dari waktu ke waktu, pra-perhitungan ini dapat dilakukan langkah demi langkah oleh pekerjaan yang berjalan terpisah dari aplikasi Anda di latar belakang. Ketepatan tidak mengubah jumlah perhitungan. Jumlah lokasi tidak. Tapi mungkin saya salah membaca bagian dari komentar Anda. Misalnya 64 lokasi akan menghasilkan perhitungan 4 096 (atau 4 032 untuk n * (n-1)) dan karenanya dicatat.
hakre