Transcript Slides - SEAS - University of Pennsylvania

Retrieving Data from Disk –
Access Methods
Zachary G. Ives
University of Pennsylvania
CIS 650 – Implementing Data Management Systems
January 19, 2005
Slides on B+ and R Trees courtesy of Ramakrishnan & Gehrke
Where We Are
 We’ve now seen an overview of DBMSs, and how
they largely look the same as in the mid-70s
 Now:
 Let’s drill down in more detail
 Today: disk access
 Why it’s a little different from OS access (Stonebraker)
 General principles of indexing (Hellerstein)
 Trivia question: where is GiST used today?
2
Low-Level Disk Access
 What are the central operations needed by a
database management system in accessing pages?




Buffering
Efficiently scannable ranges, i.e. extents
Locking and concurrency
Flushing/forcing to disk
 For managing multiple users?
 Context switching
 Shared memory
 (Avoiding convoys)
3
Search Trees
 We are probably all familiar with the B+ Tree
 To review from CIS 550…
4
B+ Tree: The DB World’s
Favorite Index
 Insert/delete at log F N cost
 (F = fanout, N = # leaf pages)
 Keep tree height-balanced
 Minimum 50% occupancy (except for root).
 Each node contains d <= m <= 2d entries.
d is called the order of the tree.
 Supports equality and range searches efficiently.
Index Entries
(Direct search)
Data Entries
("Sequence set")
Example B+ Tree
 Search begins at root, and key comparisons direct it
to a leaf.
 Search for 5*, 15*, all data entries >= 24* ...
Root
13
2*
3*
5*
7*
14* 16*
17
24
19* 20* 22*
30
24* 27* 29*
33* 34* 38* 39*
 Based on the search for 15*, we know it is not in the tree!
B+ Trees in Practice
 Typical order: 100. Typical fill-factor: 67%.
 average fanout = 133
 Typical capacities:
 Height 4: 1334 = 312,900,700 records
 Height 3: 1333 = 2,352,637 records
 Can often hold top levels in buffer pool:
 Level 1 =
1 page = 8 Kbytes
 Level 2 =
133 pages = 1 Mbyte
 Level 3 = 17,689 pages = 133 MBytes
Inserting Data into a B+ Tree
 Find correct leaf L
 Put data entry onto L
 If L has enough space, done!
 Else, must split L (into L and a new node L2)
 Redistribute entries evenly, copy up middle key
 Insert index entry pointing to L2 into parent of L
 This can happen recursively
 To split index node, redistribute entries evenly, but push up middle key.
(Contrast with leaf splits.)
 Splits “grow” tree; root split increases height.
 Tree growth: gets wider or one level taller at top
Inserting 8* into Example B+ Tree
 Observe how minimum occupancy is guaranteed in
both leaf and index page splits
 Recall that all data items are in leaves, and partition
values for keys are in intermediate nodes
Note difference between copy-up and push-up.
Inserting 8* Example: Copy up
Root
13
2*
3*
5*
7*
17
24
19* 20* 22*
14* 16*
30
24* 27* 29*
33* 34* 38* 39*
Want to insert here; no room, so split & copy up:
8*
Entry to be inserted in parent node.
(Note that 5 is copied up and
continues to appear in the leaf.)
5
2*
3*
5*
7*
8*
10
Inserting 8* Example: Push up
Need to split node
& push up
Root
13
17
24
30
5
2*
3*
19* 20* 22*
14* 16*
5*
7*
24* 27* 29*
8*
Entry to be inserted in parent node.
(Note that 17 is pushed up and only
appears once in the index. Contrast
this with a leaf split.)
17
5
13
24
33* 34* 38* 39*
30
11
Deleting Data from a B+ Tree
 Start at root, find leaf L where entry belongs
 Remove the entry
 If L is at least half-full, done!
 If L has only d-1 entries,
 Try to re-distribute, borrowing from sibling (adjacent node with same
parent as L)
 If re-distribution fails, merge L and sibling
 If merge occurred, must delete entry (pointing to L or sibling)
from parent of L
 Merge could propagate to root, decreasing height
B+ Tree Summary
B+ tree and other indices ideal for range searches, good for
equality searches





Inserts/deletes leave tree height-balanced; logF N cost
High fanout (F) means depth rarely more than 3 or 4
Almost always better than maintaining a sorted file
Typically, 67% occupancy on average
Note: Order (d) concept replaced by physical space criterion in
practice (“at least half-full”)
 Records may be variable sized
 Index pages typically hold more entries than leaves
But What about Generalizing It?
 What if I had:
 Multidimensional data (find a point or a polygon within a
region)
 Set-oriented data (find an instance containing these values)
 Property-oriented queries (as above)
 Let’s start with an overview of R Trees before diving
into GiST
14
R Trees (Guttman 84)
 “Region trees” – multidimensional indices
 Any number of dimensions
 Generally uses containment of bounding boxes, not full polygons, for
efficiency
 Must deal with two issues vs. a B+ Tree:
 Is there a complete ordering?
 Can items overlap without being identical?
 Basic idea of the R Tree:
 Create a tree based on containment of polygons/“rectangles” – child
polygons are contained within parent polygons
15
The R-Tree
 The R-tree is a tree-structured index that remains
balanced on inserts and deletes.
 Each key stored in a leaf entry is intuitively a box, or
collection of intervals, with one interval per
dimension.
Root of
 Example in 2-D:
R Tree
Y
X
Leaf
level
R-Tree Properties
 Leaf entry = < n-dimensional box, rid >
 Box is the tightest bounding box for a data object.
 Non-leaf entry = < n-dim box, ptr to child node >
 Box covers all boxes in child node (in fact, subtree)
 All leaves at same distance from root (height balanced)
 Nodes can be kept 50% full (except root)
 Can choose a parameter m that is <= 50%, and ensure that
every node is at least m% full
Example of an R-Tree
Leaf entry
R1
R4
R3
R8
R9
R10
Index entry
R11
Spatial object
approximated by
bounding box R8
R5 R13
R14
R12
R7
R6
R15
R18
R17
R16
R19
R2
Example R-Tree (Contd.)
R1 R2
R3 R4 R5
R8 R9 R10 R11 R12
R6 R7
R13 R14
R15 R16
R17 R18 R19
Search for Objects Overlapping Box Q
Start at root.
1. If current node is non-leaf, for each
entry <E, ptr>, if box E overlaps Q,
search subtree identified by ptr
2. If current node is leaf, for each entry
<E, rid>, if E overlaps Q, rid identifies
an object that might overlap Q
Note: May have to search several subtrees at each node!
(In contrast, a B-tree equality search goes to just one leaf.)
Insert Entry <B, ptr>
 Start at root and go down to “best-fit” leaf L
 Go to child whose box needs least enlargement to cover B; resolve
ties by going to smallest area child
 This corresponds to the “penalty” in GiST
 If best-fit leaf L has space, insert entry and stop
 Otherwise, split L into L1 and L2
 Adjust entry for L in its parent so that the box now covers (only) L1
 Add an entry (in the parent node of L) for L2
 (This could cause the parent node to recursively split)
Splitting a Node During Insertion
 The entries in node L plus the newly inserted entry
must be distributed between L1 and L2
 Goal is to reduce likelihood of both L1 and L2 being
searched on subsequent queries
 Redistribute to minimize area of L1 plus area of L2
Exhaustive algorithm is too slow;
quadratic and linear heuristics are
used
GOOD SPLIT!
BAD!
R-Tree Variants
 The R* tree uses forced reinserts to reduce overlap in tree
nodes
 When a node overflows, instead of splitting:
 Remove some (say, 30% of the) entries and reinsert them into the tree
 Could result in all reinserted entries fitting on some existing pages,
avoiding a split
 R* trees also use a different heuristic, minimizing box
perimeters rather than box areas during insertion
 Another variant, the R+ tree, avoids overlap by inserting an
object into multiple leaves if necessary
 Searches now take a single path to a leaf, at cost of redundancy
R Trees in Practice
 One of many (dozens of!) multidimensional index
structures
 Perhaps the most popular, though not as ubiquitous as the
B+ Tree
 Implemented in a few DBMSs, such as Oracle, Illustra
(Stonebraker startup, acquired by Informix, then IBM) and
MySQL
24
Generalizing B+ Trees and R Trees: GiST
 Fundamental goal: can we create an index creation toolkit
that can be customized for any kind of index we’d like?
 Doesn’t quite get there – but a nice framework for understanding the
concepts
 Clearly, there seem to be some aspects of the B+ Tree and R
Tree that can be drawn out:
 Height balanced – requires re-organization
 Data on leaves; intermediate nodes help focus on a child
 High fan-out
 Used in PostgreSQL, SHORE
25
Similarities and Differences
 Key differences between B+ Trees and R Trees:
 B+ Tree:
 one-dimensional
 full ordering among data
 R Tree:
 many-dimensional
 no complete ordering among the data
 means that intermediate nodes’ children may fit in more than one
place
 also, intermediate node’s bounding box may have lots of space that’s
not occupied by child nodes (relates to “curse of dimensionality”)
 needs to rely on heuristics about where to insert a node
 may need to search many possible paths along the tree
26
Basic Operations that
Need Customizing for Search
 Contains(node, predicate)
 Returns FALSE only if the node or its children can’t
contain the predicate
 Can return false positives
 What does this correspond to in a B+ Tree? An R Tree?
 What additional work needs to be done if contains() returns
true?
27
Insertion – Simple Case
 Union(entrySet) returns predicate
 Returns a predicate (e.g., bounding box) that holds over a
set (e.g., of children) – basically a disjunction
 Compress(entry) returns entry’
 Simplifies the predicate of the entry, potentially increasing
the chance of false positives
 Decompress(entry) returns entry’
 The inverse of the above – may have false positives
 Penalty(entry1, entry2)
 Gives the cost of inserting entry2 into entry1
28
Insertion – Splitting
 PickSplit(entrySet) returns <entrySet1, entrySet2>
 Splits the set of children in an intermediate node into two
sets
 Typically split according to a “badness metric”
29
Basic Routines
 How do we search for a node set satisfying a
predicate?
 Search(node, predicate)
 For every nonleaf, if Consistent, call recursively on
children; return union of result sets from children
 For leaf, if Consistent, return singleton set, else empty set
 Ordered domains: FindMin(root, predicate), Next(root,
predicate, current)
 Used to do a linear scan of the data at the leaves, if ordered
30
Basic Routines II
 How do we insert a node?
 Insert(node, new, level)
 L = ChooseSubtree(node, new, level)
 If room in L, insert new as a child, else invoke Split(node, L, new)
 AdjustKeys(node, L)
 ChooseSubtree(node, new, level) returns node at level
 Recursively descend tree, minimizing Penalty
 If at desired level, return node
 Among child entries in node, find one with minimal Penalty, return
ChooseSubtree on that child
31
Helper Functions
 Split(root, node, new)
 Invoke PickSplit on union of children of node and new
 Put one partition into node and create a new node’ with the remainder
 Insert all of node’ children into Parent(node) – if insufficient space,
invoke PickSplit on this parent
 Modify the predicate describing node
 AdjustKeys(root, node)
 If node = root, or predicate referring to node is correct, return
 Otherwise,
 modify predicate for node to contain the union of all keys of node
 recursively call AdjustKeys(root, parent(node))
32
Exercise
 In groups of 2, describe how to implement the
following for B+ Trees:




Contains()
Consistent()
Union()
PickSplit()
 Assume that predicates in B+ Trees will be ranges
 What are the major differences in the R Tree
implementation?
33
Next Time
 Query execution principles and strategies
 Should be largely review!
 Sections 1-5, 7
 No review required for this paper
 For Wednesday:
 Read Chaudhuri survey as an overview
 Read and review Selinger et al. paper
34