Thread: Guarenteeing ordering constraints
I have some trouble guarenteeing that an ordering constraint is enforced
on the database. On the table ordering (see below) I want to enforce
that for every tuple t, all tuples u where u.position < t.position this
implies u.cumvalue <= t.cumvalue.
Unfortunally postgresql gives me a choice between concurrency or
consistency. Given the trigger procedure below (written for simplicity,
not speed) it will fail to guarentee consistency when using serializable
isolation.
Just load the initial dataset (the failing operations are only to test
the constraints).
The next step is to execute transactions 1 and 2 in parallel (step by
step). This will cause the constraint to be violated.
It does work in the default isolation level (read committed).
Alternatively one can use the second LOCK statement in the trigger,
which does an ACCESS EXCLUSIVE. Obviously this completely defeats
concurrency (causes one of the transactions to be retried).
Is there any way that will both guarentee consistency and provide some
better concurrency?
- Joris
===
CREATE PROCEDURAL LANGUAGE plpgsql;
CREATE TABLE ordering (
"position" integer NOT NULL,
cumvalue integer NOT NULL
);
CREATE FUNCTION tr_ordering_cumvalue_simple() RETURNS "trigger"
AS $$BEGIN
-- position is unique (index enforced)
-- cumvalue constraint
--
-- Let p,q be an element of ordering,
-- where p.position < q.position implies p.cumvalue <=
q.cumvalue
-- Thus for every new tuple t
-- we need to ensure
-- For all p (of ordering) p.position < t.position implies
p.cumvalue <= t.cumvalue
-- and p.position > t.position implies
p.cumvalue >= t.cumvalue
--
-- note (p implies q) <=> (!p or q)
-- lock full table, no others updating it...
LOCK TABLE ordering IN EXCLUSIVE MODE;
--LOCK TABLE ordering IN ACCESS EXCLUSIVE MODE;
IF EXISTS (SELECT *
FROM ordering o
WHERE -- violates constraints
(o.position < NEW.position and o.cumvalue >
NEW.cumvalue)
OR
(o.position > NEW.position and o.cumvalue <
NEW.cumvalue)
)
THEN
RAISE EXCEPTION 'Constraint violation detected by %',
TG_name;
END IF;
RETURN NEW;
END$$
LANGUAGE plpgsql;
CREATE TRIGGER tr_ordering_cumvalue
BEFORE INSERT OR UPDATE ON ordering
FOR EACH ROW
EXECUTE PROCEDURE tr_ordering_cumvalue_simple();
-- initial dataset
BEGIN;
DELETE FROM ordering;
INSERT INTO ordering VALUES (0,0);
INSERT INTO ordering VALUES (10,100);
INSERT INTO ordering VALUES (20,200);
COMMIT;
-- failing operation
BEGIN;
INSERT INTO ordering VALUES (-1,1);
INSERT INTO ordering VALUES (15,1);
INSERT INTO ordering VALUES (16,201);
INSERT INTO ordering VALUES (21,-1);
ROLLBACK;
-- transaction 1
BEGIN ISOLATION LEVEL SERIALIZABLE;;
SELECT * FROM ordering;
INSERT INTO ordering VALUES (19,101);
SELECT * FROM ordering;
COMMIT;
-- transaction 2
BEGIN ISOLATION LEVEL SERIALIZABLE;
SELECT * FROM ordering;
INSERT INTO ordering VALUES (11,199);
SELECT * FROM ordering;
COMMIT;
Even this can be violated. Just create another table and change the first select statement of the transactions to get data from that table. Is there any way to actually enforce such ordering constraints under postgresql? - Joris >-----Original Message----- >From: pgsql-general-owner@postgresql.org >[mailto:pgsql-general-owner@postgresql.org] On Behalf Of Joris >Dobbelsteen >Sent: donderdag 22 februari 2007 14:27 >To: pgsql-general@postgresql.org >Subject: [GENERAL] Guarenteeing ordering constraints > >I have some trouble guarenteeing that an ordering constraint >is enforced on the database. On the table ordering (see below) >I want to enforce that for every tuple t, all tuples u where >u.position < t.position this implies u.cumvalue <= t.cumvalue. > >Unfortunally postgresql gives me a choice between concurrency >or consistency. Given the trigger procedure below (written for >simplicity, not speed) it will fail to guarentee consistency >when using serializable isolation. >Just load the initial dataset (the failing operations are only >to test the constraints). >The next step is to execute transactions 1 and 2 in parallel >(step by step). This will cause the constraint to be violated. > >It does work in the default isolation level (read committed). >Alternatively one can use the second LOCK statement in the >trigger, which does an ACCESS EXCLUSIVE. Obviously this >completely defeats concurrency (causes one of the transactions >to be retried). > >Is there any way that will both guarentee consistency and >provide some better concurrency? > >- Joris > >=== > >CREATE PROCEDURAL LANGUAGE plpgsql; > >CREATE TABLE ordering ( > "position" integer NOT NULL, > cumvalue integer NOT NULL >); > >CREATE FUNCTION tr_ordering_cumvalue_simple() RETURNS "trigger" > AS $$BEGIN > -- position is unique (index enforced) > -- cumvalue constraint > -- > -- Let p,q be an element of ordering, > -- where p.position < q.position implies p.cumvalue <= >q.cumvalue > > -- Thus for every new tuple t > -- we need to ensure > -- For all p (of ordering) p.position < t.position >implies p.cumvalue <= t.cumvalue > -- and p.position > t.position implies >p.cumvalue >= t.cumvalue > -- > -- note (p implies q) <=> (!p or q) > > -- lock full table, no others updating it... > LOCK TABLE ordering IN EXCLUSIVE MODE; > --LOCK TABLE ordering IN ACCESS EXCLUSIVE MODE; > > IF EXISTS (SELECT * > FROM ordering o > WHERE -- violates constraints > (o.position < NEW.position and o.cumvalue > >NEW.cumvalue) > OR > (o.position > NEW.position and o.cumvalue < >NEW.cumvalue) > ) > THEN > RAISE EXCEPTION 'Constraint violation detected >by %', TG_name; > END IF; > > RETURN NEW; >END$$ > LANGUAGE plpgsql; > >CREATE TRIGGER tr_ordering_cumvalue > BEFORE INSERT OR UPDATE ON ordering > FOR EACH ROW > EXECUTE PROCEDURE tr_ordering_cumvalue_simple(); > > >-- initial dataset >BEGIN; >DELETE FROM ordering; >INSERT INTO ordering VALUES (0,0); >INSERT INTO ordering VALUES (10,100); >INSERT INTO ordering VALUES (20,200); >COMMIT; > >-- failing operation >BEGIN; >INSERT INTO ordering VALUES (-1,1); >INSERT INTO ordering VALUES (15,1); >INSERT INTO ordering VALUES (16,201); >INSERT INTO ordering VALUES (21,-1); >ROLLBACK; > >-- transaction 1 >BEGIN ISOLATION LEVEL SERIALIZABLE;; >SELECT * FROM ordering; >INSERT INTO ordering VALUES (19,101); >SELECT * FROM ordering; >COMMIT; > >-- transaction 2 >BEGIN ISOLATION LEVEL SERIALIZABLE; >SELECT * FROM ordering; >INSERT INTO ordering VALUES (11,199); >SELECT * FROM ordering; >COMMIT; > >---------------------------(end of >broadcast)--------------------------- >TIP 6: explain analyze is your friend >
"Joris Dobbelsteen" <Joris@familiedobbelsteen.nl> writes:
> I have some trouble guarenteeing that an ordering constraint is enforced
> on the database. On the table ordering (see below) I want to enforce
> that for every tuple t, all tuples u where u.position < t.position this
> implies u.cumvalue <= t.cumvalue.
I can't think of any reasonable way to enforce that in SQL. Perhaps you
should consider restructuring your tables in such a way that this
behavior emerges from a constraint that is enforceable --- maybe the
cumulative values should be a (materialized?) view on an underlying
table that contains individual observations.
regards, tom lane
>-----Original Message----- >From: Tom Lane [mailto:tgl@sss.pgh.pa.us] >Sent: donderdag 22 februari 2007 17:16 >To: Joris Dobbelsteen >Cc: pgsql-general@postgresql.org >Subject: Re: [GENERAL] Guarenteeing ordering constraints > >"Joris Dobbelsteen" <Joris@familiedobbelsteen.nl> writes: >> I have some trouble guarenteeing that an ordering constraint is >> enforced on the database. On the table ordering (see below) >I want to >> enforce that for every tuple t, all tuples u where u.position < >> t.position this implies u.cumvalue <= t.cumvalue. > >I can't think of any reasonable way to enforce that in SQL. >Perhaps you should consider restructuring your tables in such >a way that this behavior emerges from a constraint that is >enforceable --- maybe the cumulative values should be a >(materialized?) view on an underlying table that contains >individual observations. Mmm, it seems that I'm beyond the boundaries. I seem to have the habit of wanting just a little more than is possible. Nevertheless this seemed simple enough... Of course there is no way to force the trigger to read all commited rows and be waiting on the (possibly) required uncommitted ones? This may get triggers closer to the constraints (like unqiue indexes and foreign keys). Seems triggers are more for business intelligence... Thinking over the idea, I strongly believe restructing is going to cause more trouble than anything else. Beyond that, there are now enough constraints that I'm sure I cannot enforce anyways. That is, I cannot even think about a good way to do it. The current triggers will prevent bad things most of the time, but not always. At this point that seems good enough for practical situations. Example: You have a printer, that's of some kind of model. With the model you define what cartridges (colors) you can put in. You can now replace a cartridge on a printer. Of course you want to enforce that the color of the cartridge you replace is valid. Same problem, and I'm quite sure I cannot enforce it. I believe something fundamental should change to ensure we can enforce these constraints. At least, that would be a lot nicer. - Joris