Optymalizowanie wyszukiwania lokalizacji w oparciu o lokalizację w pobliżu na współdzielonym serwerze internetowym?


11

Mam projekt, w którym muszę zbudować lokalizator sklepu dla klienta.

Używam niestandardowego typu posta „ restaurant-location” i napisałem kod do geokodowania adresów przechowywanych w postmeta za pomocą Google Geocoding API (tutaj link, który geokoduje amerykański Biały Dom w JSON, a ja zapisałem szerokość i długość geograficzną z powrotem do pól niestandardowych.

Napisałem get_posts_by_geo_distance()funkcję, która zwraca listę postów w kolejności tych najbliższych geograficznie, korzystając ze wzoru znalezionego w pokazie slajdów w tym poście . Możesz tak wywołać moją funkcję (zaczynam od stałego „źródła” lat / long):

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;

Oto get_posts_by_geo_distance()sama funkcja :

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);
}

Obawiam się, że SQL jest tak niezoptymalizowany, jak to tylko możliwe. MySQL nie może uporządkować według żadnego dostępnego indeksu, ponieważ geo źródłowe jest zmienne i nie ma skończonego zestawu geo źródłowych do buforowania. Obecnie mam problemy z optymalizacją.

Biorąc pod uwagę to, co już zrobiłem, pytanie brzmi: jak poszedłbyś na optymalizację tego przypadku użycia?

Nie jest ważne, aby zachować wszystko, co zrobiłem, jeśli lepsze rozwiązanie pozwoliłoby mi to wyrzucić. Jestem otwarty na rozważenie prawie każdego rozwiązania, z wyjątkiem takiego, które wymaga zrobienia czegoś takiego jak instalacja serwera Sphinx lub czegokolwiek, co wymaga spersonalizowanej konfiguracji MySQL. Zasadniczo rozwiązanie musi działać na dowolnej zwykłej waniliowej instalacji WordPress. (To powiedziawszy, byłoby wspaniale, gdyby ktokolwiek chciał wymienić alternatywne rozwiązania dla innych, którzy mogliby być bardziej zaawansowani i dla potomnych.)

Znaleziono zasoby

Do Twojej wiadomości, przeprowadziłem trochę badań na ten temat, więc zamiast tego czy robisz to ponownie, czy raczej zamiast publikować którekolwiek z tych linków jako odpowiedź, dodam je.

Odnośnie wyszukiwania Sfinksa

Odpowiedzi:


6

Jakiej precyzji potrzebujesz? jeśli jest to wyszukiwanie ogólnokrajowe / ogólnokrajowe, być może mógłbyś wykonać wyszukiwanie w dowolnym miejscu i mieć wstępnie obliczoną odległość od strefy zip do strefy zip w restauracji. Jeśli potrzebujesz dokładnych odległości, nie będzie to dobra opcja.

Powinieneś przyjrzeć się rozwiązaniu Geohash , w artykule w Wikipedii znajduje się link do biblioteki PHP do kodowania dekodowania długiego do geohashów.

Tutaj masz dobry artykuł wyjaśniający, dlaczego i jak używają go w Google App Engine (kod Python, ale łatwy do naśladowania). Ze względu na potrzebę używania geohash w GAE możesz znaleźć dobre biblioteki i przykłady Pythona.

Jak wyjaśnia ten post na blogu , zaletą korzystania z geohashów jest to, że możesz utworzyć indeks w tabeli MySQL na tym polu.


Dzięki za sugestię dotyczącą GeoHash! Na pewno to sprawdzę, ale za godzinę przejdę do WordCamp Savannah, więc nie mogę teraz. Jest to lokalizator restauracji dla turystów odwiedzających miasto, więc 0,1 mili prawdopodobnie byłby minimalną precyzją. Idealnie byłoby lepiej. Zmienię twoje linki!
MikeSchinkel,

Jeśli zamierzasz wyświetlić wyniki na mapie Google, możesz użyć ich interfejsu API, aby wykonać sortowanie code.google.com/apis/maps/documentation/mapsdata/…

Ponieważ jest to najciekawsza odpowiedź, przyjmuję ją, chociaż nie miałem czasu na badania i wypróbowanie jej.
MikeSchinkel

9

To może być dla ciebie za późno, ale i tak odpowiem, udzielając podobnej odpowiedzi, jak udzieliłem na to powiązane pytanie , aby przyszli odwiedzający mogli odnieść się do obu pytań.

Nie zapisałbym tych wartości w tabeli metadanych posta, a przynajmniej nie tylko tam. Chcesz stół z post_id, lat, lonkolumny, dzięki czemu można złożyć indeks lat, loni zapytania w tej sprawie. To nie powinno być zbyt trudne, aby być na bieżąco z hakiem na zapisywanie i aktualizowanie postów.

Podczas wyszukiwania w bazie danych definiuje się ramkę graniczną wokół punktu początkowego, dzięki czemu można wykonać wydajne zapytanie dla wszystkich lat, lonpar między granicami północ-południe i wschód-zachód ramki.

