WL#6609: InnoDB GIS: Support Predicate Locking for GIS index

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.