Tag Archives: fuelo

Оптимизиране на MySQL заявки при геолокализирано приложение

Работа, Технологии, , , , , ,

Навярно повечето от вас знаят, че се занимавам със сайта fuelo.net и на мен се стоварват всички технически проблеми. В този пост искам да споделя два от основните проблемите пред подобен род приложения – силно зависими от местоположението на потребителите, и как съм ги разрешил.

1. Намиране на най-близките N обекта (в нашия случай бензиностанции).

Във fuelo използваме MySQL за основен database и една от първите ми оптимизации беше да upgrade-нем до версия 5.7, където има доста подобрения и готови функции, свързани с геолокацията. Първоначално всички заявки свързани с определяне на бензиностанции наблизо бяха нещо от рода на :

$sql = "SELECT *, (6371 * acos( cos( radians(".$lat.") ) * cos( radians(`lat`) ) * cos( radians(`lon`) - radians(".$lon.") ) + sin( radians(".$lat.") ) * sin( radians(`lat`) ) ) ) AS `distance` FROM `gasstations` HAVING `distance` < ".$distance." ORDER BY `distance` ASC";

забележка: всички примери ще бъдат на PHP, а заявките са опростени (без WHERE и LIMIT клаузи) с цел прегледност.

Както виждате тук дори не се използва stored procedure, а цялата haversine формула се изчислява при всяка заявка. Това при малък ненатоварен сайт с неголяма база данни (напр. до 1000 обекта) на практика работи и се използва доста често. Повечето tutorials в интернет препоръчват именно тази формула. Първата ми идея за MySQL 5.7 беше именно да заменим тази формула с вградената (от версия 5.7.6) функция ST_Distance_Sphere. Така горната заявка се свива до:

$sql = "SELECT *, ST_Distance_Sphere(POINT(`lon`, `lat`), POINT(".$lon.", ".$lat."), 6371) AS `distance` FROM `gasstations` HAVING `distance` < ".$distance." ORDER BY `distance` ASC";

Така изчислението на теория (и на практика) става много по-бързо. Забележете, добавения трети параметър на функцията ST_Distance_Sphere, който преобразува изчислението в km, а не в метри както е по подразбиране. Това ни се наложи, за да запазим съвместимостта със функциите, които извикваха тази заявка, а те очакват резултата в километри.
На пръв поглед всичко изглежда супер, но на практика не е. Тази функция наистина изчислява възможно най-бързо разстоянието между две точки, но не използва индекси и затова все пак трябва да обходи всички редове в таблицата, за да подреди резултатите по разстояние. При все по-голяма база (при нас като наближихме 50000 бензиностанции), тази заявка също започна да става бавна. Започнах да мисля как да огранича резултатите, за които се изчислява разстоянието. Както се вижда от заявките (почти) винаги има ограничение в разстоянието (HAVING `distance` <  X) и се зачудих как мога да превърна това X в координати и така да огранича резултатите още преди да започне изчислението и сортирането. Така намерих тази статия (Finding Points Within a Distance of a Latitude/Longitude Using Bounding Coordinates by Jan Philip Matuschek), в която на теория много добре е описан точно моя проблем. Има и source код на Java, както и линкове за други програмни езици, включително и PHP. Това беше точно каквото ми трябваше. Като използвам тази библиотека кода придобива следния вид:

$edison = Geolocation::fromDegrees($lat, $lon);
$coordinates = $edison->boundingCoordinates($distance, 'km');
$lat_min = $coordinates[0]->getLatitudeInDegrees();
$lon_min = $coordinates[0]->getLongitudeInDegrees();
$lat_max = $coordinates[1]->getLatitudeInDegrees();
$lon_max = $coordinates[1]->getLongitudeInDegrees();

$sql = "SELECT *, ST_Distance_Sphere(POINT(`lon`, `lat`), POINT(".$lon.", ".$lat."), 6371) AS `distance` FROM `gasstations` WHERE `lat` > '".$lat_min."' AND `lat` < '".$lat_max."' AND `lon` > '".$lon_min."' AND `lon` < '".$lon_max."' HAVING `distance` < ".$distance." ORDER BY `distance` ASC";

Така вече заявката беше доста по-бърза, обхождаше доста по-малко редове, което подобри работата на MySQL и сървъра като цяло. Аз обаче не се спрях до тук. Хрумна ми как да се възползвам от spatial индекса на MySQL. Първо направих ново поле в таблицата gasstations с име coords и тип POINT. Попълних новото поле от другите две полета, които вече имах, lat и lon , чрез заявката UPDATE `gasstations` SET coords = Point(lon, lat); и след това направих полето spatial index. След тази промяна бях готов за последната ми (за сега) SQL заявка за намиране на най-близките бензиностанции:

