Efficiency, Indexing, Physical Design

Question 1

Why should we study efficiency

Answer 1

If databases and DBMS don’t run fast enough to be useful, then the point is missed entirely.

Question 2

Main Memory (RAM)

Answer 2

Volatile, fast, small, and expensive

Question 3

Secondary Memory (DISK)

Answer 3

Permanent, slow, big, and cheap

Question 4

Main Memory Access Time

Answer 4

30ns (.3 x 10^-7 sec)

Question 5

Disk Access Time

Answer 5

10ms (1 x 10^-2)

Only this cost (I/O) is calculated

Question 6

Parts of the Disk

Answer 6

Read/Write Head
Actuator
Arm
Spindle
Track/Cylinder
Sector
Block
Platters

Question 7

Spanned Representation

Answer 7

Where a record is split up between two blocks of disk memory

Question 8

Unspanned Representation

Answer 8

Where a record exists on a single block on disk memory

Question 9

Why not fill up a block with data?

Answer 9

We may want to leave space at the end of a block in case we need to insert new records.
Target is 80% filled.

Question 10

File

Answer 10

A series of blocks linked by address pointers.

Question 11

Seek Time

Answer 11

Time it takes to find a block on disk. Costs 3-8ms

Question 12

Rotation Delay

Answer 12

Time it takes for the disk to rotate to a block. Costs 2-3ms

Question 13

Transfer Time

Answer 13

Time it takes for I/O to deliver the data via data bus to Main Memory. Costs .5-1ms

Question 14

LRU buffer management strategy

Answer 14

When we run out of buffer space and need to free some, the least recently used space will be overwritten.

Excellent for Merge Joins
Kills Nested loop joins

Question 15

Heap

Answer 15

Unsorted file of data.

Question 16

Heap Lookup Time

Answer 16

N/2 | N = # data blocks
(ex. 200000 / 2 * .01s = 16.6 min)

Sometimes we’re lucky and the target is in the first location.
Sometimes we’re unlucky and its in the last location.

Question 17

Sorted Binary Search

Answer 17

Inspect records halfway through file and determine if we should search before or after this record. Repeat until record is found.

Question 18

Sorted Linear Search Time

Answer 18

N/2 | N = # data blocks

ex 200000 / 2 * .01s = 16.6 min

Question 19

Sorted Binary Search Time

Answer 19

log2(N) | N = # data blocks

ex log2(200000) * .01s = 18 * .01s = .18s

Question 20

Primary Index

Answer 20

Create a copy of the key of a record into a new block, and create a pointer to the address of the block of data the key belongs to.

Block design:
K = Key
P = Pointer
+—–+——+——+——+——+——+
| K1 | P1 | K2 | P2 | K3 | P3 |
+—–+——+——+——+——+——+

Question 21

Primary Index Lookup Time

Answer 21

log2(n) + 1 | n = # index blocks

ex: log2(n / fanout) + 1 | fanout = 60

Sparse (200,000 records):
(log2(200/000 / 60) + 1) * 0.01s = (12+1)*0.01s = 0.13s

Dense (4M):
(log2(4,000,000 / 60) + 1) * 0.01s = (16+1)*0.01s = 0.17s

Question 22

Index Block Calculation

Answer 22

data blocks / fanout

Question 23

Fanout

Answer 23

The number of overall blocks the total records fall into.

Question 24

Sparse (Single Level) Index

Answer 24

index records are not created for every search key value.

Question 25

Dense Index

Answer 25

an index record is created for every search key value in the database. Requires more space.

Question 26

Multi Level Index

Answer 26

Where we have an index for the indices of our blocks of data.

Question 27

Multi Level Lookup Time

Answer 27

log(fanout)(n) + 1 | n = # index blocks

Question 28

Multi Level Index B-Tree

Answer 28

All data is at the bottom, and all nodes above that are index node.

If the tree deteriorates over time, so does the search time.
It’s very important that the distance from the root to the base level never change over time.

Question 29

Static Hashing

Answer 29

Hashing function hashes keys from a keyspace which resolves an address in a designated address space. This address holds a pointer for a linked data block.

Question 30

Properties of a Good Hash Function

Answer 30

1) Distribute values uniformly over the address space
2) Fill buckets as much as possible
3) Avoid collisions

Question 31

Properties of Good Static Hashing

Answer 31

Linked data blocks are uniform, address space is appropriate size so linked lists don’t get too deep.

Question 32

Blocking Factor

Answer 32

Number of blocks in a file