1

I'm trying to create a table with a path column. This table should only allow inserting a new path if the new path is neither an ancestor nor a descendant of any already inserted path. i.e. with '/foo/bar' already in the table:

  • inserting '/foo/bar' should fail
  • inserting '/foo/bar/baz' should fail
  • inserting '/foo/bar/baz/bat' should fail
  • inserting '/foo' should fail
  • inserting '/' should fail
  • inserting '/foo/bar2' should succeed
  • inserting '/foo/baz' should succeed
  • inserting '/fox/bar' should succeed
  • inserting '/xxx/yyy/foo/bar' should succeed

Essentially, these are absolute and fully-resolved (no /../ or /./) unix path to some filesystem directories (they are relative in my precise use case but all will have the same origin so they can be safely compared with the same logic as one would use for absolute paths).

My solution was to try an exclude constraint using the ^@ (aka starts_with) operator (with proper r-trimming and appending of a path delimiter to avoid false-positives, like /foo/bar and /foo/bar2.

with

CREATE TABLE location (
    id UUID NOT NULL, 
    path VARCHAR NOT NULL,  
    EXCLUDE USING btree ((rtrim(path, '/') || '/') WITH ^@)
)

which gets me this error:

Only commutative operators can be used in exclusion constraints.

I know the operator is not commutative, but I (wrongly) expected postgres would see this and do the check both ways (thus excluding both ancestors and descendants).

I've tried looking up alternatives but haven't found one. How can I enforce this constraint at the db level? I really don't want to do this at the application level, as this would force me to deal with race conditions for something that really should be dealt with on the db side (data integrity concerns).

The only other solution I can see is using an insert trigger that select all the rows in the table and throws if any of them matches my condition. This seems inefficient, and a bit ugly (it would essentially be a PL/pgSQL version of that exclude constraint, thus foregoing any performance benefit of an index).

Any ideas ? Thanks in advance :)

1
  • Hi, thank you :) Yes, if /foo/bar exists, /xxx/yyy/foo/bar should be allowed. I'll update the question to be more specific. Nov 9, 2021 at 18:50

1 Answer 1

0

I'm starting to think there isn't a direct answer to this question beyond "it can't be done", so I'll post my workaround for anyone else who stumbles upon this.

I decided to go with the trigger+function option instead of doing the check in the application, because data integrity concerns should remain on the db side.

    ALTER TABLE public.location
        ADD CONSTRAINT ck__location__path_must_be_absolute
            CHECK (starts_with(path, '/'));

    CREATE OR REPLACE FUNCTION public.unique_path_lineage()
        RETURNS TRIGGER AS $unique_path_lineage$

        DECLARE
            new_path text := rtrim(NEW.path, '/') || '/';

        BEGIN
            PERFORM pg_advisory_xact_lock(0);
            IF EXISTS (
                SELECT 1
                FROM public.location AS loc
                WHERE (
                    loc.id <> NEW.id
                    AND (
                        starts_with(
                            rtrim(loc.path, '/') || '/',
                            new_path
                        )
                        OR starts_with(
                            new_path,
                            rtrim(loc.path, '/') || '/',
                        )
                    )
                )
            ) THEN
                RAISE unique_violation
                USING MESSAGE = (
                    'An ascendant or a descendant of path "' 
                    || NEW.path || '" already exists in the table.'
                );
            END IF;
            RETURN NEW;
        END;
    $unique_path_lineage$ LANGUAGE plpgsql;

    CREATE TRIGGER unique_path_lineage
    BEFORE INSERT OR UPDATE OF path
    ON public.location
    FOR EACH ROW
    EXECUTE PROCEDURE public.unique_path_lineage();

