COSC2406/2407 Database Systems File Organisations and Indexing
Xiangmin (Emily) Zhou
RMIT University Room : 14.11.04
Online Consultation via Collaborate Ultra(no appointment required): 10:20-11.20am Thursdays
Email : xiangmin.zhou@rmit.edu.au
Lecture 4
References: Ramakrishnan & Gehrke Chapter 8 Garcia-Molina et al. Chapter 13
Elmasri & Navathe Chapters 5 & 6
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 1 / 34
Slot Offset Table in Apache Derby [from last lecture]
Slot Offset Table contains of 6 bytes (12 bytes when pagesize > 64KiB) per record:
• 2 bytes page offset for record
• 2 bytes length of record on this page
• 2 bytes length of the reserved number of bytes for this record on
this page
Note: 1 KiB (kibibyte) = 1024 bytes
similarly 1MiB (mibibyte) = 10242 bytes
to avoid confusion with 1MB (megabyte) = 10002 bytes etc
http://db.apache.org/derby/papers/pageformats.html
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 2 / 34
Overview: Week 4
In the first part of this lecture, we will:
• Introduce the cost model
• Analyse three common file organisations:
• heap files
• files sorted on some fields
(see Section 8.4.3 of Ramakrishnan & Gehrke)
• files hashed on some fields
In the second part of this lecture, we will continue with a discussion of
indexes.
• Discuss properties of an index
• Discuss alternatives for data entries in an index
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 3 / 34
Cost Model for Our Analysis
In our discussion we will use a simple cost model.
The cost metric is the number of disk-block I/Os.
Usually the number of I/Os is the dominant cost in database applications. We ignore CPU costs and the use of pre-fetching of blocks (blocked access).
We express the costs of basic operations in terms of:
• B: the number of data blocks (or pages) • D: (average) time to transfer a disk block
(The average-case analyses here are based on several simplistic assumptions.)
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 4 / 34
Simplifying Assumptions
Aside from CPU costs and blocked access, in our cost model we will ignore:
• time to do an equality comparison • time to apply a hash function
In 2003 these were in the order of 100 nanoseconds, while I/O is in the order of 15 milliseconds. Therefore, I/O is the dominant cost.
These trends will continue to diverge: CPU speeds are rising much more quickly than disk access speeds — both have increased by a factor of over 100 since 2003.
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 5 / 34
Example
We will consider a file that stores data from the following Character relation:
NAME
LEVEL
CLASS
Frost Moon Lysa Varra Meerkat Shaka Cass Otho
38
20
13
19
18
2
15
24
Mage Warrior Druid Warrior Rogue Shaman Mage Hunter
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 6 / 34
Basic Operations for File Organisations
The operations we analyse are those identified last lecture: • Scan:
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 7 / 34
Basic Operations for File Organisations
The operations we analyse are those identified last lecture: • Scan: Fetch all records in the file
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 7 / 34
Basic Operations for File Organisations
The operations we analyse are those identified last lecture:
• Scan: Fetch all records in the file • Search with equality selection:
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 7 / 34
Basic Operations for File Organisations
The operations we analyse are those identified last lecture:
• Scan: Fetch all records in the file
• Search with equality selection: Fetch all records that satisfy an
equality selection
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 7 / 34
Basic Operations for File Organisations
The operations we analyse are those identified last lecture:
• Scan: Fetch all records in the file
• Search with equality selection: Fetch all records that satisfy an
equality selection
“Find the record for a character with name ’Lysa’.”
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 7 / 34
Basic Operations for File Organisations
The operations we analyse are those identified last lecture:
• Scan: Fetch all records in the file
• Search with equality selection: Fetch all records that satisfy an
equality selection
“Find the record for a character with name ’Lysa’.”
• Search with range selection:
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 7 / 34
Basic Operations for File Organisations
The operations we analyse are those identified last lecture:
• Scan: Fetch all records in the file
• Search with equality selection: Fetch all records that satisfy an
equality selection
“Find the record for a character with name ’Lysa’.”
• Search with range selection: Fetch all records that satisfy a range
selection
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 7 / 34
Basic Operations for File Organisations
The operations we analyse are those identified last lecture:
• Scan: Fetch all records in the file
• Search with equality selection: Fetch all records that satisfy an
equality selection
“Find the record for a character with name ’Lysa’.”
• Search with range selection: Fetch all records that satisfy a range
selection
“Find all records of characters with level greater than 22.”
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 7 / 34
Basic Operations for File Organisations
The operations we analyse are those identified last lecture:
• Scan: Fetch all records in the file
• Search with equality selection: Fetch all records that satisfy an
equality selection
“Find the record for a character with name ’Lysa’.”
• Search with range selection: Fetch all records that satisfy a range
selection
“Find all records of characters with level greater than 22.”
• Insert:
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 7 / 34
Basic Operations for File Organisations
The operations we analyse are those identified last lecture:
• Scan: Fetch all records in the file
• Search with equality selection: Fetch all records that satisfy an
equality selection
“Find the record for a character with name ’Lysa’.”
• Search with range selection: Fetch all records that satisfy a range
selection
“Find all records of characters with level greater than 22.”
• Insert: Insert a single, new record into the file
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 7 / 34
Basic Operations for File Organisations
The operations we analyse are those identified last lecture:
• Scan: Fetch all records in the file
• Search with equality selection: Fetch all records that satisfy an
equality selection
“Find the record for a character with name ’Lysa’.”
• Search with range selection: Fetch all records that satisfy a range
selection
“Find all records of characters with level greater than 22.”
• Insert: Insert a single, new record into the file
• Delete:
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 7 / 34
Basic Operations for File Organisations
The operations we analyse are those identified last lecture:
• Scan: Fetch all records in the file
• Search with equality selection: Fetch all records that satisfy an
equality selection
“Find the record for a character with name ’Lysa’.”
• Search with range selection: Fetch all records that satisfy a range
selection
“Find all records of characters with level greater than 22.”
• Insert: Insert a single, new record into the file
• Delete: Delete a single record specified by its record-id rid
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 7 / 34
Example (again)
We will consider a file that stores data from the following Character relation:
NAME
LEVEL
CLASS
Frost Moon Lysa Varra Meerkat Shaka Cass Otho
38
20
13
19
18
2
15
24
Mage Warrior Druid Warrior Rogue Shaman Mage Hunter
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 8 / 34
Heap File
Records are unordered:
Frost Moon Lysa
38 20 13
Mage Warrior Druid
Varra Meerkat Shaka
19 18 2
Warrior Rogue Shaman
Cass Otho
15 24
Mage Hunter
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 9 / 34
Heap Files
Remember that in a heap file, records in the file are unorganised. Here, for simplicity, we assume insertions are always at the end of file. Equality selections are on a unique key, that is, we have exactly one match.
Access costs on average:
• Scan: BD
• Equality Search: 0.5BD • Range Search: BD
• Insert: 2D
• Delete: Search + D
To ensure a compact heap file, we need to keep and update a free space list for deletions and insertions (using the structures we discussed last week).
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 10 / 34
Linear Search
We wish to search for a data entry with key value 73 in the following array of 16 items:
Slot 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Key 7 12 21 22 26 34 56 61 68 69 71 73 89 91 92 94
For a linear search, the average cost is:
N = 16 = 8 22
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 11 / 34
Binary Search
Suppose that we again wish to search for a data entry with key value 73 in the following array of 16 items, this time using binary search:
Slot 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Key 7 12 21 22 26 34 56 61 68 69 71 73 89 91 92 94
For a binary search, the average cost is: log2N =log216=4
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 12 / 34
Sorted File
Records are sorted on name:
Cass Frost Lysa
15 38 13
Mage Mage Druid
Meerkat Moon Otho
18 20 24
Rogue Warrior Hunter
Shaka Varra
2 19
Shaman Warrior
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 13 / 34
Sorted Files
A sorted file is like a heap file, but the file is sorted on a sequence of fields, which we call the search key.
A search key need not uniquely identify records. We can locate a record using a binary search on the search key.
I/O cost on average:
• Scan: BD
• Equality Search: D log2 B
• Range Search: D(log2 B + number of pages with matches) • Insert: Search +BD
• Delete: Search +BD
Inserting and expanding records can be problematic.
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 14 / 34
Hashed File
Hash function: level mod 3
0
1
2
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 15 / 34
Hashed File
Hash function: level mod 3
0
Cass Meerkat Otho
15 18 24
Mage Rogue Hunter
1
Lysa Varra
13 19
Druid Warrior
2
Frost Moon Shaka
38 20 2
Mage Warrior Shaman
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 16 / 34
Page Occupancy
Suppose that 100 records are to be stored in a file, and that 10 records can fit on one page.
• How many pages are needed?
Now suppose that an (initial) maximum occupancy of 80% is imposed. • How many records fit on one page?
• How many pages are needed in total?
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 17 / 34
Static Hashed Files
The pages in a hashed file are grouped into buckets. We can apply a hash function to the search key to find out the bucket number to which a record belongs. We assume that we do not have overflow buckets. The page occupancy is assumed to be 80%. I/O cost on average:
• Scan: 1.25BD (1.25 = 1 ; you need 1.25B blocks to store the records) 0.8
• Equality Search: D
• Range Search: 1.25BD • Insert: 2D
• Delete: 2D
Overflowing buckets decrease the performance of a static hashed file. Dynamic hash structures such as Linear Hashing, and Extendible Hashing address this problem.
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 18 / 34
Cost of Operation : Summary
Access Method
Scan
Equality Range Search
Insert
Heap File
BD 0.5BD BD
Sorted File
BD
D log2 B D(log2 B+
# of match pages) Search +BD Search +BD
Hashed File 1.25BD
D 1.25BD
2D
2D Search +D
2D
Delete
No file organisation is uniformly superior in all situations. Indexes are used to speed up operations that are not efficiently supported by the basic organisation.
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 19 / 34
Review: Alternative File Organisations
• Heap files: suitable when the typical access is a file scan to retrieve all records
• Sorted or sequential files: best if records must be retrieved in some order, or only a “range” of records are needed
• Hashed files: good for selecting records that match equality conditions
• File is a collection of buckets;
Bucket = primary page plus zero or more overflow pages
• Hashing function h maps a record r into a bucket. h looks only at some of the fields of r, called the search key
Each file organisation works well for some situations but not for all.
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 20 / 34
Indexes
An Index on a file speeds up selections on the search key.
• Any subset of the fields of a relation can be the search key of an
index.
• A search key is not the same as a unique key of a relation that uniquely identifies a record in a relation.
An index contains a collection of data entries, and supports efficient retrieval of all data entries k∗ with a given search key value k. There are three alternatives for a data entry k∗ in an index.
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 21 / 34
Alternatives for the Data Entry k∗ in an Index
Three alternatives:
1 Data record with search key value k
2 (k, rid of data record with search key value k)
3 (k, list of rids of data records with search key k)
The choice of an alternative for data entries is independent of the index technique used to locate data entries with a given value k. Any indexing technique can use one of the three alternatives above. Examples of indexing techniques include B+-trees and hash-based structures.
Typically, an index contains auxiliary information that directs searches to the desired data entries (for example, index entries in index pages in a B+-tree).
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 22 / 34
Alternatives for Data Entries …
• Alternative 1:
• If this is used, the index structure is in fact a file organisation for
data records (e.g. like sorted file).
• At most, one index on a given collection of data records can use
Alternative 1. (Otherwise, data records are duplicated, leading to
redundant storage and potential inconsistency.)
• If data records are very large, the number of pages containing data
entries is high. This typically implies that the size of auxiliary information in the index is also large.
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 23 / 34
An Alternative 1 Index
An Alternative 1 index on level:
Shaka Lysa Cass
2 13 15
Shaman Druid Mage
Meerkat Varra Moon
18 19 20
Rogue Warrior Warrior
Otho Frost
24 38
Hunter Mage
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 24 / 34
Alternatives for Data Entries …
• Alternatives 2 and 3:
• Index data entries are typically much smaller than data records.
• Therefore, more storage efficient than Alternative 1.
• If more than one index is required on a file, only one can use
Alternative 1, and remainder must use Alternatives 2 or 3.
• Alternative 3 is most compact, but the variable size of the index
entries is harder to handle (lists can grow and shrink in size).
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 25 / 34
Alternative 2 Index
An Alternative 2 index on name:
Cass
Shaka, 2, Shaman
Lysa, 13, Druid
Frost
Cass, 15, Mage
Lysa
Meercat
Moon Otho
Meercat, 18, Rogue
Varra, 19, Warrior Moon, 20, Warrior
Shaka
Otho, 24, Hunter
Varra
Index on Name
Data File
Frost, 38, Mage
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 26 / 34
Index Classification
• Primary vs. secondary: If the search key contains the primary key, then the index is the primary index.
• Unique index: Search key contains a candidate key.
• Clustered vs. unclustered: If order of data records is the same as, or “close to” the order of the data entries, then the index is a clustered index.
• Using alternative 1 implies a clustered index, but not vice-versa • A file can be clustered at most on one search key
• The cost of retrieving data records greatly depends on whether
index is clustered or not
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 27 / 34
Clustered vs. Unclustered Indexes
Consider using alternative 2 used for the data entries and storing the data records in a heap file.
• To build clustered index, first sort the heap file (leaving free space on each page for future inserts).
• Overflow pages are used later for inserts. Thus, order of data records is ’close to’ (but not identical) the sort order.
Clustered
Index entries
(Direct search for
Unclustered
Index entries
(Direct search for
data entries)
Data entries
Index File
Data file
data entries)
ta entries
Data Records
Data Records
Da
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 28 / 34
Dense vs. Sparse Indexes
• Dense vs sparse: If there is (at least) one data entry in the index per search key value then the index is dense. In a sparse index, we may have one data entry in the index for a page or set of records.
• Implications:
• Alternative 1 always leads to a dense index
• Every sparse index is clustered (otherwise we would ignore the
order)
• There is only one sparse index (since we can have only one
clustered index)
• Sparse indexes are smaller; however, some useful optimisations
are based on dense indexes (refer to Section 12.5.2 of Ramakrishnan & Gehrke)
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 29 / 34
Dense vs. Sparse Indexes …
The first index shown below is a sparse, clustered index on name. The order of data entries in the index corresponds to the order of records in the data file. There is one data entry per page of records.
The second index is dense, unclustered index on level. The order of data entries in the index differs from the order of data records. (There is one data entry in the index per record in the data field [Alternative 2].)
Cass Meercat
Meercat, 18, Rogue Moon, 20, Warrior
Shaka
Otho, 24, Hunter
Sparse Index on Name
Data File
Dense Index on Level
Cass, 15, Mage
Frost, 38, Mage Lysa, 13, Druid
Shaka, 2, Shaman
Varra, 19, Warrior
2 13
15
18
19
20
24
38
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 30 / 34
Advantages and Disadvantages
• Clustered index: good for range queries. Rids of qualifying index entries point to a contiguous collection of records, hence few page I/Os
• Unclustered index: could lead to as many page I/Os as there are matching index entries. However, if we need more than one index, additional indexes must be unclustered
• Dense index: especially advantageous when index can fit into memory; can find a record with one I/O. Can determine from index alone whether a record exists
• Sparse index: smaller than a dense index, so can fit more into memory and can be searched quickly. However, may need to to an I/O just to check whether a record exists
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 31 / 34
Review
• Many alternative file organisations exist, each is appropriate for particular situations
• If selection queries are frequent, sorting the file (or building an index) is important
• Hash-based files (or indexes) are only good for equality search
• Sorted files (and tree-based indexes) are best for range searches,
and also good for equality searches
• An index is a collection of data entries, plus a way to quickly find entries with given key values
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 32 / 34
Review …
• Index data entries can be actual data records, (key, rid) pairs, or (key, rid-list) pairs.
• The choice is independent of the indexing techniques used to locate data entries with a given key value
• There can be several indexes on a given file of data records, each with different search key
• Indexes can be classified as clustered or unclustered, primary or secondary, and dense or sparse. Differences have important consequences for utility and performance
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 33 / 34
Summary: File Organisations and Properties of Indexes
We have discussed:
• A file-access cost model based on the number of disk page I/Os as the cost metric.
• Three basic file organisations and their costs for common operations
• the properties of indexes:
• clustered vs. unclustered; • dense vs. sparse;
• primary vs. secondary.
• Alternatives for the index data entries k* in an index.
In the next few lectures, we will cover hash-based indexing and tree-based indexing techniques like the B+ tree. We will also discuss a related topic, the external merge sort.
Xiangmin (Emily) Zhou (RMIT University)
COSC2406/2407 Database Systems
Lecture 4 34 / 34