How to get Postgres to "give up" filtering?

Viewed 94

I have a query that tries to (very naïvely) implement fuzzy searching for country names:

WITH matching_countries AS (
  SELECT * FROM directory.country WHERE id = $1
  UNION
  SELECT * FROM directory.country 
  WHERE
    alpha2 = $2 OR
    alpha3 = $2 OR
    name = $2 OR
    canonical_name = $2 OR
    name LIKE $3 OR
    canonical_name LIKE $3
  UNION
  SELECT country.* FROM directory.country country
  LEFT JOIN directory.country_alias cAlias
    ON cAlias.country_id = country.id
  WHERE
    cAlias.name = $2 OR
    cAlias.name LIKE $3
)
SELECT * FROM matching_countries
ORDER BY LENGTH(name) ASC
LIMIT 1

Ideally this query should just "give up" scanning tables once an accurate match has been found, as every line you go down we sacrifice accuracy to hopefully make a fuzzy match. I thought LIMIT 1 would do this, but it seems to be picking up blatant false-positives from the LIKE filters.

How can I make it "give up"/early-return on a match? I am optimizing this as I had implemented it as multiple individual queries from application-code but it was quite a bit slow to do it that way instead of UNION-ing all queries.

2 Answers

First, I would use UNION ALL instead of UNION to avoid additional sorting.

If you want to rank the results, use something like

WITH matching_countries AS (
    SELECT *,
           1 AS match_level
    FROM directory.country
    WHERE /* first condition */
  UNION ALL
    SELECT *,
           2 AS match_level
    FROM directory.country 
    WHERE /* second condition */
  UNION
    ...
)
SELECT *
FROM matching_countries
ORDER BY match_level, length(name)
LIMIT 1;

This will still execute all the UNION ALL branches, but it will return a match from the first subquery that returned a result.

This appears to work:


SELECT version();

CREATE TABLE country
        ( id integer not null primary key
        , name text
        , canonical_name text
        );
INSERT INTO country(id, name, canonical_name) VALUES
 ( 1, 'United Kingdom', 'UK' )
, ( 2, 'Deutchland', 'DE' )
, ( 3, 'France', 'FR' )
, ( 4, 'Nederland', 'NL' )
        ;

CREATE TABLE country_alias
        ( id SERIAL not null primary key
        , country_id integer not null REFERENCES country(id)
        , name text
        );
INSERT INTO country_alias(country_id, name) VALUES
 ( 1, 'Britain' )
, ( 1, 'Great Britain' )
, ( 2, 'Germany')
, ( 3, 'Marianne')
, ( 3, 'Ohlala')
, ( 4, 'Holland' )
, ( 4, 'Kaaskoppen' )
        ;

----------

prepare onion(integer, text, text) AS
WITH one AS (
  SELECT 'one' AS tag, * FROM country
  WHERE id = $1
  )
, two AS (
        SELECT 'two' AS tag, * FROM country
        WHERE NOT EXISTS ( SELECT * FROM one)
        AND ( name = $2
           OR name ILIKE $3
           OR canonical_name = $2
           OR canonical_name ILIKE $3
           )
        )
, three AS (
        SELECT 'three' AS tag, *
        FROM country co
        WHERE NOT EXISTS ( SELECT * FROM two)
        AND EXISTS ( SELECT *
        FROM country_alias ca
        WHERE ca.country_id = co.id
        AND ( ca.name = $2 OR ca.name ILIKE $3)
        )
)
SELECT * FROM (
        SELECT * FROM one
        UNION ALL SELECT * FROM two
        UNION ALL SELECT * FROM three
        ) six
-- ORDER BY LENGTH(name) ASC
LIMIT 1
        ;

-- EXPLAIN ANALYZE EXECUTE onion(1,'Huge Britain', 'Uk');
EXPLAIN ANALYZE EXECUTE onion(6,'Huge Britain', 'U%');

