A cursor object to sequentially read BTree. More...
#include <btcursor.h>
Public Member Functions | |
| bt_cursor_t (StoreID store, bool forward) | |
| bt_cursor_t (StoreID store, const w_keystr_t &lower, bool lower_inclusive, const w_keystr_t &upper, bool upper_inclusive, bool forward) | |
| bt_cursor_t (StoreID store, const w_keystr_t &bound, bool inclusive, bool forward) | |
| ~bt_cursor_t () | |
| rc_t | next () |
| bool | is_valid () const |
| bool | is_forward () const |
| void | close () |
| const w_keystr_t & | key () |
| bool | eof () |
| int | elen () const |
| char * | elem () |
Private Member Functions | |
| void | _init (StoreID store, const w_keystr_t &lower, bool lower_inclusive, const w_keystr_t &upper, bool upper_inclusive, bool forward) |
| rc_t | _locate_first () |
| rc_t | _check_page_update (btree_page_h &p) |
| rc_t | _find_next (btree_page_h &p, bool &eof) |
| void | _release_current_page () |
| void | _set_current_page (btree_page_h &page) |
| w_rc_t | _refix_current_key (btree_page_h &p) |
| Re-fix the page at which the cursor was on with SH mode. More... | |
| rc_t | _advance_one_slot (btree_page_h &p, bool &eof) |
| Chooses next slot and potentially next page for cursor access. More... | |
| rc_t | _make_rec (const btree_page_h &page) |
Private Attributes | |
| StoreID | _store |
| w_keystr_t | _lower |
| w_keystr_t | _upper |
| bool | _lower_inclusive |
| bool | _upper_inclusive |
| bool | _forward |
| bool | _needs_lock |
| bool | _ex_lock |
| bool | _dont_move_next |
| bool | _first_time |
| bool | _eof |
| PageID | _pid |
| pin_for_refix_holder | _pid_bfidx |
| slotid_t | _slot |
| lsn_t | _lsn |
| w_keystr_t | _key |
| w_keystr_t | _tmp_next_key_buf |
| smsize_t | _elen |
| char | _elbuf [SM_PAGESIZE] |
Detailed Description
A cursor object to sequentially read BTree.
This class is used as follows.
// constructs a cursor with search conditions.
bt_cursor_t cursor (volid, storeid,
lower_bound, lower_inclusive,
upper_bound, upper_inclusive,
is_forward_direction);
do {
W_DO(cursor.next());
if (cursor.eof()) {
break;
}
w_keystr_t key = cursor.key();
cvec_t el (cursor.elem(), cursor.elen());
....
} while (true);LSN-and-Concurrency
A cursor object releases latches on the page after each next() call to allow concurrent accesses. Thus, it also checks if the current page has been changed after its last access using _lsn variable.
If it has been changed, and if the page still contains the key we previously read, we just re-locate _slot in the page and goes on.
If it has been changed and also the page doesn't contain the key we previously read any more, we re-locate _pid by re-traversing the tree.
These two events are expensive, but happen only after the LSN check, so they are rare too.
Locking-and-Concurrency
A cursor object also takes locks on the keys and their intervals it read. Here, the complication is that the cursor object has two modes; forward and backward. Unfortunately, these two are not quite symmetric because the key range locks are on half-open interval (a key and open interval on its right).
Also, there's a trade-off between concurrency and overhead. In this class, we try to minimize overhead rather than concurrency. See jira ticket:89 "Cursor case: overhead-concurrency trade-off" (originally trac ticket:91) for more details.
Constructor & Destructor Documentation
§ bt_cursor_t() [1/3]
| bt_cursor_t::bt_cursor_t | ( | StoreID | store, |
| bool | forward | ||
| ) |
Constructs a full scan cursor.
- Parameters
-
[in] store Store ID [in] forward true if this cursor goes forward from lower bound, false if this cursor goes backwards from upper bound.
§ bt_cursor_t() [2/3]
| bt_cursor_t::bt_cursor_t | ( | StoreID | store, |
| const w_keystr_t & | lower, | ||
| bool | lower_inclusive, | ||
| const w_keystr_t & | upper, | ||
| bool | upper_inclusive, | ||
| bool | forward | ||
| ) |
Creates a BTree cursor object for the given search conditions.
- Parameters
-
[in] store Store ID [in] lower lower bound of the search range [in] lower_inclusive true if returning a tuple exactly matching the lower bound [in] upper upper bound of the search range [in] upper_inclusive true if returning a tuple exactly matching the upper bound [in] forward true if this cursor goes forward from lower bound, false if this cursor goes backwards from upper bound.
§ bt_cursor_t() [3/3]
| bt_cursor_t::bt_cursor_t | ( | StoreID | store, |
| const w_keystr_t & | bound, | ||
| bool | inclusive, | ||
| bool | forward | ||
| ) |
Constructs an open-end scan, with a start condition only.
- Parameters
-
[in] store Store ID [in] bound start condition for the scan (lower if forward, upper otherwise) [in] inclusive true if returning a tuple exactly matching the bound [in] forward true if this cursor goes forward from lower bound, false if this cursor goes backwards from upper bound.
§ ~bt_cursor_t()
|
inline |
Member Function Documentation
§ _advance_one_slot()
|
private |
Chooses next slot and potentially next page for cursor access.
Computes the next slot, which might be on a successor to p, or even a successor to the successor, in which case, p will be re-fixed to the page, and "slot" indicate where on that page it is. Leave exactly one page fixed.
- Parameters
-
[in] p fixed current page [out] eof whether this cursor reached the end
§ _check_page_update()
|
private |
§ _find_next()
|
private |
§ _init()
|
private |
§ _locate_first()
|
private |
§ _make_rec()
|
private |
Make the cursor point to record at "slot" on "page".
§ _refix_current_key()
|
private |
Re-fix the page at which the cursor was on with SH mode.
In most cases, this method just re-fixes the page ID we observed before. However, fix_direct might fail if the disk page is corrupted. In that case, we need the parent page to apply Single-Page-Recovery on the corrupted page (eBF_DIRECTFIX_SWIZZLED_PTR). Thus, we re-locate the key by traversing from the root. This is expensive, but does not happen often.
- Parameters
-
[out] p page handle that will hold the re-fixed page
§ _release_current_page()
|
private |
§ _set_current_page()
|
private |
§ close()
| void bt_cursor_t::close | ( | ) |
§ elem()
|
inline |
§ elen()
|
inline |
§ eof()
|
inline |
Admittedly bad naming, but this means if the cursor still has record to return. So, even if it's not quite the end of file or index, it returns true when it exceeds the upper-condition.
§ is_forward()
|
inline |
§ is_valid()
|
inline |
§ key()
|
inline |
§ next()
| rc_t bt_cursor_t::next | ( | ) |
Moves the BTree cursor to next slot.
Member Data Documentation
§ _dont_move_next
|
private |
Whether we should move on to next key on the subsequent next() call.
§ _elbuf
|
private |
buffer to store the current record (el).
§ _elen
|
private |
length of current record(el).
§ _eof
|
private |
true if no element left.
§ _ex_lock
|
private |
§ _first_time
|
private |
true if the first next() has not been called.
§ _forward
|
private |
§ _key
|
private |
current key.
§ _lower
|
private |
§ _lower_inclusive
|
private |
§ _lsn
|
private |
lsn of the current page AS OF last access.
§ _needs_lock
|
private |
these are retrieved from xct() when the cursur object is made.
§ _pid
|
private |
id of current page. current page has additional pin_count for refix().
§ _pid_bfidx
|
private |
current page's corresponding slot index in the bufferpool.
§ _slot
|
private |
current slot in the current page.
§ _store
|
private |
§ _tmp_next_key_buf
|
private |
only internally used as temporary variable.
§ _upper
|
private |
§ _upper_inclusive
|
private |
The documentation for this class was generated from the following files:
- src/sm/btcursor.h
- src/sm/btcursor.cpp
