db-derby-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Dag H. Wanvik (JIRA)" <j...@apache.org>
Subject [jira] [Comment Edited] (DERBY-532) Support deferrable constraints
Date Tue, 12 Nov 2013 21:42:19 GMT

    [ https://issues.apache.org/jira/browse/DERBY-532?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13820503#comment-13820503
] 

Dag H. Wanvik edited comment on DERBY-532 at 11/12/13 9:41 PM:
---------------------------------------------------------------

Some thoughts about correctness in the last patch, I'd appreciate help in thinking through
this..

Deferrable constraint correctness

# Using serializable BTree scan, on a physically non-unique index.
  Intending to insert key "v", we navigate to the first match, if any,
  of the key (the base row Location - the last column - is not used in
  scan key even if it is physically part of the index). This leaves
  the scan on the first "next" on the first "v" if it exists, or just
  past "v-1" (the slot containing the key just before "v", call it
  "v-1").

# transactions intending to insert value "v" will need to U-lock slot
  containing the value "v-1", since the serializable scan always locks
  previous row.

# One and only one transaction could find "v" missing (and hence OK to
  insert), namely the first to lock "v-1" as part of a serializable
  BTRee scan. [Any other transaction type with a U lock on "v-1" would
  not be looking to insert "v", if it did it would need to do the same
  thing.] Later transactions to lock "v-1" would find "v" committed,
  and so would need to throw (not deferred mode), or postpose checking
  till transaction commit (deferred mode).

# If the lock holder of "v-1" (the first transaction) decides to
  delete "v" or roll back, the road will be open for other
  transactions to insert "v" once the U-lock on "v-1" is released by
  trans one.

# In transactions, SQL mandates duplicates be visible to self later in
  the transaction, which would hold since self owns the X-lock till
  transaction commit time.

# Any other transaction would not see "v", until the X-lock is release
  at commit time (with the exception of read uncommitted transactions).

# Deleted slots are handled (presumably) correctly by the existing
  BTreeScan machinery.

# The above holds for both unique nullable and unique not nullable
  deferrable, since in both cases, we use the same physically
  non-unique index and the same method of checking uniqueness with a
  serializable BTreeScan: the only difference is that insertion of "v"
  would go ahead in the presence of an existing "v" iff the key
  contains one or more nulls. We forego the left-right checking
  currently being done for non-deferrable nullable unique indexes.

# At commit time, all transactions that inserted "v" but found it to
  be a duplicate must check that "v" is now present in max one row in
  the BTree. For this we use a read BTreeScan which releases its locks
  as it goes along (ISOLATION_READ_COMMITTED_NOHOLDLOCK).  By
  navigating to the first "v" we have two cases for the transaction:
  
#* The "v" was present *before* transaction in which it inserted a
  duplicate: it already has a U-lock on the first "v" and and X-lock
  on the newly inserted ones. So, its the scan should be able to
  position a read scan on both kinds of rows, and so detect if there
  is more than one of them.

#* There was no "v" present before this transaction came along, in
  which case it has X-lock to all inserted "v"s. Also in this case,
  the transaction has the locks it needs to position a read scan and
  check.

  
# Possible dead-locks: 
Since the writing transaction takes U and X locks, no other writing
transaction can take U or X locks on these rows (only R is compatible
with U). So since a trans has U and X or "v-1" and "v" and doesn't
need to upgrade that to more locks during the transaction (at least
for the insert of value "v"), two transactions that insert different
values should be free to act concurrently, iff the values are not
adjacent in the Btree.

# As for the checking phase at commit time, the read only BTreeScan used
takes read locks on locks we already have, so again multiple
transaction should be free to both move forward concurrently iff
inserting non adjacent values.

# Any dead-locks should thus be the result of the transactions trying to
read each others inserted values before commit (normal), e.g.
{quote}
t1:    X[v] wants R[z]
t2:    X[z] wants R[v]
{quote}
This window slightly increases as the transactions now need to U-lock
"v-1" which isn't necessary with non deferrable PK indexes, at least
not in read committed mode.



was (Author: dagw):
Some thoughts about correctness in the last patch, I'd appreciate help in thinking through
this..

Deferrable constraint correctness

* Using serializable BTree scan, on a physically non-unique index.
  Intending to insert key "v", we navigate to the first match, if any,
  of the key (the base row Location - the last column - is not used in
  scan key even if it is physically part of the index). This leaves
  the scan on the first "next" on the first "v" if it exists, or just
  past "v-1" (the slot containing the key just before "v", call it
  "v-1").

* transactions intending to insert value "v" will need to U-lock slot
  containing the value "v-1", since the serializable scan always locks
  previous row.