EXECUTE onion(9,'Ned', 'kaas%');
EXPLAIN ANALYZE EXECUTE onion(11,'Huge Britain', 'U%');
                                                                                                                                                                             

Result:


 PostgreSQL 11.6 on armv7l-unknown-linux-gnueabihf, compiled by gcc (Raspbian 8.3.0-6+rpi1) 8.3.0, 32-bit
(1 row)

CREATE TABLE
INSERT 0 4
CREATE TABLE
INSERT 0 7
PREPARE
                                                                           QUERY PLAN                                                                           
----------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=90.37..90.39 rows=1 width=100) (actual time=0.163..0.165 rows=1 loops=1)
   CTE one
     ->  Index Scan using country_pkey on country  (cost=0.15..2.37 rows=1 width=100) (actual time=0.054..0.055 rows=0 loops=1)
           Index Cond: (id = 6)
   CTE two
     ->  Result  (cost=0.02..27.02 rows=850 width=100) (actual time=0.083..0.084 rows=1 loops=1)
           One-Time Filter: (NOT $1)
           InitPlan 2 (returns $1)
             ->  CTE Scan on one one_1  (cost=0.00..0.02 rows=1 width=0) (actual time=0.002..0.003 rows=0 loops=1)
           ->  Seq Scan on country country_1  (cost=0.00..27.00 rows=850 width=68) (actual time=0.069..0.070 rows=1 loops=1)
                 Filter: ((name = 'Huge Britain'::text) OR (name ~~* 'U%'::text) OR (canonical_name = 'Huge Britain'::text) OR (canonical_name ~~* 'U%'::text))
   CTE three
     ->  Result  (cost=35.52..60.98 rows=425 width=100) (never executed)
           One-Time Filter: (NOT $3)
           InitPlan 4 (returns $3)
             ->  CTE Scan on two two_1  (cost=0.00..17.00 rows=850 width=0) (never executed)
           ->  Hash Join  (cost=35.50..60.96 rows=425 width=68) (never executed)
                 Hash Cond: (co.id = ca.country_id)
                 ->  Seq Scan on country co  (cost=0.00..18.50 rows=850 width=68) (never executed)
                 ->  Hash  (cost=33.00..33.00 rows=200 width=4) (never executed)
                       ->  HashAggregate  (cost=31.00..33.00 rows=200 width=4) (never executed)
                             Group Key: ca.country_id
                             ->  Seq Scan on country_alias ca  (cost=0.00..28.00 rows=1200 width=4) (never executed)
                                   Filter: ((name = 'Huge Britain'::text) OR (name ~~* 'U%'::text))
   ->  Append  (cost=0.00..31.90 rows=1276 width=100) (actual time=0.158..0.159 rows=1 loops=1)
         ->  CTE Scan on one  (cost=0.00..0.02 rows=1 width=100) (actual time=0.060..0.061 rows=0 loops=1)
         ->  CTE Scan on two  (cost=0.00..17.00 rows=850 width=100) (actual time=0.092..0.093 rows=1 loops=1)
         ->  CTE Scan on three  (cost=0.00..8.50 rows=425 width=100) (never executed)
 Planning Time: 2.560 ms
 Execution Time: 1.169 ms
(30 rows)

  tag  | id |   name    | canonical_name 
-------+----+-----------+----------------
 three |  4 | Nederland | NL
(1 row)

Most important detail of ths query plan are the last few lines:

->  CTE Scan on one  (cost=0.00..0.02 rows=1 width=100)
(actual time=0.060..0.061 rows=0 loops=1)
->  CTE Scan on two  (cost=0.00..17.00 rows=850 width=100)
(actual time=0.092..0.093 rows=1 loops=1)
->  CTE Scan on three  (cost=0.00..8.50 rows=425 width=100)
(never executed)

So, one does not yield any rows, causing two to be used, which does results in some rows, such that three does not need to be evaluated at all. (in this case the estimates are off, because the freshly created tables have no valid statistics)

Related