DBMS - External Hashing

Question 1

Basic/Old Idea of Hashing

Answer 1

Decide on hash key, size of hash file, hash function. Hash the source data and place it in the file of RRN location indexed by the hash function.

To search for a record, hash its key and directly access record in hash file.

Question 2

Hash address collision

Answer 2

hash addresses can collide

Question 3

Hash key space

Answer 3

shouldnt be much larger than hash file address space

Question 4

Hashing allows us to retrieve

Answer 4

a record on the basis of key value throughout use of a hashing function.

Question 5

Hashing Uses and Issues

Answer 5

• Routine converts key value to int that corresponds to an address location in a hash file where record’s key values and pointers are kept

-Locations generated appear to be random

• With hashing, no of keys could be mapped into same address/location (collision)
• Another issue is exhaustion of pre-booked space

Question 6

External hashing

Answer 6

Deals with hashing as a file indexing structure

Question 7

Internal Hashing

Answer 7

Deals with main memory structures

Question 8

If keyi > keyj

Answer 8

It is not necessary that h(keyi)>(keyj) unless h() is monotonic

Question 9

Perfect hash function

Answer 9

Has no duplicate hashes

Question 10

Minimal perfect hash function

Answer 10

has as many keys as hashes

Question 11

Hash Function Examples

Answer 11

• Represent key in numerical form
• Prime Division
• Truncation
• Folding

Question 12

Truncation

Answer 12

If key is 123456789 then truncation (of last 3 digits) will return an address of 789

Question 13

Folding

Answer 13

Works by splitting the key into two and operating on these, so 1234 and 456 will add to an address of 1690

Question 14

Prime Division

Answer 14

Say n is our file address size, divide key by a prime just greater than n (skewed dist)

Question 15

Represent Key in numerical form

Answer 15

convert alphanumerics to numbers and apply function to a key to produce address

Question 16

Hashing Collision Management

Answer 16

Caused because actual hash key distribution is not uniform. Size of hash index address space range i.e size of file.

Question 17

Conflict Resolution

Answer 17

Overflow Area and Placement Management. If cells in a home address are taken then remaining synonyms are spanned over overflow area.

We can also use double hashing or a linked list to use multiple keys in a hash.

Question 18

Home address

Answer 18

Has fixed size. Promising solution is to address extendable address space and hashing function

Question 19

Operations over an external hashed file structure

Answer 19

• Create hash file (incl. overflow area) with initial no. of buckets, loading ratios etc,
• Insert records in bucket
• Compute address (key value) in memory
• Get from address into bucket
• Put an address into bucket

All these ops are very fast, unless overflow occurs, they are direct. 70-90% of loading can still operate with low level of collisions.

Question 20

Hash structure characteristics

Answer 20

• Space: Pre-booking of space seems counter productive. Optimal system performance at 66% capacity.
• Operation’s Time: Searching, inserts. Sequential traversal not implicitly supported.
• Parameters: Bucket space, hash function distribution, hash key dist. in indexed dataset.

Question 21

Advantages of Hashing

Answer 21

Very Fast

Question 22

Disadvantages of Hashing

Answer 22

Hash files cannot be read out in record-sequence since they are stored in address-sequence.
Hash files grow substantially in size without redesign of hashing routine or address size sequence increase

Question 23

Improvements

Answer 23

• Extensible hashing with better overflow management
• Multidimensional hashing

Question 24

Making Hashing Disk Friendly

Answer 24

• Address space is to represent disk addressing, use RRN
• Space at address is called the bucket, can be a single disk block or a bunch of blocks
• Hash address collisions possible even with large buckets and low loading
• If h() is monotonic, we can sequential scan
• With static addressing we cant have a scalable index, but with extendible addressing we can.

Question 25

RRN

Answer 25

Relative Record Number

Question 26

Making Hashing Dynamic

Answer 26

• h() that grows with key address space
• hash file that grows and shrinks according to demand.

Question 27

Solution for hashing

Answer 27

Extendible Hashing

Question 28

Extendible Hashing, Basic Technique

Answer 28

Introduce search structure that is
1) additional to hash file
2) search structure entries are all based on (or part) of key entry’s hash

Question 29

How to define extendible hashing function

Answer 29

• Select a hashing function ex. prime, folding
• Start with a bucket b0
• Eventually b0 overflows
• We may need more space

Question 30

What if we need more space in extensible hashing

Answer 30

Bucket that overflows must be split in 2 by increasing local bucket depth by 1. Directory must be adjusted, first double its entries, then adjust global depth.

Question 31

What to look for in hashing function

Answer 31

Ensure it can return a huge range. Compute hashing on key value and return a left string of the hash address generated.

Question 32

What happens when the bucket eventually overflows in extendible hashing

Answer 32

Create new bucket b1 and share index entries with b0. Create a directory structure with two bit pattern entries 0 and 1, with each directory entry having a pointer to the respective bucket.

Also mark depth of directory as the max of all local depths. This is called the global depth.

Question 33

Hash indexes can only handle

Answer 33

Simple equality comparisons.

Question 34

Query Planner

Answer 34

consider using a hash index whenever an indexed column is involved in a comparison using the = operator

Question 35

Command to create a hash index in postgres

Answer 35

CREATE INDEX name ON table USING hash(column);

Question 36

Cases to use external hashing

Answer 36

group by queries, joins, distinct keywords, indexing on attributes.

Question 37

Where is internal hashing used (ie. DBMS)

Answer 37

Intermediate IO ops, General use, Function name look up, Expressions look-up