Index for searching in column where the column starts with the provided value

Question

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?

Answer 1

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.

Answer 2

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:

• Can PostgreSQL index array columns?

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.