2

I have a table, where one column contains a substring of an url. It's always the leftmost part of the url without scheme.

id domain column1 column2
1 example.com value1 value2
2 example.org value3 value4
3 example.net/en-US value5 value6
4 example.net/en-GB value7 value8

There's never an overlap in the domains, so there won't be a row with domain example.net, nor a domain that's empty.

I want to search and find the matching row given an url, for example example.org/sub/sub/sub/test.html it should return the row with id 2.

So far I've used SELECT id FROM table WHERE 'example.org/sub/sub/sub/test.html' LIKE (domain || '%') which gives what I want, but it always does a seq scan of the table, even though I have an index on the domain column. I was hoping that Postgres could make some conclusions and use the index anyway.

How can I improve the performance of this?

1
  • Have you thought about extracting the url portion from your input first? Mar 17, 2023 at 19:40

2 Answers 2

2

Q: SELECT id FROM table WHERE 'example.org/sub/sub/sub/test.html' LIKE (domain || '%') which gives what I want, but it always does a seq scan of the table, even though that I have an index on the domain column

The kind of prefix-matching LIKE queries that can use a btree index have this form:

SELECT ... FROM table WHERE column LIKE parameter||'%'

where parameter is a constant and does not itself contain wildcard characters (_ and %)

In the case of this question, that's the opposite: parameter LIKE column||'%'. For one thing, Postgres cannot know in advance if column may contain _ or % characters for some rows. So it needs to read all of them. Even if there was a way to use the btree index to accelerate the matching, it could not be used here.

There's a prefix extension that provides a datatype specifically optimized to find longest prefix matches with the help of a GIST index. It seems like this would work fine for accelerating the kind of search you're doing.

3

It seems like all possible substrings of your input are delimited with the character /. To illustrate my point:

SELECT string_agg(part, '/') OVER (ORDER BY ord) AS prefix
FROM   string_to_table('example.org/sub/test.html', '/') WITH ORDINALITY s(part, ord)
ORDER  BY ord DESC;

          prefix         
---------------------------
 example.org/sub/test.html
 example.org/sub
 example.org

Building on that assumption, here is a highly efficient solution to overcome the principal obstacle Daniel explained:

CREATE OR REPLACE FUNCTION my_longest_prefix(_url text)
  RETURNS SETOF domain
  LANGUAGE plpgsql ROWS 1 STABLE AS
$func$
DECLARE
   _prefix text;
BEGIN
   FOR _prefix IN
      SELECT string_agg(part, '/') OVER (ORDER BY ord)
      FROM   string_to_table(_url, '/') WITH ORDINALITY s(part, ord)
      ORDER  BY ord DESC
   LOOP
      RETURN QUERY
      SELECT d.*
      FROM   domain d
      WHERE  d.domain = _prefix;
      
      EXIT WHEN FOUND;
   END LOOP;
END
$func$;

Call:

SELECT * FROM my_longest_prefix('example.org/sub/sub/sub/test.html');

fiddle

The function exits after the first hit. You get no row if nothing is found.

The "magic" is to switch operands in the filter expression so that the input can be the pattern and the query is "sargable" again.
Also, after splitting the input to its atomic parts, we can match with = instead of LIKE. Now, left & right of the operator don't matter any more because = has a COMMUTATOR (itself) - as opposed to LIKE which does not. Related:

If the input can really be truncated at any position, replace the start of the loop with:

   FOR _prefix IN
      SELECT string_agg(part, '') OVER (ORDER BY ord)
      FROM   string_to_table(_url, null) ...

Only slightly less efficient. Results in one index seek per character in the input. But you'll probably take at least the leading domain as pattern ...

All you need is a plain B-tree index on (domain). From what you told us, there may already be a UNIQUE constraint or index on the column providing said index.

string_to_table() requires Postgres 14 or later. Earlier versions offer various alternatives. The solution does not hinge on this implementation detail.

2
  • Thanks! I played around with this and wrote an alternative using unnest and string_to_array since we're on Postgres 13. We finally went with the prefix extension though, as that was already supported in AWS RDS.
    – Zyberzero
    Mar 23, 2023 at 8:18
  • @Zyberzero Did you get a chance to compare performance of both solutions? A major bonus of this one: it only needs a btree index on (domain) that probably exists anyway. Mar 23, 2023 at 11:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.