Uploaded image for project: 'Derby'
  1. Derby
  2. DERBY-2991

Index split deadlock



    • Type: Bug
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s:,,
    • Fix Version/s:
    • Component/s: Store
    • Labels:
    • Environment:
      Windows XP, Java 6
    • Issue & fix info:
      High Value Fix


      After doing dome research on the mailing list, it appears that the index split deadlock is a known behaviour, so I will start by describing the theoretical problem first and then follow with the details of my test case.

      If you have concurrent select and insert transactions on the same table, the observed locking behaviour is as follows:

      • the select transaction acquires an S lock on the root block of the index and then waits for an S lock on some uncommitted row of the insert transaction
      • the insert transaction acquires X locks on the inserted records and if it needs to do an index split creates a sub-transaction that tries to acquire an X lock on the root block of the index

      In summary: INDEX LOCK followed by ROW LOCK + ROW LOCK followed by INDEX LOCK = deadlock

      In the case of my project this is an important issue (lack of concurrency after being forced to use table level locking) and I would like to contribute to the project and fix this issue (if possible). I was wondering if someone that knows the code can give me a few pointers on the implications of this issue:

      • Is this a limitation of the top-down algorithm used?
      • Would fixing it require to use a bottom up algorithm for better concurrency (which is certainly non trivial)?
      • Trying to break the circular locking above, I would first question why does the select transaction need to acquire (and hold) a lock on the root block of the index. Would it be possible to ensure the consistency of the select without locking the index?

      The attached test (InsertSelectDeadlock.java) tries to simulate a typical data collection application, it consists of:

      • an insert thread that inserts records in batch
      • a select thread that 'processes' the records inserted by the other thread: 'select * from table where id > ?'

      The derby log provides detail about the deadlock trace and stacktraces_during_deadlock.txt shows that the inser thread is doing an index split.

      The test was run on and with identical behaviour.


      Bogdan Calmac.


        1. d2991-2a.diff
          436 kB
          Knut Anders Hatlen
        2. d2991-2a.stat
          2 kB
          Knut Anders Hatlen
        3. d2991-2b.diff
          444 kB
          Knut Anders Hatlen
        4. d2991-2b.stat
          2 kB
          Knut Anders Hatlen
        5. d2991-preview-1a.diff
          17 kB
          Knut Anders Hatlen
        6. d2991-preview-1a.stat
          0.4 kB
          Knut Anders Hatlen
        7. d2991-preview-1b.diff
          225 kB
          Knut Anders Hatlen
        8. d2991-preview-1b.stat
          1 kB
          Knut Anders Hatlen
        9. d2991-preview-1c.diff
          261 kB
          Knut Anders Hatlen
        10. d2991-preview-1c.stat
          2 kB
          Knut Anders Hatlen
        11. d2991-preview-1d.diff
          265 kB
          Knut Anders Hatlen
        12. d2991-preview-1d.stat
          2 kB
          Knut Anders Hatlen
        13. d2991-preview-1e.diff
          269 kB
          Knut Anders Hatlen
        14. derby.log
          45 kB
          Bogdan Calmac
        15. InsertSelectDeadlock.java
          6 kB
          Bogdan Calmac
        16. perftest.diff
          10 kB
          Knut Anders Hatlen
        17. Repro2991.java
          4 kB
          Kurt Huwig
        18. stacktraces_during_deadlock.txt
          5 kB
          Bogdan Calmac
        19. test-1.diff
          12 kB
          Knut Anders Hatlen
        20. test-2.diff
          9 kB
          Knut Anders Hatlen
        21. test-3.diff
          12 kB
          Knut Anders Hatlen
        22. test-4.diff
          0.8 kB
          Knut Anders Hatlen

          Issue Links



              • Assignee:
                knutanders Knut Anders Hatlen
                bcalmac Bogdan Calmac
              • Votes:
                13 Vote for this issue
                9 Start watching this issue


                • Created: