WL#6609: InnoDB GIS: Support Predicate Locking for GIS index
Status: Complete — Priority: Medium
BUG#25847 ADD PREDICATE LOCKING TO AVOID DEADLOCKS DUE TO LOCKING NON-EXISTENT ROWS For InnoDB GIS index, it is difficult (if not impossible) to use the GAP lock (or next key locking) to support the "repeated read" or "serializable read" isolation level, since there is no such absolute ordering concept in multi-dimension data. So it is difficult to define the "next" key. We proposed to use "Predicate lock" to enforce such consistent read for GIS index. In this case, we might simply lock the MBR (minimum bounding rectangle/box) which is used for the query, and other transactions cannot insert or modify a row that would have matched the condition. The predicate in this case might be limited to rectangle used in GIS query. So it is a fairly specialize "predicate" locking. The problem with predicate locking is its overhead and being expensive. We might need to improve the granularity of predicate locking by "attaching" the predicates to GIS index nodes. So that queries do not touch related nodes (or area) will not be evaluated against such predicates. User Documentation ================== http://dev.mysql.com/doc/relnotes/mysql/5.7/en/news-5-7-5.html http://dev.mysql.com/doc/refman/5.7/en/innodb-transaction-model.html http://dev.mysql.com/doc/refman/5.7/en/innodb-predicate-locks.html
This is tested a part of R-tree implementation (wl 6968). So please see Worklog 6968 for function and non-functional requirement
As we discussed in the high level description, the Predicate lock will be designed in such a way that it is attached to the index node. This greatly reduce the granularity of the lock, thus increase the concurrency. To get to a bit detail, we illustrate the general design decision for the predicate locking. 1: We will use the existing record lock infrastructure for predicate locking. However, the lock is not attached to any particular user record on the page, instead they are all set on record heap number 0 (PAGE_HEAP_NO_INFIMUM). The PAGE_HEAP_NO_INFIMUM is used currently temporarily on lock parking (lock_rec_store_on_page_infimum and lock_rec_restore_from_page_infimum) when records are being moved, predicate lock does not require such lock parking. We will discuss more on how we resolve the compatibility issue in Low Level Design. In this design, the predicate lock is more or less a page level lock. 2. The predicate lock are not in the same lock space as record lock or table lock, so in theory, they do not conflict with each other. It is attached to a different lock hash table on "lock_sys". However, it queues to the transaction lock list as other locks. 3. The Minimum Bounding Rectangle (MBR) will be part of the the predicate lock structure, right after the heap number. 4. There will be separate APIs for predicate lock create, conflict check etc., where the MBR will be involved in deciding whether 2 Lock are compatible or conflicting. 5. The S predicate lock is attached to the node in top - down fashion. Only the leaf level Predicate Lock is used for checking conflicts with insertion. 6. The predicate lock on non-leaf node is needed when ever there is entry MBR adjustment or split, so that the predicate locks on that page needs to be re-evaluated to decide whether it needs to propagate to the leaf node. 7. During node split, the original Predicate lock on the page might also need to evaluated to copy to the new node. 8. To prevent starvation, the insert operation could insert an X lock on the Predicates to the page. 9. There will be no special predicate manager for managing the predicates, which are no mostly managed by the predicate lock system.
Copyright (c) 2000, 2019, Oracle Corporation and/or its affiliates. All rights reserved.