Fuzzystrmatch: Why is difference() slow and how to make it faster.

PostgreSQL manual lists this example for the difference function:

SELECT * FROM s WHERE difference(s.nm, 'john') > 2;

The equivalent and faster way to do it is:

SELECT * FROM s WHERE (4 - levenshtein(soundex(s.nm),soundex('john'),99,99,1)) > 2; 

The test data:

CREATE TABLE fuzzy_test AS 
  SELECT md5(i::text) AS str
  FROM generate_series(1,1000000) AS i;

The test:

postgres=# \timing
Timing is on.
postgres=# SELECT Count(Difference(str,md5('1'))) FROM fuzzy_test;
  count
---------
 1000000
(1 row)


Time: 3160,953 ms
postgres=# SELECT Count(Levenshtein(Soundex(str),Soundex(Md5('1')),99,99,1)) FROM fuzzy_test;
  count
---------
 1000000
(1 row)


Time: 2077,191 ms

Why? Because using difference() pg has to calculate the soundex for 'john' on each row and in the other query it's evaluated only once, if we wouldn't use a static parameter difference() would be faster.

10 najbardziej odludnych miejscowości w Polsce

Cel: znalezienie miejscowości w Polsce najbardziej oddalonych od cywilizacji Realizacja: Zakładamy że miejscowość najbardziej oddalona od cywilizacji to taka której odległość od najbliższego sąsiada jest największa. Jako źródło posłużą nam dane z OSM pobrane z dumpa udostępnionego przez GeoFabrik. Użyjemy polskiego układu odniesienia SRID 2180

SELECT p1.gid,p1.name,p2.name AS closest,p1.geom<->p2.geom AS "4326_dist",p1.geom2<->p2.geom2 AS "2180_dist",ST_DISTANCE(p2.geog,p1.geog,TRUE) as geog_dist FROM
  ( SELECT p1.gid as g1,
     (SELECT p.gid
      FROM places AS p
      WHERE p1.gid<>p.gid
        AND p.type<>'locality'
      ORDER BY p.geom2<->p1.geom2 ASC LIMIT 1) AS g2
      FROM places AS p1
      WHERE p1.type NOT IN ('locality','suburb') 
      OFFSET 0
) AS q
JOIN places AS p1
  ON q.g1=p1.gid
JOIN places AS p2
  ON q.g2=p2.gid
ORDER BY "2180_dist" DESC
LIMIT 10;

EXPLAIN ANALYZE Interesują nas tylko miejscowości ale mierzymy ich odległość od przedmieść by choć trochę nadrobić to że nie mierzymy faktycznych granic administracyjnych.

  gid  |   name    |    closest     |     4326_dist      |    2180_dist     |    geog_dist
-------+-----------+----------------+--------------------+------------------+------------------
  8426 | Jastrowie | Ptusza         | 0.0616304650991193 | 6306.86042240474 | 6309.65174708274
  7930 | Niekursko | Sarcz          | 0.0696506877357633 | 6059.07941299731 | 6061.08526001983
 28586 | Hel       | Hel Bór        | 0.0653122224030758 | 6057.77326343045 | 6062.04615190325
  7297 | Szwecja   | Ostrowiec      | 0.0617091111621273 | 5865.59766775731 | 5867.79900767539
  7808 | Ostrowiec | Wałcz          | 0.0708066344153986 | 5459.97500003219 |  5461.9397373565
  7488 | Skórka    | Paruszka       | 0.0559207089411363 | 5383.63952364084 | 5386.10143273522
    74 | Kuźnica   | Chałupy        | 0.0754909744769629 |  5337.0960945683 | 5340.76237394738
    75 | Chałupy   | Kuźnica        | 0.0754909744769629 |  5337.0960945683 | 5340.76237394726
 24770 | Wołosate  | Ustrzyki Górne | 0.0537518787199188 | 5229.74155008295 | 5228.79126557615
 53625 | Łebki     | Kamińsko       | 0.0636011795158242 | 5157.97617185783 | 5161.54924296325

Wyniki z indeksu dla geometry dla SRID 2180 są dość zbliżone do tych z typu geography, te dla geometry SRID 4326 niestety dość odbiegają. Można też zauważyć że przy użyciu geography dystans z Kuźnicy do Chałup jest mniejszy niż z Chałup do Kuźnicy. Podmieniamy pierwszą linijkę na:

SELECT p1.gid,
       RANK() OVER (ORDER BY p1.geom<->p2.geom DESC)  AS "4326_rank",
       RANK() OVER (ORDER BY p1.geom2<->p2.geom2 DESC) AS "2180_rank",
       RANK () OVER (ORDER BY ST_DISTANCE(p2.geog,p1.geog,TRUE) DESC) as geog_rank

I otrzymujemy porównanie sortowania:

  gid  | 4326_rank | 2180_rank | geog_rank
-------+-----------+-----------+-----------
  8426 |        26 |         1 |         1
  7930 |         7 |         2 |         3
 28586 |        12 |         3 |         2
  7297 |        24 |         4 |         4
  7808 |         6 |         5 |         5
  7488 |        52 |         6 |         6
    74 |         1 |         7 |         7
    75 |         1 |         7 |         8
 24770 |        77 |         9 |         9
 53625 |        17 |        10 |        10

Rzutki, Pi i PostGIS.

Przybliżenie liczby Pi metodą Monte Carlo. Czyli gra w rzutki. Wieszamy tarczę do gry w rzutki na kwadratowej desce o boku równym średnicy tarczy. Po kilku kolejkach gry liczymy stosunek rzutek które trafiły w tarczę do liczby rzutek które trafiły w tarczę lub deskę i mnożymy razy cztery by uzyskać liczbę Pi. Im więcej rzutek tym dokładniejsze przybliżenie.

Na początek musimy się wygenerować losowe punkty w PostGISie:

SELECT st_makepoint((2.0*random()-1),(2.0*random()-1))

FROM generate_series(1,100);

To zapytanie wygeneruje nam sto punktów których x,y leży w przedziale <-1.0,1.0), następnie obliczamy stosunek punktów leżących w kole do ogółu:

SELECT sum(st_dwithin(point,st_makepoint(0,0), 1.0)::int)::float/count(*)*4

FROM

(SELECT st_makepoint((2.0*random()-1),(2.0*random()-1)) AS point

FROM generate_series(1,100)) AS q;

Zmierzymy przybliżenie dla stu punktów a następnie dla tysiąca, dziesięciu tysięcy i stu tysięcy (wizualizacja w OpenJUMP).

100 punktów Pi=3,36

 1000 punktów Pi=3,156

 10 tysięcy punktów Pi=3.1336

100 tysięcy punktów Pi=3.141

I na sam koniec, zapytanie do generowania danych do wykresu:

WITH RECURSIVE t(n,point, circ,pi) AS (

    SELECT 1 as n,point, ST_DWithin(point,ST_MAKEPOINT(0,0), 1.0)::int AS circ, ST_DWithin(point,ST_MAKEPOINT(0,0), 1.0)::int::float/1*4 as pi

    FROM (SELECT ST_MAKEPOINT((2.0*random()-1),(2.0*random()-1)) as point) as q

  UNION ALL

    SELECT t.n+1 as n,q.point, circ + ST_DWithin(q.point,ST_MAKEPOINT(0,0), 1.0)::int,

    ((circ + ST_DWithin(q.point,ST_MAKEPOINT(0,0), 1.0)::int::float)/(n+1))*4 as pi

    FROM (SELECT ST_MAKEPOINT((2.0*random()-1),(2.0*random()-1)) as point) as q,t

    WHERE n<10000   

)

SELECT * FROM t;