$edison = Geolocation::fromDegrees($lat, $lon);
$coordinates = $edison->boundingCoordinates($distance, 'km');
$lat_min = $coordinates[0]->getLatitudeInDegrees();
$lon_min = $coordinates[0]->getLongitudeInDegrees();
$lat_max = $coordinates[1]->getLatitudeInDegrees();
$lon_max = $coordinates[1]->getLongitudeInDegrees();

$sql = "SELECT *, ST_Distance_Sphere(`coords`, POINT(".$lon.", ".$lat."), 6371) AS `distance` FROM `gasstations` WHERE ST_Within(`coords`, ST_MakeEnvelope(Point(".$lon_min.", ".$lat_min."), Point(".$lon_max.", ".$lat_max."))) HAVING `distance` < ".$distance." ORDER BY `distance` ASC;

Същността тук е функцията ST_Within(), която се възползва от spatial index-а на coords и филтрира резултатите още по-бързо. Функцията ST_MakeEnvelope създава “квадрат”, по две крайни точки, в който се ограничава търсенето.

За сега това ми е решението за намиране на най-близките бензиностанции. Не мога да дам сравнителни стойности, защото междувременно условията много се променяха, но на практика нещата вървят много по-добре. Бавните заявки намаляха и натоварването на сървъра спадна.

2. Изобразяване на голям брой обекти на карта

Във fuelo използваме Google Maps за визуално представяне на бензиностанциите на карта. В началото беше лесно – малко обекти – просто показвай всички на картата. След време, както всички, започнахме да използваме js marker clusterer. Така обаче прехвърляме тежките изчисления върху клиента и когато той реши да unzoom-не за да види всички бензиностанции в Европа, може направо да му забие browser-а и/или компютъра. Започнах да търся сървърно решение за clustering на обекти. Решението, което използваме в момента, се нарича geohash. MySQL поддържа geohash функции и с тяхна помощ заявката за server-side clustering става нещо подобно:

$sql = "SELECT `id`, `brand_id`, AVG(lat) as avglat, AVG(lon) as avglon, substring(`geohash`, 1, ".$precise.") as cluster_hash, count(*) as cluster_count
FROM `gasstations`
WHERE ST_Within(`coords`, ST_MakeEnvelope(Point('.$lon_min.', '.$lat_min.'), Point('.$lon_max.', '.$lat_max.')))
GROUP BY `cluster_hash`";

За целта Ви трябват няколко неща:

  • поле geohash (при мен VARCHAR(9) ) в таблицата gasstations, което предварително е попълнено със ST_GeoHash() функцията (и не забравяйте да го update-вате винаги, когато промените координатите на обекта ! )
  • $lon_min, $lat_min, $lon_max и $lat_max , които лесно може да вземете за видимата част на картата от google maps API-то
  • $precise – колко прецизно да е клъстерирането. Основно зависи от zoom level-а на картата и може да си го нагласите според вашите нужди

При изпълнение на заявката получавате всичко необходимо за визуализиране на картата и не е необходимо на използвате client-side clustering:

  • cluster_count е броя обекти в клъстера – ако е 1, значи е само една бензиностанция и може да покажете пинче в зависимост от нейната brand_id. Ако е повече от 1 значи има повече от една бензиностанция в района и показвате клъстерна иконка с цифричка cluster_count, която показва броя.
  • avglat и avglon са средноаритметично от координатите на бензиностанциите и така може да позиционирате клъстерната иконка на “по-правилно” място. Иначе, от самата специфика на geohash алгоритъма, Земята се разделя на правоъгълници и клъстерите Ви ще се наредят като в решетка. Разбира се ако cluster_count e 1, avglat и avglon са координатите на самата бензиностанция.

 

Това са решенията и заключенията до които стигнах за тези два проблема и ще се радвам, ако съм полезен на някой.

Ново начало

Лични, Работа, Разни, ,

Преди около две седмици с мен се свързаха едни хора, които проявяваха интерес към моя сайт fuelo.net. След няколко срещи, през тези две седмици, се стигна до днес, когато създадохме “Фуело ООД”. Така вече съм съдружник във фирма, за първи път, и то със хора, които на практика не познавам. Общо сме 5 човека, като е хубаво, че всеки е силен в различна област и вярваме, че заедно може да постигнем нещо голямо. За мен най-хубаво, е че Фуело ще може да реализира някои мои идеи, които беше немислимо да се справя сам. Днес беше само началото, от утре започваме да реализираме мечтите си.

