Transcript DBMS Architecture and Performance

Database System
Architecture and
Performance
CSCI 6442
©Copyright 2016, David C. Roberts, all rights reserved
Components of a DBMS
2
Agenda
Database performance goals
 DBMS use of disk
 Searching
 B-trees
 DBMS Architecture

3
DBMS Architecture
Data is stored on disk
 Disk is necessary for database to be
reliably available
 Disk is millions of times slower than
anything that happens in RAM
 Number of disk accesses is a good
measure of DBMS cost for an
operation

4
Disk
o Disk
is composed of fixedlength records, rotating
around
o To access information, we
need to move the head and
wait for the disk to rotate
o We wait the same time
whether we use one byte or
all the record
o We call this fixed length
record a page
5
Efficient Use of Disk
For efficient use of disk, we want to
use all the information contained in a
single page
 We will look at how we organize disk
in order to reduce the number of disk
accesses for a search

6
Disk vs. RAM
RAM is accessible in any order
 Any sort of structures can be used
 Data structure courses usually cover
data structures for RAM
 We’ll talk about how to make efficient
use of disk

7
Disk as Pages
Disk is composed of fixed-length
records, rotating around
 To access information, we need to
move the head and wait for the disk to
rotate
 We wait the same time whether we
use one byte or all the record
 We call this fixed length record a page

8
Search Methods
Linear search
 Binary search
 Binary tree-structured search
 N-ary trees
 B-trees
 Hashing

9
Linear Search
Elements are stored in arrival order
 Search starts at the beginning,
continues until desired value is found
 Average number of accesses for n
elements is approximately n/2

10
Binary Search
Elements are stored in order by value
to be searched
 Search starts at midpoint
 With each probe, half of candidates
are removed
 Average number of probes is log2n

11
Disadvantages of Binary
Search
Elements must be kept in order
 Inserting one element may require
reorganization of entire list
 If stored, search jumps from bucket to
bucket

12
Using Linked Structure for
Binary Search
Using links we can separate physical
organization from search sequence
 Avoids possible need to reorganize
the entire store because of a single
update
 Accelerates update, still allows fast
search

13
Example Binary Search Tree
14
Problems with Binary
Search Tree
Each node is likely to be on a different
page, making inefficient use of disk
accesses
 What if, instead of just one key at
each node, we could store a whole
page full of keys?
 Then we would use disk efficiently
and have a very shallow tree

15
Balance
16
Balance
A tree is said to be balanced if the length of all the paths from the root
to the leaves differ by no more than one.
17
B-tree
We allow nodes to be incompletely
filled in order to maintain perfect
balance
 We grow the tree from the bottom;
when a node is over-full we split it and
put an added node one level up
 Deletions are the reverse of additions

18
B-tree
19
B-tree
We understand that with each entry
there is an address in storage.
Having understood that, we omit
them from the rest of the diagrams
Data Store
20
B-tree
21
B-tree
1
22
B-tree
1
23
4
B-tree
1
24
4
6
B-tree
1
25
4
6
8
B-tree
5
1
26
4
6
8
When a node is full, to add a
value we split the node and
put the middle value in the
level above.
B-tree
5
1
27
4
6
8
How It Really Looks
28
B-tree questions
How large should node size be? How
many values should it contain?
 Are the values indexed by a b-tree
properly called keys?
 How full are b-tree nodes, on the
average, after the system has been
operating for a while?

29
B-plus tree
B+ trees have all indexed values
represented in the leaves
 Other nodes do not have pointers to
rows, only pointers to other nodes
 B+ trees provide very high density of
indexes

30
B+ tree
Index Set
Sequence Set
31
B+ Tree Add Algorithm
The insert algorithm for B+ Trees
Leaf Page
Full
NO
YES
YES
Index Page
FULL
Action
NO
Place the record in sorted position in the appropriate leaf page
NO
1.
2.
3.
4.
Split the leaf page
Place Middle Key in the index page in sorted order.
Left leaf page contains records with keys below the middle key.
Right leaf page contains records with keys equal to or greater than
the middle key.
1.
2.
3.
4.
5.
6.
7.
Split the leaf page.
Records with keys < middle key go to the left leaf page.
Records with keys >= middle key go to the right leaf page.
Split the index page.
Keys < middle key go to the left index page.
Keys > middle key go to the right index page.
The middle key goes to the next (higher level) index.
YES
IF the next level index page is full, continue splitting the index
pages.
32
B+ Tree Delete Algorithm
The delete algorithm for B+ Trees
Leaf Page
Below
Fill
Factor
Index Page
Below
Fill
Factor
Action
NO
NO
Delete the record from the leaf page. Arrange keys in ascending order to fill
void. If the key of the deleted record appears in the index page, use
the next key to replace it.
YES
NO
Combine the leaf page and its sibling. Change the index page to reflect the
change.
YES
YES
1.
2.
3.
Combine the leaf page and its sibling.
Adjust the index page to reflect the change.
Combine the index page with its sibling.
Continue combining index pages until you reach a page with the
correct fill factor or you reach the root page.
33
Hashing
Develop a function that maps data
values into a range of storage
addresses
 For each search value, use a function