A couple of remarks (assumes READ COMMITTED isolation level):

  • I added a check constraint to ensure all paths are absolute. This simplifies comparisons greatly as I don't have to worry about a relative empty-path ('') being considered a parent of an absolute path (both starts_with('/foo/', '') and starts_with('/foo/', rtrim('', '/') || '/') evaluate to TRUE).

  • The function starts by acquiring an exclusive, transaction-level, advisory lock. This is because the function's code introduces a race condition:

    • transaction 1 & 2: BEGIN
    • transaction 1: prepares to INSERT by acquiring a ROW EXCLUSIVE lock on the table.
    • transaction 1: EXISTS(...) -> does not see conflicting data from transaction 2
    • transaction 2: prepares to INSERT conflicting data by attempting to acquire a ROW EXCLUSIVE lock on the table. This does not conflicts with transaction 1's ROW EXCLUSIVE table lock so transaction 2 proceeds.
    • transaction 2: EXISTS(...) -> does not see conflicting data from transaction 1
    • transaction 2: finalizes the INSERT(...); COMMIT -> no error
    • transaction 1: finalizes the INSERT(...); COMMIT -> no error, yet data integrity is compromised.

    The exclusive lock prevents this from happening so we get this sequence instead:

    • transaction 1 & 2: BEGIN
    • transaction 1: prepares to INSERT by acquiring a ROW EXCLUSIVE lock on the table.
    • transaction 1: PERFORM pg_advisory_xact_lock(0); -> exclusive lock acquired
    • transaction 1: EXISTS(...) -> does not see conflicting data from transaction 2
    • transaction 2: prepares to INSERT conflicting data by attempting to acquire a ROW EXCLUSIVE lock on the table. This does not conflicts with transaction 1's ROW EXCLUSIVE table lock so transaction 2 proceeds.
    • transaction 2: PERFORM pg_advisory_xact_lock(0); -> conflicts with transaction 1. Transaction 2 waits.
    • transaction 1: INSERT(...); COMMIT -> no error, exclusive lock is released
    • transaction 2 resumes: EXISTS(...) -> sees conflicting data committed by transaction 1 (because READ COMMITTED)
    • transaction 2: RAISE -> error is raised.

    Data integrity is preserved. The downside is: we've disabled concurrent writes on this table. My initial attempts used an exclusive table lock (LOCK TABLE public.location IN EXCLUSIVE MODE;) instead of an advisory lock. The idea was to prevent other transaction from inserting/updating the path column between EXISTS and INSERT. The problem was that it introduced this deadlock scenario:

    • transaction 1 & 2: BEGIN
    • transaction 1: prepares to INSERT by acquiring a ROW EXCLUSIVE lock on the table.
    • transaction 2: prepares to INSERT by acquiring a ROW EXCLUSIVE lock on the table. No conflicts as two transactions can hold ROW EXCLUSIVE locks on the same table.
    • transaction 1: LOCK TABLE(...) -> EXCLUSIVE lock cannot be acquired because it conflicts with transaction 2's ROW EXCLUSIVE lock. Transaction 1 waits for transaction 2 to release its ROW EXCLUSIVE lock.
    • transaction 2: LOCK TABLE(...) -> EXCLUSIVE lock cannot be acquired because it conflicts with transaction 1's ROW EXCLUSIVE lock. Transaction 2 waits for transaction 1 to release its ROW EXCLUSIVE lock.

    Postgres has protections against deadlocks, so this shouldn't be a problem but it meant that application code had to be ready to retry in the eventuality that the EXCLUSIVE lock couldn't be acquired fast enough. The advisory lock, on the other hand, doesn't conflict with any table lock, so the deadlock isn't possible. We ensure the lock actually protects against concurrent update/insert on the path column by having it inside the before trigger function: no insert/update can execute without acquiring the lock.

  • The trigger protects any modification of the path column by executing on a per-row basis before any insert and any update that includes the path column.

  • Finally, the WHERE clause in the EXISTS takes care of eliminating the current row with loc.id <> NEW.id. This is very important for updates. Without it, UPDATE location SET path='/foo/bar' WHERE path='/foo' would fail because the condition would match the path of the currently updating row as a parent of the new path.

Conclusion: The EXISTS certainly makes things lighter than looping on a SELECT, as I had proposed in my original post. Still, this is neither trivial nor lightweight and the locking is not ideal.

A proper solution to the initial question (or a better alternative) is still welcome :)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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