1 година Fuelo.net

Разни, , ,

Измина една година откакто, в свободното ми време, се занимавам с Fuelo.net – един сайт, който следи актуалните цени на горивата в България. Опитал съм се на го направя възможно най-автоматизиран, т.е. да прави всичко сам без човешка намеса. Взима цени, чертае графики, прави статистики … но има и доста ръчна работа. Най-трудно ми беше да добавя всички бензиностанции в България – другата голяма цел на fuelo.net. Понеже повечето координати, които намирах в Интернет, се оказваха грешни, се наложи да проверявам всеки обект на няколко места – най-често използвах foursquare, wikimapia и google street view. Покрай Fuelo ми се наложи да направя и се научих на няколко полезни неща. Най горд съм с:

  • Foursquare connected app – идеята беше чудесна, но за съжаление от ноември миналата година Foursquare спряха поддръжката да се отговаря на checkin-и и приложението ми стана безполезно
  • Android приложение – хем съм горд от него, хем съм наясно, че не струва ! В момента е направено с phonegap, но ми се иска да направя native. Ако някой иска да ми помогне – ще съм много благодарен !
  • Fuelo API – малко известен факт, е че Fuelo има API. Идеята ми беше мобилното приложение да го използва, но го пуснах за всички. Документацията не е пълна, но както всеки програмист знае – никога не остава време за документация

Малко статистика

  • Във Fuelo вече има 1216 бензиностанции, метанстанции и електроколонки … и растат
  • Андроид приложението е инсталирано от 158 човека
  • Горд съм, че има посещения от цяла България: fuelo visitors

Накрая – малко благодарности !

  • Първо на Юли, който срещу малко bitcoins направи лого и дизайн на мобилния сайт (m.fuelo.net).
  • На всички марки, които се съгласиха да ми пращат актуални цени да горивата по техните бензиностанции. Поименно искам да благодаря на Мария от Dieselor и Слав от SNG !
  • И разбира се на всички, които използват и харесват Fuelo !

Както виждате , във fuelo, няма реклами и реално нямам никакви приходи от него. Дори съм дал пари за домейна и за google play конзолата. Единствено приемам дарения – за една година съм получил само две дарения – 0,015 биткойна и 1,26лв. през epay.bg.

Цени на горивата

Разни, , , ,

От няколко седмици се занимавам с един страничен проект в свободното ми време. Общо взето започна като тест на highcharts, но постепенно идеята се разрасна и реших да го пусна с надеждата, че на някой може да му е полезно. Май забравих да спомена за какво става дума 🙂 Идеята е сайт, който следи цените на горивата по бензиностанциите. Голямата ми цел е да знам във всеки момент в коя бензиностанция какви горива се предлагат и на каква цена, и да препоръчвам най-близката и най-евтината. Естествено знам, че в България цените навсякъде са изравнени, и някой може да каже, че няма смисъл от такъв сайт, но точно от него може да се види как реално няма конкуренция на пазара и всичко е един голям картел. Адреса на сайта е fuelo.net, като не претендирам за красив дизайн 🙂 За хора като мен, лаици в CSS-а, Bootstrap си е дар 🙂 Пробвайте го от гледна точка на функционалност. Ако забележите грешка – линка „съобщи за неточност“ работи, или просто се свържете с мен по всякакъв начин (може да оставите и коментар по-долу). Като цяло всичко е дълбока beta и като имам време хващам това или онова и се опитвам да оправям бъговете. С течение на времето се надявам да стане по-добър. А ако някой иска да удари едно рамо с дизайн е добре дошъл.

Последното нещо, което добавих е мобилна версия на адрес m.fuelo.net, където акцента е да откриете най-близката бензиностанция, която ви трябва. Усилено използвам местоположението Ви, така че не забранявайте на browser-а Ви да го споделя със сайта – просто няма смисъл.

Ако имате бензиностанция, независимо дали малка или голяма, и публикувате цените си в интернет, с удоволствие бих Ви добавил в сайта и ще Ви препоръчвам да посетителите му. Просто намерете начин да се свържете с мен и ще се разберем.

Като цяло разчитам на потребителите да направим сайта полезен. Просто без актуална информация, той няма да е полезен. Затова влезте в сайта и вижте дали най-близката до Вас бензиностанция е добавена, дали е коректна информацията за нея, дали все още съществува, и съобщете за неточност. А ако я няма, дори може да я добавите.