to compute a hash value and store the
associated data at that address
 To search, just compute the hash
value and look at that address

34
Hashing
Instead of storing the data at the hash
address, store a pointer to the data
 The table of pointers is called a hash
table
 Using hashing for a search locates a
stored value in just one access
 Number of accesses to locate a value
is independent of n

35
Hashing Question
Why are b-trees the most used index
method for database systems and not
hashing, given that hashing is faster?
Hint—think about the disadvantages of
hashing

36
Database System
Architecture
DBMS and Applications
Application Buffer
Program
Application Buffer
Program
Application Buffer
Program
Application Buffer
Program
38
Database
Management
System
DBMS Software Architecture
Application Buffer
Program
Application Buffer
Program
Application Buffer
Program
Application Buffer
Program
39
System
Global
Area
Database
System
Database System
Architecture
SQL
Tokens
Lexical
Analyzer
Quads
Syntax
Analyzer
Executor
Results
40
Executor Software
Architecture
SQL Executor
Table Management
Index Management
Row Management
Node Management
Page Management
Data Store
41
DBMS and Applications
Application Buffer
Program
Application Buffer
Program
Application Buffer
Program
Application Buffer
Program
42
Database
Management
System
DBMS Software Architecture
Application Buffer
Program
Application Buffer
Program
Application Buffer
Program
Application Buffer
Program
43
System
Global
Area
Database
System
Code
Inside the Database System
SQL
Tokens
Lexical
Analyzer
Syntax
Analyzer,
Code
Generator
Quads
Executor
Results
44
Executor Software
Architecture
SQL Executor
Table Management
Index Management
Row Management
Node Management
Page Management
Data Store
45
Pages
Disk is divided into physical records
called “pages”
 A page can be an index page (ie btree) or a data page
 Index page contains one node of a btree
 Data page contains rows of tables

46
Page Allocation
Pages are initially considered all
unallocated
 In response to requests, they are
allocated and marked allocated
 When freed, they are chained onto a
list of free pages

47
Database Extents

Database needs to be able to extend
over disk boundaries




48
Size may require it
Growth may require it
Typically it’s managed as “extents”, each
of which is a file to the OS file system
Multiple files are mapped into a single
sequence of page IDs
Extents
SQL Executor
Table Management
Index Management
Row Management
Node Management
Page Management
Extent Management
Data Store
49
The Database
Extent 1
Extent 2
Row
50
Extent 3
<<tid>,<rid>,<cid><cli><cv>, … ,
<cid>,<cli>,<cv>, … >>
Startup
At startup, DBMS creates an empty
system catalog
 Catalog has images of some tables;
once images are established, then
SQL can be used to create other
tables

51
System Catalog
System Catalog tells you how the
database system works
 When the system starts with a new
database, it lays down part of the
system catalog from an image
 The rest of the system catalog is
created by SQL statements
 Many SQL statements reference or
change the system catalog

52
System Catalog
You will have the opportunity to learn
more about the system catalog in your
assignment.
53
Database
Performance
54
Join Processing
For a non-join query be sure there are
indexes on columns used in
predicates
 Joins are the issue in database
performance
 We need to understand how they are
performed so that we can make them
efficient

55
“Optimization”




56
More properly called access path selection
“Optimizer” selects a strategy for processing
Approaches:

Cost-based: estimate total cost to process by
different approaches, choose lowest estimate

Heuristic: use rules to decide how to process
Cost-based is typically used by all database
systems today
The Optimizer
Selects indexes to use
 Chooses the order of using indexes
 Chooses algorithms to use
 Decides when to apply predicates

57
Classes of Predicates



Predicate: condition in the WHERE
clause
Predicates are combined using AND, OR
to make WHERE clauses
Classes of predicates:


58
Sargable: search arguments that can be
processed close to the data
Residual: not sargable, such as complex
use of nesting
Access Paths

Five possible access paths:
Table scan
 Non-selective index scan
 Selective index scan
 Index only access
 Fully qualified unique index


59
Each of these types of scans has
different cost estimates for its use
Predicate Selectivity



Selectivity function f(p): % of rows retrieved on average
by predicate p
Number of rows retrieved is strongly related to cost
n = number of rows in table
Form of P
f
column = value
1/n
column != value
1-1/n (nearly 1)
column > value
(high value - search
value)/high value - low
value)
p1 or p2
f(p1) + f(p2)
p1 and p2
f(p1) * f(p2)
60
Join Processing



61
Cartesian Product: for each row of inner
table, inspect join value for every row of
outer table. n2 operations
Nested loop: for each row of inner table,
use index to retrieve matching rows of
outer table. > 2n operations
Merge join: single pass through indexes
on join columns for both tables. 2n
operations
Join Order
For JOIN queries, the “outer” table is
access first, “inner” second
 Order for joining tables must be
selected
 Most selective first
 Least costly joins first

62
Query Transformations
Queries and subqueries may be
transformed
 We’ll ignore this for now, look at the
bigger picture

63
Database Statistics

System catalog includes various
database statistics
Max, min values
 Cardinality of each table
 Data distribution


64
Statistics must be updated