* One and only one transaction could find "v" missing (and hence OK to
  insert), namely the first to lock "v-1" as part of a serializable
  BTRee scan. [Any other transaction type with a U lock on "v-1" would
  not be looking to insert "v", if it did it would need to do the same
  thing.] Later transactions to lock "v-1" would find "v" committed,
  and so would need to throw (not deferred mode), or postpose checking
  till transaction commit (deferred mode).

* If the lock holder of "v-1" (the first transaction) decides to
  delete "v" or roll back, the road will be open for other
  transactions to insert "v" once the U-lock on "v-1" is released by
  trans one.

* In transactions, SQL mandates duplicates be visible to self later in
  the transaction, which would hold since self owns the X-lock till
  transaction commit time.

* Any other transaction would not see "v", until the X-lock is release
  at commit time (with the exception of read uncommitted transactions).

* Deleted slots are handled (presumably) correctly by the existing
  BTreeScan machinery.

* The above holds for both unique nullable and unique not nullable
  deferrable, since in both cases, we use the same physically
  non-unique index and the same method of checking uniqueness with a
  serializable BTreeScan: the only difference is that insertion of "v"
  would go ahead in the presence of an existing "v" iff the key
  contains one or more nulls. We forego the left-right checking
  currently being done for non-deferrable nullable unique indexes.

* At commit time, all transactions that inserted "v" but found it to
  be a duplicate must check that "v" is now present in max one row in
  the BTree. For this we use a read BTreeScan which releases its locks
  as it goes along (ISOLATION_READ_COMMITTED_NOHOLDLOCK).  By
  navigating to the first "v" we have two cases for the transaction:
  
** a) the "v" was present *before* transaction in which it inserted a
  duplicate: it already has a U-lock on the first "v" and and X-lock
  on the newly inserted ones. So, its the scan should be able to
  position a read scan on both kinds of rows, and so detect if there
  is more than one of them.

** b) There was no "v" present before this transaction came along, in
  which case it has X-lock to all inserted "v"s. Also in this case,
  the transaction has the locks it needs to position a read scan and
  check.

  
* Possible dead-locks

Since the writing transaction takes U and X locks, no other writing
transaction can take U or X locks on these rows (only R is compatible
with U). So since a trans has U and X or "v-1" and "v" and doesn't
need to upgrade that to more locks during the transaction (at least
for the insert of value "v"), two transactions that insert different
values should be free to act concurrently, iff the values are not
adjacent in the Btree.

As for the checking phase at commit time, the read only BTreeScan used
takes read locks on locks we already have, so again multiple
transaction should be free to both move forward concurrently iff
inserting non adjacent values.

Any dead-locks should thus be the result of the transactions trying to
read each others inserted values before commit (normal), e.g.
{quote}
t1:    X[v] wants R[z]
t2:    X[z] wants R[v]
{quote}
This window slightly increases as the transactions now need to U-lock
"v-1" which isn't necessary with non deferrable PK indexes, at least
not in read committed mode.


> Support deferrable constraints
> ------------------------------
>
>                 Key: DERBY-532
>                 URL: https://issues.apache.org/jira/browse/DERBY-532
>             Project: Derby
>          Issue Type: Improvement
>          Components: SQL
>            Reporter: Jörg von Frantzius
>            Assignee: Dag H. Wanvik
>              Labels: derby_triage10_11
>         Attachments: deferredConstraints.html, deferredConstraints.html, deferredConstraints.html,
deferredConstraints.html, derby-532-import-1.diff, derby-532-import-1.status, derby-532-import-2.diff,
derby-532-import-3.diff, derby-532-import-3.status, derby-532-more-tests-1.diff, derby-532-more-tests-1.stat,
derby-532-serializable-scan-1.diff, derby-532-syntax-binding-dict-1.diff, derby-532-syntax-binding-dict-1.status,
derby-532-syntax-binding-dict-2.diff, derby-532-syntax-binding-dict-2.status, derby-532-syntax-binding-dict-all-1.diff,
derby-532-testAlterConstraintInvalidation.diff, derby-532-testAlterConstraintInvalidation.status,
derby-532-unique-pk-1.diff, derby-532-unique-pk-1.status, derby-532-unique-pk-2.diff, derby-532-unique-pk-3.diff,
derby-532-unique-pk-3.status, derby-532-xa-1.diff, derby-532-xa-2.diff, derby-532-xa-3.diff,
derby-532-xa-3.status
>
>
> In many situations it is desirable to have constraints checking taking place only at
transaction commit time, and not before. If e.g. there is a chain of foreign key constraints
between tables, insert statements have to be ordered to avoid constraint violations. If foreign
key references are circular, the DML has to be split into insert statements and subsequent
update statements by the user.
> In other words, with deferred constraints checking, life is much easier for the user.
Also it can create problems with softwares such as object-relational mapping tools that are
not prepared for statement ordering and thus depend on deferred constraints checking.



--
This message was sent by Atlassian JIRA
(v6.1#6144)

Mime
View raw message