Karteikarten
Ohne Titel
Karten in diesem Stapel (52)
- 1index Number of Entries Dense/SparsePrimary
Number of blocks in
data file
Sparse
Clustering
Number of distinct
values
Sparse
Secondary
(key)
Number of records
in data file
Dense
Secondary
(nonkey)
Number of distinct
values (1st level)
Number of records
(2nd level)
Dense - 2Why Multi-Level Indexes?As the size of the database grows, so does the size of the indices. There is an immense need to keep the index records in the main memory so as to speed up the search operations. If single-level index is used, then a large size index cannot be kept in memory which leads to multiple disk accesses.
- 3How many levels do we need?Number of index entries ei
= 1024
n Index blocking factor bfrindex= 4 (aka fan-out fo)
Number of levels = log4 1024 = 5 = logfo ei - 4Search in a multi-level index1) Read one block at each level in the index
Number of accessed index blocks = Number of levels
= logfo ei
2) Read the data block containing the searched record
Total number of accessed blocks = logfo ei + 1 - 5What if we are searching by multiple keys?Bitmap Index
- 6Bitmap SizeSize of each bitmap (in bits) is equal to the number of
rows in the relation
o Number of bitmaps for a field is equal to the number
of distinct values of that field
o Total space needed to index one field (in bits)
=number of distinct values x number of rows
Whereas, file size (in bits)
= record size in bits x number of rows - 7Bitmap LimitationsNot good for data that is modified regularly
n Updates will require modifying all the associated
bitmap indexes - 8Binary Search Treeinary Search Tree
Each node has 2 pointers (left child & right child)
Fan-out = 2 Tree order = 2 - 9General Search treesIn a search tree of order n, each node contains at most:
n n-1 search values (keys), and
n n pointers
fan out n = tree order n - 10Multi-level index is a form of search treeEach node has pointers
n By following a pointer, we restrict our search to a
subtree and ignore all other nodes
n The number of pointers (fan-out) equals the index
blocking factor - 11Dynamic Multi-Level Index vs (B+ trees)Because of the insertion/deletion problem, most multilevel
indexes use B+-trees:
Leave space in each tree node
n Each node is kept between half-full and completely full - 12Internal vs. Leaf NodesInternal Nodes
n Guide the search to leaf nodes (see next 2 slides)
n Pointers are tree pointers
Leaf Nodes
n Have an entry for every value of the search field
n Pointers are data pointers
n Data pointers are stored only at leaf nodes - 13Pointers:Pointers are tree pointers to blocks that are tree nodes
n For a tree of Order q:
o Each internal node has at most:
n q tree pointers
o Each internal node has at least:
n q/2 tree pointers
except the root, which can have at least 2 tree pointers - 14Pointers priEach pri
is a data pointer to ki
’s record(s): - 15Pointer pnextpnext points to the next leaf node to provide ordered access
- 16Dynamic Multi-Level Index (B+ trees) insert/deleteInsertion:
n into a node that is not full is quite efficient
n if a node is full it is split into two nodes
n splitting may propagate to other tree levels
o Deletion:
n efficient if a node remains more than half full
n otherwise, it is merged with neighboring nodes - 17Inserting an new entry into a B+ treeo Find correct leaf L, put new entry onto L
n If L has enough space, done J
n Else, must split L (into L and a new node Lnew)
o redistribute entries evenly
n If L is of order p, then ⎡(p+1)/2⎤ entries stay in L and
the rest move to Lnew (or some other similar rule)
o copy up first key in Lnew into L’s parent
o Insert pointer to Lnew into L’s parent - 18Search in a B+ tree indexSearching for a record using B+ tree:
1) Read one block at each level in the index
n Number of accessed index blocks = tree height
2) Read the data block containing the searched record
o Total number of accessed blocks = tree height + 1 - 19conceptual evaluation strategy: (steps taken by the DBMS to evaluate that plan above)1. Compute the cross-product of from-list
2. Discard resulting tuples that fail qualifications
3. Delete attributes that are not in select-list
4. If DISTINCT is specified, eliminate duplicate
rows - 20Steps in Processing a QueryScan, Parse, Validate
Query Optimizer
Query Code Generator
Runtime DB Processor - 21o An SQL query is translated into equivalent: Represented as a:Relational Algebra Expression
Query Tree - 22Relational algebraBasic set of operations for the relational model
- 23Relational algebra expressioSequence of relational algebra operations
- 24SQL is based on concepts fromrelational algebra
- 25Optimization of Query TreesGet initial Query Tree :
using select,from,where
Transform it into an Equivalent Query Tree :
Represents a different relational expression
n Gives the same result
n More efficient to execute - 26Operations of Relational Algebraunion u
intersectionuce n
difference a-b (produces all tuples in a that arnt in b)
Cartesian product a*b(all possible comb or a*b tuples)
division a/b (all the a's that contain all the b's) - 27project πproduces a new relationship with only some of the attributes of r, removes all duplicates.
Deletes attributes that are not in - 28Projection has to eliminate duplicates: why?In the formal relational model: a relation is a set of records
n Elements cannot be repeated in a set
o SQL typically does not eliminate duplicates unless the user
explicitly asks for it (i.e., DISTINCT)! - 29Selection (σ)selects all tuples form R that satisify the selection condition
πname,rating(σ Rating > 8(S)) - 30SELECT Queries - Exampleso Point Query:
n σ SSN='123456789' (Employee)
o Range Query
n σ DNUMBER>5 (Department)
o Conjunction Query
n σ DNO=5 AND SALARY>30000 AND GENDER=F (Employee)
o Disjunction Query
o σ DNO=5 OR SALARY>30000 OR GENDER=F (Employee) - 31Several factors influence which algorithm performs best:o Size of the tables
o Existing index and sort orders
o Size of available memory - 32How to implement SelectionType of Query:
1. Point query,
2. Range query,
3. Conjunction, or
4. Disjunction
n Type of available Access Path:
1. Index,
2. Sorted File, or
3. None - 33selection putting it togetherFor a single condition: σ R.attr op value (R)
1. Use the index on the condition attribute if
available, else
2. Use Binary search if the files is sorted on the
condition attribute, else
3. Use the “brute force” linear search approach - 34SelectivityAge<25 AND Salary>60,000 (Employee)
o Which index to choose: Age or Salary?
o The optimizer should choose the access path
(i.e., index) that retrieves the fewest records:
1. Less blocks to read from disk
2. Less checks to do in memory - 35JoinsCondition Join Defined as: R condition S
Equijoin: a special case of condition join where the
condition contains only equalities
Natural Join: Equijoin on all common fields
n Common fields appear only once
o Join can be defined as cross-product followed by
selection:
o But a join result has fewer tuples than cross-product!
n might be able to compute more efficiently (next slides..)
R condition S = σcondition (R ×S) - 36Outer JoinLeft outer join (r s) keeps every tuple in the left
relation
n Right outer join (r s) keeps every tuple in the right
relation
n Full outer join (r s) keeps every tuple
o Attributes of tuples with no matching tuples are set to
NULL - 37General Transformation Rules σCascade of σ
n A conjunctive selection condition can be broken up
into a cascade of individual σ operations
σA.gender = ‘F’ AND A.age > 25 (A) = σA.gender = ‘F’ (σA.age > 25 (A))
Commutativity of σ
n The σ is commutative
σA.gender = ‘F’ (σA.age > 25 (A))
= σA.age > 25 (σA.gender = ‘F’ (A)) - 38General Transformation Rules ΠCascade of Π
n In a cascade of of π operations, all but the last one
can be ignored
ΠA.name (ΠA.name, A.age (A))
ΠA.name (Π A.age (A))
= ΠA.name (A) - 39Commuting σ with ΠIf c involves only attributes in projection list A1, A2, …, An, then
the two operations can be commuted - 40General Transformation Rules σ with JOINCommuting σ with
o If all the attributes in the selection condition “
c
” involve
only the attributes of one of the joined relations (e.g.,
R), the two operations can be commuted
σActors.age < 18 (Actors Actors.id=Oscars.id Oscars) =
= (σActors.age < 18 (Actors)) Actors.id=Oscars.id Oscars
“
c
” can be written as: c1 AND c2, where
o c1 involves only the attributes in R, and
o c2 involves only the attributes in S: - 41General Transformation Rules Π with JOIN“
c
” must only involve attributes in projection list.
swtich from projection-(rJoincS) to project joinc projection
and common joined attribute must always be in there respected bracket. - 42Associativity of , join, u, n, x(R * S) * T = R * (S * T)
o where * can be any of join, u, n, x
Converting a (σ, x) sequence into a join operation
n If c corresponds to a join condition, then
σc (R x S) = R join c S - 43Outline of algebraic optimization1. Break up selections (with conjunctive conditions) into
a cascade of selection operators
2. Push selection operators as far down in the tree as possible
3. Convert Cartesian products into joins
4. Rearrange leaf nodes so that to:
n Execute first the most restrictive select operators
o What is restrictive? (Fewest tuples or Smallest size)
5. Move projections as far down as possible - 44Heuristics for Algebraic Optimization:o The main idea is to apply first the operations that
reduce the size of intermediate results
1. Perform select operations as early as possible to
reduce the number of tuples, and
2. Perform project operations as early as possible to
reduce the number of attributes
3. The select and join operations that are most restrictive
should be executed before other similar operations - 45Query Execution Plans1. the relational algebra query tree, and
2. information about the access methods to be
used for each relation, and
n E.g., table scan, B+ tree index, Bitmap index, etc.
3. the algorithms to be used in computing the
relational operators stored in the tree
n E.g., Nested Loop Join, Single Loop Join, etc. - 46Cost-based Query Optimization (vs. heuristic)1. Estimate and compare the costs of executing a
query using different execution strategies, and
2. Choose the strategy with the lowest cost estimate
o (Compare to heuristic query optimization)
o Issues
n Cost function
n Number of execution strategies to be considered - 47Cost-based Query Optimization1. Access cost to secondary storage
2. Storage cost
3. Computation cost
4. Memory usage cost
5. Communication cost - 48loopsNL = B out + (N out * B in)
NL P = B out + (B out * B in)
BL = B out + (B out /(Nb-2))*B in
where
N = #records
Nb = # buffers
B = #blocks
small on outside - 49tuples after joinsjoining to PK means that tuples is determined by non PK value
once joined tuple size doubles thus only half the amount can now be stored.
if old was 10 new is 5 - 50join on FK to PKsimply just divide the inner value by 2
- 51query tree1.put from as nodes
2. where half way up
3.select at the top
then....
4. break where into slections (replace ands with ())
5. push these selection as far down as possible
6. switch Cartesian for joins
7. rearrange leaf node to execute most restictive selections first
8.move projections as far down as possible.
9. add MD.M_id on branches - 52bitmap index adv/limA bitmap index on an attribute is a bitmap for each distinct field value.
- Contains a “1” for each record in the relation where that attribute value is found.
- Contains a “0” for all other records.
Advantage:
1. Bitmap indexes facilitates querying on multiple keys.
2. Bitmap indexes are generally space efficient.
Limitations:
Not efficient for data that is modified regularly, as it would require modifying all the associated bitmap indexes.
Informationen
- Beschreibung
- Karteikarten am Ohne Titel, erstellt von 101ldaniels . am 12/10/2016.
- Erstellt von
- 101ldaniels .
- Aufrufe
- 1
- Bewertung