Enable Prefix Extension for Fast String Matching in PolarDB PostgreSQL - PolarDB

The prefix extension is a third-party extension that adds string prefix matching to PolarDB for PostgreSQL (Compatible with Oracle). It defines the prefix_range data type and a set of operators for finding all rows whose prefix column matches a given string — or for finding the single longest-matching prefix.

A common use case is call routing in telephony applications: given a dialed number, find the operator whose prefix best matches it.

SELECT *
    FROM prefixes
    WHERE prefix @> '0123456789'
ORDER BY length(prefix) DESC
    LIMIT 1;

Prerequisites

Before you begin, ensure that you have:

A PolarDB for PostgreSQL (Compatible with Oracle) cluster running version 2.0, revision 2.0.14.18.0 or later

To check your version, run:

SHOW polar_version;

Enable the extension

CREATE EXTENSION prefix;

Set up a table and index

The prefix extension introduces the prefix_range type for storing prefix values. Create a GiST index on the prefix_range column so prefix lookups use an index scan instead of a sequential scan.

The following example creates a sample French telephony operator prefix table:

CREATE TABLE prefixes (
        prefix    prefix_range PRIMARY KEY,
        name      TEXT NOT NULL,
        shortname TEXT,
        status    CHAR DEFAULT 'S',

        CHECK( status IN ('S', 'R') )
);
COMMENT ON COLUMN prefixes.status IS 'S:   - R: reserved';

INSERT INTO prefixes (prefix, name, shortname) VALUES
('010001','COLT TELECOMMUNICATIONS FRANCE','COLT'),
('010002','EQUANT France','EQFR'),
('010003','NUMERICABLE','NURC');

CREATE INDEX idx_prefix ON prefixes USING gist(prefix);

The GiST index is required for efficient prefix lookups. Without it, queries perform a sequential scan of the entire table.

Query examples

Match a prefix

Use the @> (*contains*) operator to test whether a prefix_range value contains a given string:

SELECT '123'::prefix_range @> '123456';
 ?column?
----------
 t
(1 row)

To find all rows whose prefix matches a dialed number:

SELECT * FROM prefixes WHERE prefix @> '01000123';
 prefix |              name              | shortname | status
--------+--------------------------------+-----------+--------
 010001 | COLT TELECOMMUNICATIONS FRANCE | COLT      | S
(1 row)

Find the longest matching prefix

Add ORDER BY length(prefix) DESC LIMIT 1 to return only the most specific match:

SELECT *
    FROM prefixes
    WHERE prefix @> '0123456789'
ORDER BY length(prefix) DESC
    LIMIT 1;

Operator reference

The prefix extension provides two groups of operators.

Comparison operators — same semantics as string comparison:

<=, <, =, <>, >=, >

Set operators:

Operator	Reads as	Description
`@>`	contains	Left prefix contains the right string or prefix
`<@`	is contained by	Left string or prefix is contained by the right prefix
`&&`	overlaps	The two prefixes share at least one common string
`\|`	union	Returns the smallest prefix that contains both inputs
`&`	intersection	Returns the largest prefix contained by both inputs

The following example shows all comparison and overlap operators across several prefix pairs:

SELECT a, b,
       a <= b AS "<=", a < b AS "<", a = b AS "=", a <> b AS "<>", a >= b AS ">=", a > b AS ">",
       a @> b AS "@>", a <@ b AS "<@", a && b AS "&&"
   FROM (SELECT a::prefix_range, b::prefix_range
         FROM (VALUES('123', '123'),
                         ('123', '124'),
                         ('123', '123[4-5]'),
                         ('123[4-5]', '123[2-7]'),
                         ('123', '[2-3]')) AS t(a, b)) AS x;
    a     |    b     | <= | < | = | <> | >= | > | @> | <@ | &&
----------+----------+----+---+---+----+----+---+----+----+----
 123      | 123      | t  | f | t | f  | t  | f | t  | t  | t
 123      | 124      | t  | t | f | t  | f  | f | f  | f  | f
 123      | 123[4-5] | t  | t | f | t  | f  | f | t  | f  | t
 123[4-5] | 123[2-7] | f  | f | f | t  | t  | t | f  | t  | t
 123      | [2-3]    | t  | t | f | t  | f  | f | f  | f  | f
(5 rows)

The following example shows union and intersection results:

SELECT a, b, a | b AS UNION, a & b AS INTERSECT
   FROM (SELECT a::prefix_range, b::prefix_range
         FROM (VALUES('123', '123'),
                         ('123', '124'),
                         ('123', '123[4-5]'),
                         ('123[4-5]', '123[2-7]'),
                         ('123', '[2-3]')) AS t(a, b)) AS x;
    a     |    b     |  union   | intersect
----------+----------+----------+-----------
 123      | 123      | 123      | 123
 123      | 124      | 12[3-4]  |
 123      | 123[4-5] | 123      | 123[4-5]
 123[4-5] | 123[2-7] | 123[2-7] | 123[4-5]
 123      | [2-3]    | [1-3]    |
(5 rows)