Optimieren einer Proximity-basierten Store Location Search auf einem gemeinsam genutzten Webhost?

11

Ich habe ein Projekt, in dem ich einen Store Locator für einen Kunden erstellen muss.

Ich verwende einen benutzerdefinierten Beitragstyp " restaurant-location" und habe den Code zum Geokodieren der in Postmeta gespeicherten Adressen mithilfe der Google Geocoding-API geschrieben (hier ist der Link, der das Weiße Haus der USA in JSON geokodiert, und ich habe den Breiten- und Längengrad zurückgespeichert zu benutzerdefinierten Feldern.

Ich habe eine get_posts_by_geo_distance()Funktion geschrieben, die eine Liste von Beiträgen in der Reihenfolge derjenigen zurückgibt, die geografisch am nächsten sind, wobei die Formel verwendet wird, die ich in der Diashow in diesem Beitrag gefunden habe . Sie könnten meine Funktion so aufrufen (ich beginne mit einer festen "Quelle" 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;

Hier ist die Funktion get_posts_by_geo_distance()selbst:

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

Ich mache mir Sorgen, dass SQL so wenig wie möglich optimiert ist. MySQL kann nicht nach einem verfügbaren Index sortieren, da das Quell-Geo geändert werden kann und keine endliche Menge von Quell-Geos zwischengespeichert werden muss. Derzeit bin ich ratlos, wie ich es optimieren kann.

Unter Berücksichtigung dessen, was ich bereits getan habe, lautet die Frage: Wie würden Sie diesen Anwendungsfall optimieren?

Es ist nicht wichtig, dass ich alles behalte, was ich getan habe, wenn eine bessere Lösung mich dazu bringen würde, es wegzuwerfen. Ich bin offen für fast jede Lösung, außer für eine, bei der beispielsweise ein Sphinx-Server installiert werden muss oder für die eine angepasste MySQL-Konfiguration erforderlich ist. Grundsätzlich muss die Lösung in der Lage sein, mit jeder einfachen Vanille-WordPress-Installation zu arbeiten. (Das heißt, es wäre großartig, wenn jemand alternative Lösungen für andere auflisten möchte, die möglicherweise fortgeschrittener werden können, und für die Nachwelt.)

Ressourcen gefunden

Zu Ihrer Information, ich habe ein bisschen darüber recherchiert, anstatt dass Sie die Recherche erneut durchführen oder einen dieser Links als Antwort veröffentlichen, werde ich fortfahren und sie einschließen.

In Bezug auf die Sphinx-Suche

MikeSchinkel
quelle

Antworten:

6

Welche Präzision brauchen Sie? Wenn es sich um eine landesweite Suche handelt, können Sie möglicherweise eine Lat-Lon-Zip-Suche durchführen und die Entfernung von Zip-Bereich zu Zip-Bereich des Restaurants vorberechnet haben. Wenn Sie genaue Entfernungen benötigen, ist dies keine gute Option.

Sie sollten sich eine Geohash- Lösung ansehen . Im Wikipedia-Artikel finden Sie einen Link zu einer PHP-Bibliothek, um die Dekodierung für Geohashs zu kodieren.

Hier finden Sie einen guten Artikel, in dem erklärt wird, warum und wie sie in Google App Engine verwendet werden (Python-Code, aber leicht zu befolgen). Da Geohash in GAE verwendet werden muss, finden Sie einige gute Python-Bibliotheken und Beispiele.

Wie in diesem Blogbeitrag erläutert, besteht der Vorteil der Verwendung von Geohashes darin, dass Sie in diesem Feld einen Index für die MySQL-Tabelle erstellen können.

MikeSchinkel
quelle
Vielen Dank für den Vorschlag auf GeoHash! Ich werde es auf jeden Fall ausprobieren, aber in einer Stunde zum WordCamp Savannah aufbrechen, also kann ich es jetzt nicht. Es ist ein Restaurant-Locator für Touristen, die eine Stadt besuchen, also wären 0,1 Meilen wahrscheinlich die minimale Präzision. Im Idealfall wäre es besser als das. Ich werde deine Links bearbeiten!
MikeSchinkel
Wenn Sie die Ergebnisse in einer Google Map anzeigen
Da dies die interessanteste Antwort ist, werde ich sie akzeptieren, obwohl ich keine Zeit hatte, sie zu recherchieren und auszuprobieren.
MikeSchinkel
9

Dies mag für Sie zu spät sein, aber ich werde trotzdem mit einer ähnlichen Antwort antworten, die ich auf diese verwandte Frage gegeben habe , damit zukünftige Besucher auf beide Fragen verweisen können.

Ich würde diese Werte nicht in der Post-Metadatentabelle speichern oder zumindest nicht nur dort. Sie wollen eine Tabelle mit post_id, lat, lonSpalten, so können Sie einen Index setzen lat, lonund Abfrage darauf. Dies sollte nicht zu schwierig sein, um mit einem Hook zum Speichern und Aktualisieren nach dem Start auf dem neuesten Stand zu bleiben.

Wenn Sie die Datenbank abfragen, definieren Sie einen Begrenzungsrahmen um den Startpunkt, sodass Sie eine effiziente Abfrage für alle lat, lonPaare zwischen den Nord-Süd- und Ost-West-Grenzen des Rahmens durchführen können.

Nachdem Sie dieses reduzierte Ergebnis erhalten haben, können Sie eine erweiterte Entfernungsberechnung (kreisförmige oder tatsächliche Fahrtrichtung) durchführen, um die Positionen herauszufiltern, die sich in den Ecken des Begrenzungsrahmens befinden und daher weiter entfernt sind, als Sie möchten.

Hier finden Sie ein einfaches Codebeispiel, das im Admin-Bereich funktioniert. Sie müssen die zusätzliche Datenbanktabelle selbst erstellen. Der Code ist von am wenigsten interessant geordnet.

<?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
quelle
@ Jan : Danke für die Antwort. Denken Sie, Sie können einen tatsächlichen Code bereitstellen, der diese implementiert zeigt?
MikeSchinkel
@ Mike: Es war eine interessante Herausforderung, aber hier ist ein Code, der funktionieren sollte.
Jan Fabry
@ Jan Fabry: Cool! Ich werde es überprüfen, wenn ich auf dieses Projekt zurückspringe.
MikeSchinkel
1

Ich bin zu spät zur Party, aber wenn ich zurückblicke, die get_post_meta ist das hier wirklich das Problem und nicht die SQL-Abfrage, die Sie verwenden.

Ich musste kürzlich eine ähnliche Geo-Suche auf einer von mir ausgeführten Site durchführen und nicht die Metatabelle zum Speichern von Lat und Lon verwenden (für die Suche sind höchstens zwei Joins erforderlich, und wenn Sie get_post_meta verwenden, zwei zusätzliche Datenbanken Abfragen pro Standort) habe ich eine neue Tabelle mit einem räumlich indizierten Geometrie-POINT-Datentyp erstellt.

Meine Anfrage sah Ihrer sehr ähnlich, wobei MySQL einen Großteil des schweren Hebens erledigte (ich habe die Triggerfunktionen weggelassen und alles auf den zweidimensionalen Raum vereinfacht, weil es für meine Zwecke nah genug war):

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

Dabei ist $ client_location ein Wert, der von einem öffentlichen Geo-IP-Suchdienst zurückgegeben wird (ich habe geoio.com verwendet, aber es gibt eine Reihe ähnlicher Werte).

Es mag unhandlich erscheinen, aber beim Testen wurden konsistent die nächsten 5 Positionen aus einer Tabelle mit 80.000 Zeilen in weniger als 0,4 Sekunden zurückgegeben.

Bis MySQL die vorgeschlagene DISTANCE-Funktion einführt, scheint dies der beste Weg zu sein, um Standortsuchen zu implementieren.

BEARBEITEN: Hinzufügen der Tabellenstruktur für diese bestimmte Tabelle. Es handelt sich um eine Reihe von Eigenschaftenlisten, sodass es möglicherweise keinem anderen Anwendungsfall ähnlich ist oder nicht.

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

Die geolocationSpalte ist das einzige, was für die Zwecke hier relevant ist; Es besteht aus x (lon), y (lat) Koordinaten, die ich beim Importieren neuer Werte in die Datenbank von der Adresse aus nachschaue.

goldene Äpfel
quelle
Vielen Dank für das Follow-up. Ich habe wirklich versucht, das Hinzufügen einer Tabelle zu vermeiden, aber am Ende habe ich auch eine Tabelle hinzugefügt, obwohl ich versucht habe, sie allgemeiner als den spezifischen Anwendungsfall zu gestalten. Außerdem habe ich den Datentyp POINT nicht verwendet, weil ich mich an die besser bekannten Standarddatentypen halten wollte. Die Geo-Erweiterungen von MySQL erfordern ein gutes Stück Lernen, um sich wohl zu fühlen. Können Sie Ihre Antwort bitte mit der DDL für Ihre verwendete Tabelle aktualisieren? Ich denke, es wäre lehrreich für andere, die dies in Zukunft lesen.
MikeSchinkel
0

Berechnen Sie einfach die Abstände zwischen allen Entitäten vor. Ich würde das in einer eigenen Datenbanktabelle speichern, mit der Fähigkeit, Werte zu indizieren.

hakre
quelle
Das ist eine praktisch unendliche Anzahl von Aufzeichnungen ...
MikeSchinkel
Unendlich? Ich sehe hier nur n ^ 2, das ist nicht unendlich. Insbesondere bei immer mehr Einträgen sollte die Vorkultierung immer mehr berücksichtigt werden.
hakre
Praktisch unendlich. Bei Lat / Long mit einer Genauigkeit von 7 Dezimalstellen würde dies 6.41977E + 17 Datensätze ergeben. Ja, wir haben nicht so viele, aber wir hätten viel mehr als alles, was vernünftig wäre.
MikeSchinkel
Unendlich ist ein gut definierter Begriff, und das Hinzufügen von Adjektiven ändert nicht viel. Aber ich weiß, was du meinst, du denkst, das ist einfach zu viel, um es zu berechnen. Wenn Sie im Laufe der Zeit nicht fließend eine große Anzahl neuer Speicherorte hinzufügen, kann diese Vorberechnung Schritt für Schritt von einem Job durchgeführt werden, der außerhalb Ihrer Anwendung im Hintergrund ausgeführt wird. Die Genauigkeit ändert nichts an der Anzahl der Berechnungen. Die Anzahl der Standorte reicht aus. Aber vielleicht habe ich diesen Teil Ihres Kommentars falsch verstanden. Zum Beispiel führen 64 Standorte zu 4 096 (oder 4 032 für n * (n-1)) Berechnungen und damit zu Aufzeichnungen.
hakre