Po uzyskaniu tego zmniejszonego wyniku możesz wykonać bardziej zaawansowane obliczanie odległości (okrągłe lub rzeczywiste wskazówki dojazdu), aby odfiltrować lokalizacje znajdujące się w rogach ramki ograniczającej i dalej, niż chcesz.

Tutaj znajdziesz prosty przykład kodu, który działa w obszarze administratora. Musisz samodzielnie utworzyć dodatkową tabelę bazy danych. Kod jest uporządkowany od najbardziej do najmniej interesującego.

<?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 : Dzięki za odpowiedź. Czy uważasz, że możesz podać rzeczywisty kod pokazujący te zaimplementowane?
MikeSchinkel,

@Mike: To było ciekawe wyzwanie, ale oto kod, który powinien działać.
Jan Fabry

@Jan Fabry: Cool! Sprawdzę to, kiedy wrócę do tego projektu.
MikeSchinkel

1

Spóźniam się na przyjęcie w tej sprawie, ale patrząc wstecz, get_post_metato naprawdę jest tutaj problem, a nie zapytanie SQL, którego używasz.

Niedawno musiałem przeprowadzić podobne wyszukiwanie geograficzne na stronie, którą prowadzę, i zamiast używać tabeli meta do przechowywania lat i lon (co wymaga co najmniej dwóch sprzężeń, aby wyszukać, a jeśli używasz get_post_meta, dwóch dodatkowych baz danych zapytań na lokalizację), utworzyłem nową tabelę z typem danych przestrzennie indeksowanej geometrii POINT.

Moje zapytanie wyglądało podobnie do twojego, z MySQL wykonującym wiele ciężkich operacji podnoszenia (pominąłem funkcje triggera i uprościłem wszystko do dwuwymiarowej przestrzeni, ponieważ było wystarczająco blisko do moich celów):

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 );
}

gdzie $ lokalizacja_klienta jest wartością zwracaną przez publiczną usługę wyszukiwania geograficznego adresu IP (korzystałem z geoio.com, ale istnieje wiele podobnych).

Może się to wydawać niewygodne, ale podczas jego testowania konsekwentnie zwracał najbliższe 5 lokalizacji ze 80 000-wierszowego stołu w czasie poniżej 0,4 sekundy.

Dopóki MySQL nie uruchomi proponowanej funkcji ODLEGŁOŚĆ, wydaje się to najlepszym sposobem na wdrożenie wyszukiwania lokalizacji.

EDYCJA: Dodanie struktury tabeli dla tej konkretnej tabeli. Jest to zestaw list właściwości, więc może, ale nie musi, być podobny do jakiegokolwiek innego przypadku użycia.

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))
)

geolocationKolumna jest jedyną rzeczą, istotne dla tutejszych celów; składa się ze współrzędnych x (lon), y (lat), które po prostu szukam z adresu po zaimportowaniu nowych wartości do bazy danych.


Dzięki za kontynuację. Naprawdę starałem się unikać dodawania tabeli, ale ostatecznie również dodałem tabelę, choć starałem się, aby była bardziej ogólna niż konkretny przypadek użycia. Ponadto nie użyłem typu danych POINT, ponieważ chciałem trzymać się lepiej znanych standardowych typów danych; Rozszerzenia geograficzne MySQL wymagają sporo nauki, aby czuć się komfortowo. To powiedziawszy, czy możesz zaktualizować swoją odpowiedź za pomocą DDL dla używanego stołu? Myślę, że byłoby to pouczające dla osób czytających to w przyszłości.
MikeSchinkel

0

Wystarczy wstępnie obliczyć odległości między wszystkimi jednostkami. Chciałbym zapisać to w tabeli bazy danych, z możliwością indeksowania wartości.


To praktycznie nieskończona liczba rekordów ...
MikeSchinkel

Infinte? Widzę tu tylko n ^ 2, to nie jest nieskończone. Zwłaszcza przy coraz większej liczbie wpisów należy coraz bardziej rozważać wstępną uprawę.
hakre

Praktycznie nieskończony. Podano Lat / Long z dokładnością do 7 miejsc po przecinku, co dałoby 6,41977E + 17 rekordów. Tak, nie mamy ich tak wiele, ale mielibyśmy o wiele więcej niż to, co byłoby rozsądne.
MikeSchinkel,

Nieskończony jest dobrze zdefiniowanym terminem, a dodawanie do niego przymiotników niewiele się zmienia. Ale wiem, co masz na myśli, myślisz, że to zbyt wiele do obliczenia. Jeśli z biegiem czasu nie dodajesz płynnie ogromnej liczby nowych lokalizacji, to wstępne obliczenia można wykonać krok po kroku przez zadanie działające niezależnie od aplikacji w tle. Precyzja nie zmienia liczby obliczeń. Liczba lokalizacji ma. Ale może źle odczytałem tę część twojego komentarza. Na przykład 64 lokalizacje będą skutkować 4096 (lub 4032 dla n * (n-1)) obliczeń, a tym samym zapisami.
hakre
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.