[DBMS Internals][Analysis of patent] Deferred Unique Constraint Check

Comments · 15 Views

I want to discuss about deferred constraint check feature.
This article is based on patent(https://patents.google.com/patent/US6105025).

Let's short description we discuss.
During large transactions involving multiple dependancies it is often difficult to process da

[0] References

[1] Requirement

  • Check unique constraint at the point the end of transaction.

[2] Main Idea

  • Enable unique index stores duplicate indexed data vvalues during transaction processing.
  • Keep unique constraint violation count which is the number of duplicate entires in the index.

[3] Design 

[3-0] Basic Environment

  • create table test (name unique, .....);
  • DBMS engine build unique index tree (Almost B+ tree) like that.

     

[3-1] Insert operation

  • Search leaf-node to insert new value with row-identification(a.k.a. rowid).
  • If duplicate, then increment unique constraint violation count by 1.
  • After processing two insert DML, unique index tree becomes like that in order above idea.

  

[3-2] Update operation

  • Search leaf-node to update from old value to new value.
  • If old value is only one occurrence, then reduce unique constarint violation count by 1.
  • If new value is duplicate, then increment unique constraint violation count by 1.
  • After processing one update DML, unique index tree becomes like that in order above idea.

  

[3-3] Delete operation

  • Search leaf-node to delete old row.
  • If old row is only one occurrence, then reduce unique constarint violation count by 1.
  • After processing one delete DML, unique index tree becomes like that in order above idea.

   

[3-4] Commit operation (End of transaction)

  • If unique constarint violation count is 0, then commit.
  • If unique constarint violation count is not 0, then rollback.
  • After processing commit operation, the unique violation count is 0. So, commited.

 

   

[4] Challenge - Concurrency?

  • Same with index locking(Gap locking, Key-Range Locking, Hierarchical locking).
  • Use entry exclusive lock to first entry which is already exising entry.
  • TX#1 blocked TX2 by locking entry exclusivley.

 

  • If not, then insert fake first entry and lock fake first entry.

  • TX#1 blocked TX#2 by locking first entry which is fake.

[5] Summary

  • The deferred unique constraint checking provides a uniqueness-required index and a corresponding non-uniqueness count to support deferred uniqueness constraint enforcement. A uniqueness-required index stores duplicate occurrences of indexed data values that occur during statement or transaction processing. The non-uniqueness count associated with the uniqueness-required index provides a count of the number of indexed data values that occur more than once in the index. Where a non-uniqueness count is not equal to zero, a uniqueness constraint violation remains unresolved. Where an unresolved constraint violation exists at enforcement time, the effects of the processing are removed, rollbacked,. A currently non-unique count can be used to represent the number of uniqueness-required indexes that are "currently non-unique". The currently non-unique count can be examined to determine whether there are any unresolved uniqueness constraint violations. Constraints can be enforced at the end of the processing of a transaction, or within a transaction at a savepoint.

 

Comments