L11: Indexing (2019)

Question 1

Input/Output Operations:

Costs of Searching over Sorted Records:

• Simple Scan
• Binary Search

Answer 1

Simple Scan:

Cost = O(N)

Binary Search:

Cost = O(lgN)

Question 2

DBMS Buffer:

Basic Idea

Answer 2

Database has it’s own I/O Buffer.

Separate from OS Buffer.

The Buffer is handled by a Buffer Manager

Motivation:

• DB knows more about access patterns
• Recovery and Logging require the ability to flush to disk

Question 3

DBMS Buffer:

Buffer Manager

Answer 3

Buffer Manager

• Handles supporting operations for the DB’s I/O Buffer
• Primarily handles and executes the Replacement Policy
  
  • Finds which pages to flush/release when the buffer fails
• A DBMS typically implements its own buffer management routines, separate from the OS

Question 4

Simplified File System:

Basic Components

Answer 4

Files consist of pages, pages consist of blocks

Block

The basic “chunk” of memory on the disk

Page

• A fixed size array of memory
• One or more disk Blocks
• Interface:
  
  • Write to an entry( called a Slot), or set to “None”

File

• Variable Length list of Pages
• Interface:
  
  • create/open/close; next_page(); etc…

Question 5

Why are Sort Algorithms

important in a Database?

Answer 5

• Data requested in Sorted Order is very common in Databases
• Quick Sort is awful for large amounts of data
• Sorting is useful for eliminating duplicate copies in a collection of records
• Sorting is the first step in Bulk Loading, and B+ Tree Index
• Sort-Merge Join algorithm involves Sorting

Question 6

Sorting Big Files:

Basic Process

Answer 6

1. Split into chunks small enough to sort in memory
   
   • Chunks are called Runs
2. Merge pairs(or groups) of runs using the External Merge Algorithm
3. Keep merging the resulting runs until left with one sorted file
   
   • Each time merging is called a Pass

Question 7

External Merge Sort Algorithm:

Example:

3 Buffer Pages

6 Page File

Answer 7

Steps:

1. Split the file ( 2 sets of 3 pages)
2. Sort Externally
3. Load First page, f₁ , in buffer (Run # 1), and sort
4. Repeat for Second page, f₂ , in buffer (Run #2)
5. Run External Merge Sort Algorithm to put original file back together

Question 8

External Merge Sorting Algorithm:

Calculating I/O Cost

Answer 8

Two Main Cost Factors:

*assume 1 read(R), 1 Write(W) per page

Cost of Loading, C_loading

C_loading = (#runs)*(#pages)*(1R + 1W) = 2RP

Cost of Merging, C_merging

C_merging = (#runs)*(#pages)*(1R + 1W) = 2RP

Total I/O Cost = C_loading + C_Merging

Question 9

General I/O Cost of

Splitting N-page file

into N single page runs

and sorting

Answer 9

First Pass:

Merge N/2 pairs of runs, each with length of 1 page

Second Pass:

Merge N/4 Pairs of runs, each with length of 2 pages

Generalized:

• For N pages, we perform lgN passes.
• Also perform 1 pass for initial split and sort.
• Each pass involves reading/writing:
  
  • 2N I/O operations

Total I/O Cost = 2N*(lgN + 1)

Question 10

Benefits of

Using Indexes

Answer 10

• Much faster searching than simple scan or binary search
• Faster insertions by avoiding shifting operations
• Search quickly among multiple attributes
• Indexes are critical across all DBMS types

Question 11

Index:

Overview

Answer 11

Index:

A data structure mapping search keys to sets of rows in a database table.

• An index on a file speeds up selections on Search Key fields
  
  • A Search Key can be any subset of fields
  • Completely separate from Keys of a relation
• Provides efficient lookup and retrieval by search key values
• An index can store either the full rows it points to
  
  • Called a Primary Index
• Or pointers to those rows
  
  • Called a Secondary Index

Question 12

Major Operations

on an Index

Answer 12

• Search
  
  • Quickly find all records which meet some conditions on the Search Key attribute
• Insert/Remove entries
  
  • Including Bulk Load and Bulk Delete

Question 13

What does the term

“Covering” mean

wrt an Index?

Answer 13

If an Index contains all the needed attributes for a specific query,

the Index is said to Cover, or be Covering, for that query.

Basically, the query can be answered by using the Index alone.

Question 14

High Level Categories

of

Index Types

(Data Structures)

Answer 14

• B-Trees (B+ Trees)
  
  • Very good for range queries, sorted data
  • Old databases used B-trees
  • Modern databases use B+ trees
• Hash Tables
  
  • Variants of this basic structure to deal with I/O
  • Called Linear or Extensible Hashing

*Both these data structures are “IO aware”

Question 15

Buffer Operations

Answer 15

• Read( Page )
  
  • Read a page from disk
  • Place in buffer if not already in buffer
• Flush( Page )
  
  • Evict page from the buffer
  • write to disk
• Release( Page )
  
  • Evict page from the buffer without writing to disk

Question 16

Disk vs Main Memory(RAM)

Answer 16

• Speed
  
  • Disk is slow:
    
    • Sequential block access
      
      • Blocks read one at a time
    • Reads/Writes are expensive
  • Main Memory is fast
    
    • Random Access, byte addressable
    • 10x faster for sequential access
    • 100,000x faster for Random Access
• Data Safety
  
  • Disk storage is durable
    
    • Once on disk, data is safe
  • Storage in RAM is Volatile
    
    • Data is lost if a crash or power loss occurs
• Cost
  
  • Large capacity Disks are cheap
  • RAM is expensive

Question 17

Buffer:

Overview

Answer 17

Buffer:

A region of physical memory used to store Temporary Data

More specifically,

Region in Main Memory used to store Intermediate Data between the disk and processes

Key Idea:

Reading/Writing to the disk is slow, so data is cached for reading/writing in the Buffer