Lezione 2-3-4
Source: Fundamentals of Database Systems 7th Edition - Chapter 16
Database structure
We have a view, a logical part and a physical part. Logical and physical part are independent each from each others. In this course we will go at very low level part
Storage organization of Databases
Databases typically store large amounts of data that must persist over long periods of time, and hence the data is often referred to as persistent data. Databases need to be stored on secondary storage for obvious reasons.
Why physical database design
The process of physical database design involves choosing the particular data organization techniques that best suit the given application requirements from among the options.
Primary File organization
Data stored on disk is organized as files of records. There are several primary file organizations, which determine how the file records are physically placed on the disk, and hence how the records can be accessed. The three main organizations are:
- heap file (unordered file)
- ordered file
- hashed file
Other organizations use the B-Trees.
Operations on file
- Read
- Write
- Delete
- Update
There are differences in some file organization when you read a single record or when you read more than a record.
- FindAll: search all records in the file that satisfy a search condition
- Find n: find the first n records that satisfies a search condition
As we will see, some file organizations require periodic reorganization. An example is to reorder the file records by sorting them on a specified field.
Calculating Time to Read From Disk
We use relative values because absolute values depends from the hardware implementation. Let’s consider a system with RAM, Cache and Disk The total time to read a record is:
Disk is order of magnitude slower than ram, this mean we can ignore the first term
Cache
If we have a cache, we need to consider also the time to read from a cache. A cache doesn’t always contain the record we need, but when it does, it sensibly decrease the time required to retrieve a record.
Let’s consider hit ratio
Hit Ratio is not an absolute valute: it’s an average value. Now, let’s consider this ratio inside the formula to read a record
Where N is the number of requests.
What does it mean "
The cache scales linearly the time of requests it have a dramatic impact on velocity.
We will not consider time to read from ram and cache because it’s two order smaller than read from disks.
Number of I/O Operations
Technology to read from disk evolves over time and became faster (i.e SSD). Instead of using the actual time we will use the number of I/O operations.
The previous formula becomes:
Now, consider this table of students. (matricola, name, surname, birth day, sex)
| MAT | N | S | BD | S | |
|---|---|---|---|---|---|
| 123 | m | r | 1212 | m | |
| 124 | g | v | 1313 | f | |
| 125 | f | g | 1312 | m |
Pages
Storage is organized in pages. (as you know from operating system). The page is the unit of transfer from secondary storage to primary storage. If i go from disk to ram the minum i write is one page. One page depends on the system, it could be 1KB, 8kB and so on. Depends from the hardware characteristics.
We’ll consider just the number of pages, because the time is variable and depends from hardware implementation.
Row-wise organization of pages
Row-wise means that every row from the table is saved in the same page. It’s the most natural way to store a table into pages.
[] [] []
[] [] []
BFR
BFR is a value that say how many information goes into a single page. This value depends from various variables:
- The size of a single record that we’ll call
- The size of a single page that we’ll call
Example: fixed length
Let’s consider a page of 1 KB (1024). Say that our table use records with fixed length. matr 10 + name is 20 + surname is 20 + bd is 7 + 1 = 58 BFR would be calculated doing 1024 / 58 = 17.6
Example: variable length
If variable lenght may change, i need to consider an average. For example instead of 10 20 20 7 1 i could consider 10 10 10 7 1 = 38. Now i got BFR = 1024/38 = 26.9
Spanning vs Non Spanning.
There is a problem with these values: they are not integer. This mean that in a single page, 26 records fits well, but there isn’t enough space for the last one. I have two choices here:
- Spanning: trim the record and write some of it in the next page. To use spanning we also need to use a pointer to this data. Let’s consider
the size of the pointer - Non-spanning: write the entire record in the next page
Adopting spanning as strategy, the BFR formula becomes:
Example: how many pages i need to fit an entire table?
Let’s consider a database with 10.000 records. First i need to calculate how many students record fits in a page.
I need 385 blocks
Propriety of BFR
The higher the BFR, the more efficient the system would be because you retrieve more data with one operation.
Heap Files (or Unordered Records)
It’s the simplest and most basic type organization. Records are placed in the file in order in which they are inserted, so new records are inserted at the end of the file.
Cost of operations:
- Reading one record costs
in the worst case. If you brought an impossible condition in the query that is not met by any of the record, the cost would be the worst case anyway. - Reading multiple records: the costs doesn’t change, O(N)
- Insert one record: it’s very efficient, because we add the record at the end of the file. O(1). Even if there is no more space in the page, it would costs only a few extra operations, so we assume it’s still O(1)
- Delete one record: the program first must find the block i, it would cost (
) on average, then we have to move all the next files upward in the memory location to avoid space waste, then it would cost on average.
Deletion Marker
It’s a technique used for record deletion. A record is marked for deletion (i.e using a deletion bit, 1 for deletion, 0 for keeping it), then periodically the table is reorganized to reclaim the unused space of deleted records.
Using this technique, the deletion is less expensive because you only need to find the block
- Update one record: we could see this operation as delete + insert, that would cost
with the deletion marker. This works if the record is of fixed static size. - But, if the new value is bigger, then the new record doesn’t fit where the old record would. Se we don’t do the update “in place” (same memory location) but we do it “out of place”, in another place.
Heap file is good if you have a very load of insert but it’s not so good when you have to delete, or update because it’s not efficient.
Sorted Files (or Ordered Records)
We can physically order the records of a file on disk based on the values of one of their fields—called the ordering field. In our previous example, that would be by the student matricola.
The memory footprint doesn’t change. The BFR doesn’t change. We are talking of changing the order of records, no difference in memory.
Cost of operations
(nota, sul libro si parla di un costo in termini di blocchi, quindi nel caso della lettura sarebbe
- Read one record: using binary search, that would be
where is Number of Pages. - Read k records: using binary search, say i need to read records from 100 to 104, with k=4, it costs me
, if k is small, it can be ignored. - Read k records, but k > BFR: in this case, i need to calculate how many pages i need to store the k value. So it would be
. The total cost would be - Inserting a record: costs more than heap file because i need first to find the location where it would be placed, then move all the records to make space for the new one, and then inserting it. It would cost me
- Delete a record: find it, delete it, shift back half file, it costs
or if i don’t use a log file - Update a record: since it combines insertion an deletion, it’s the most expensive operation, the costs is given as sum of the previous one. In the worst case
A special case for Sorted Files would be: insert multiple records that are not sorted. The cost would be:
In real life situation, it’s unlikely that records are in the same location or page, so you have to do anyway a full scan. A full scan of a very large file with billions of record may even break the server.
Column-wise organization of pages
[] [] []
[] [] []
This mean we store first all matricolas, then all the names, then all the surnames and so on. If all the fields are fixed length it’s easier. If all the files have variable lenghts, we don’t know the matching record when we find it in memory.
Consider the table in our previous example. It could be consider as splitted table as if you have the table for name of students, another for surname of students and so on. In this way, you can reconstruct record, matching the name, surname and so on, without accounting for the physical record position.
What is the record size of matricola and name? For example let’s consider 10 + 10 = 20. Let’s consider a system that does trimming without spanning.
What would be the BFR of this table?
51 > 38, in our previous column wise example, so theoretically it’s more efficient to retrieve a single record. How many pages do i need to store the first column?
it is less than half of before. But we store it in just names. Then i do the same for surname, birthday, and so on.
Why should this would be advantegous? If i want to retrieve a record, i need to research multiple time, even if tables are smaller. To retrieve one record here i have 4 tables, so i have to pay four times the scan of the table. It’s true that they are smaller but it isn’t advantegeous for retrieving records.
If i want to retrieve a single field from a record, the column-wise approach is better. So think of operations like count, aggregations and so on.
In general: there is no system that works better than another. There are only choices. In one situation is better to use one structure, in another it is better to use another structure. One of the things that concern database optimization is finding optimal configuration, that depends on the load. But usually loads changes, then the configuration has to change too.
Hashing Techniques
Another type of primary file organization is based on hashing, which provides very fast access to records under certain search conditions. This organization is usually called a hash file.
The search condition must be an equality condition on a single field, called the hash field (or hash key if it is the key of the record). The idea behind hashing is to provide a function h, called a hash function or randomizing function, which is applied to the hash field value of a record and yields the address of the disk block in which the record is stored.
Example, let’s consider a teacher that has to assign 35 laboratory station to 100+ students. The teacher is busy and doesn’t have the time to register and manage each one. Also he needs three iterations (because 100/35
where,
Internal Hashing
Cost of operations
- Retrieve one student/Assign a station to one student/Delete a student: The costs for every operation is always O(1)
Collisions:
A collision occurs when the hash field value of a record that is being inserted hashes to an address that already contains a different record. In this situation, we must insert the new record in some other position, since its hash address is occupied. The process of finding another position is called collision resolution
Hashing has some problems relative to collisions, also called overflow (for example if an hash function returns the same location in memory for two records).
There are numerous method for collision resolution, including the following:
- Open addressing. Proceeding from the occupied position specified by the hash address, the program checks the subsequent positions in order until an unused (empty) position is found.
- In our previous example, it would be like a student wait at the door and the next available station will be assigned to they.
- In that case it’s slightly more expensive to search because you need to search in that location and in the following. In a worst case scenario where all slots are full and you pay linear scalar time. (It also means that you sized wrongly the memory that you have).
- Chaining. For this method, various overflow locations are kept, usually by extending the array with a number of overflow positions. Additionally, a pointer field is added to each record location. A collision is resolved by placing the new record in an unused overflow location and setting the pointer of the occupied hash address location to the address of that overflow location.
- Multiple hashing. The program applies a second hash function if the first results in a collision. If another collision results, the program uses open addressing or applies a third hash function and then uses open addressing if necessary. Note that the series of hash functions are used in the same order for retrieval.
The goal of a good hashing function
- Distribute the records uniformely over the address space so as to minimize collissions. This way, we locate a record with only a single access
- Not leaving too many location unused. According to simulations and analysis, it is better to keep a hash file between 70% and 90% full so that the number of collisions remain low and we do not waste much space.
On the (2), according to our previous example, the teacher needs 3 iterations, we say 3 slot. What if he chooses instead 6 slots? It may seems to be a waste of space, only 15+ students for each iteration. But, actually it makes database more robust to new records. If the table changes size and becomes bigger i have no degradation of performance.
On the other size if i have exactly 105 students, with 35 locations, i have exactly 3. But it is not going to work because i hash is not deterministic, i will never have slot with exactly number of number so i need some more space.
On the (1), what i need to do when choosing an hash function? I need to be ensured that N records are bigger than the number of pages. How much bigger? It depends, it’s your choice. Do you expect data to grow fast? how likely they grow? will they shrink?
if you use an N >> Np, most of your pages will be quite empty so i will do a lot of lessons with almost empty room, but it means if tomorrow i double the studentds then i will have no degradation. If students decrease to 50 for example, why i should use anymore 3? With hash your critical decision is how many pages will you reserve for hashing. Once you decide it’s very expensive to change it. What i would do is to read the entire file, apply the new hash function to every record. I have to read and write all the file. So it’s 2NP, twice linear scalar.
To put it all togheter, hashing files techniques make retrieving very fast. But, if the files grow, then you may experience overflow and collisions, and rearranging the file is very expensive.
The problem of hashing is that if the size of the file changes then you start to get overflow, and if for example the file doubles then you have to read and write the whole file. You can have a very big file that is unmaneagable.
BFR and CLOB/BLOB
In memory, there are usually special symbols that indicate the end of a record, such as the dollar sign ($) for end of field and the pound sign (#) for end of records. If the record is fixed you can use the length of the field and of the record, but if you have even one var char, then the length is variable and you need to use special symbols.
Most of the time, relational data will get BFR > 1. It means more records in one page. Sometimes, you get a BFR < 1. This means that i have a very long text field. For example, var char fields in Oracle can be as long as 256K, so you can have a var char like a description that is 256K b just this field. If you have such a big field, you need multiple page and the record is trim across multiple pages.
This situation is very bad because you need to retrieve multiple pages to even one record, and the system becomes very slow, no matter what file organization you use. A solution could be to use the column-wise approach and store the big field in another file.
But what happen with unstructured data like a photo stored in bits? From a database point of view, a photo is memorized like a long string of bits. Usually database are equipped with a type called BLOB/CLOB. Generally speaking, a LOB (Large Object) can be:
- CLOB: Character Larg Objects
- BLOb: Binary Large Objects
What usually it is done, is that you don’t memorize the entire BLOB in the field. Usually, it is only memorized a POINTER that points to the real memory location of the file, in a separate memory area.
The importance of free space in your memory storage system in static file structure In static file structure, you need some free space in your storage beause otherwise, as we saw in techniques like hashing, you get a degradation of performance when you do updates.
In Oracle there is PCT FREE https://www.orafaq.com/wiki/PCTFREE
PCTFREE is a block storage parameter used to specify how much space should be left in a database block for future updates. For example, for PCTFREE=10, Oracle will keep on adding new rows to a block until it is 90% full. This leaves 10% for future updates (row expansion).
Hard Disks
Se metto tutti i dati nello stesso cilindro (dato che i piatti sono fatti di cerchi concentrici) pago solo una volta il seek time. Tuttavia, se i dati sono più grandi e non ci vanno in un cilindro, allora mi conviene mettere i dati nel cilindro adiacente, il più vicino. Quindi il modo migliore di conservare i dati e ad anello. Perché tutti i dati sono vicini, quindi ti muovi solo un po’ e minimizzi il tempo per muovere la testina. This works ideally in an environement where you never have to write. For recorded structured data, it’s not a big idea, it’s better to have empty space, some room between data. Because it will make the system more robust to change the file size. But if you have blobs for example, they must be read sequentially one bit a time because they are just a long list of bits. So you never write, because if you write the blob get corrupted. And for this property, it’s very convenient to save blob this way.
If you have like a film that is 4GB, you don’t store it in a relational database. You have to think how do i read the film? One bit a time. Even the time used to read film, to see the film. You don’t need the speed, because you dn’t need to see a film of two hours in 10 minutes. The time to consume the film is constraine that depends from the human that it’s going to see it.
Hashing Techniques that allows Dynamic File Structure
A major drawback of the static hashing scheme just discussed is that the hash address space is fixed. Hence, it is difficult to expand or shrink the file dynamically.
Hashing techniques that allow dynamic file structure are based on hashing, where we slightly modify the hashing. If the file changes also the hash function changes accordingly.
Linear Hashing
Following quotes are from the book (see start of this note, p580)
The idea behind linear hashing, proposed by Litwin (1980), is to allow a hash file to expand and shrink its number of buckets dynamically without needing a directory.
Definition
Suppose that the file starts with M buckets numbered 0, 1, … , M − 1 and uses the mod hash function h(K) = K mod M; this hash function is called the initial hash function
Overflow because of collisions is still needed and can be handled by maintaining individual overflow chains for each bucket. However, when a collision leads to an overflow record in any file bucket, the first bucket in the file bucket 0 is split into two buckets: the original bucket 0 and a new bucket M at the end of the file. The records originally in bucket 0 are distributed between the two buckets based on a different hashing function hi+1(K) = K mod 2M.
A key property of the two hash functions
and is that any records that hashed to bucket 0 based on will hash to either bucket 0 or bucket M based on ; this is necessary for linear hashing to work
And this property is essential for further growing memory and for shrinking.
As further collisions lead to overflow records, additional buckets are split in the linear order 1, 2, 3, … .
How do i retrieve a record?
To retrieve a record with hash key value K, first apply the function
to K; if , then apply the function on K because the bucket is already split. Initially, n = 0, indicating that the function hi applies to all buckets; n grows linearly as buckets are split.
Example from class
Let’s start with four pages.
0 1 2 3
[] [] [] []
In our previous example i split students in four groups.
Let
Say that something happens, and our course becomes popular and we get more students to follow it. If i get more students in the third slot, i get the room full, then i have an overflow. The overflow is managed locally so i create another page that is a local overflow page. As soon as the first overflow happen, i add a page at the end of memory area.
0 1 2 3
[] [] [] []
x x | x
x x [] x
This is basic hashing with local overflow as we saw in Hashing Techniques. Now, let’s consider a system where we count the number of overflow. Let N be the number of overflows. In this example, now N =1. What i do is adding another page, and changing my hash function.
0 1 2 3 4
[] [] [] [] []
x x | x x
x x [] x x
I add another page, and i change the hash function to:
In this way, if an overflow happen say in the Page 0, with this new hash function, the students will be splitted across the 0th and 4th page. If i get another overflow, and and the number become N=2, i add another page.
0 1 2 3 4 5
[] [] [] [] [] []
x x | x x x
x x [] x x x
Some calculation stuff the prof did but i don’t want to order right now:
If i get another overflow, and and the number become N=2. Then i use
. 16 / 8 rest = 1, then remains here. 17/8, rest = 2, then i add another page, and we have 0 to 5 pages. Rest of two or six and i add pages at the end. All the overflow from page 2 will be split between here and the last page. So i’m removing the overflow location.
This system is called linear hashing, because we linearly add new pages so the memory grows linearly.
The advantage of this system is that we are not going to read/write the full page in case of overflow or reorganization. As we saw in Hashing Techniques, reorganization is the most expensive operation we can do.
We saw memory grows, but the same holds for memory shrink. If students decrease in number, then we can shrink back the memory and use the
Another way to do this is using the file load factor (FLC), that is calculated as:
Cost of operations:
- Find operation: O(1) + the cost of overflow. Usually you don’t get mostly overflow. When i increas the pages, the overflow disappear, i merge the two pages.
- Find operation if it is not divided by the module in the hash function: O(1) + overflow + doubling the first page, it’s in the order of 3 or 4 operations.
Conclusion: In many real systems you don’t have many choices, here we are considering an idea case. There is no standard, different companies uses different solutions for example In IBM relations database you don’t find them in Oracle yes. We will see that mixing these ingredients together, we get a standard structure that is not fancy and works well for most cases. The main goal is to get lower time for insertion and deletion.
Spiral Hashing
Consider a logarithmic spiral.
Imagine that the spiral is cut at
Quadrant consideration on pages: If we consider a division by quadrants, on the first quadrants there will be some few pages, on the second there will be more pages, on the third even more, on the fourth even more pages. So the distribution of pages is not equal for every quadrant.
How does it works
Consider a simple hash function like
Overflow is managed in the same way as in Linear Hashing, but the memory doesn’t grow linearly but exponentially accordingly to a logarithmic or exponential function. It’s as the spiral “moves”. When the spiral moves, then the area memories at the start of the spiral are removed and their content is spread across more pages at the end.
Memory shrinkage works the same as linear hashing, thus you still use a threshold and calculate how empty are pages. The difference as seen in “advantages” is that you don’t change the hash function.
Advantages
- Memory grows exponentially, so handles well data that grows rapidly. This atleast in theory, in practice, since this is only a logical representation, in physical layer is not convenient or implemented to move “memory” i.e. pages around, so you still use the firsts.
- You only need a single hash function.
- While in Linear Hashing you usually have two active function and in general
function. Every time you change hash function you also need to reorganize everything, which is very expensive. - So, Spiral Hashing is better because you reuse the same hash function
- While in Linear Hashing you usually have two active function and in general
Disadvantages:
- Like in Linear Hashing, content isn’t distributed equally and the start of the file is overloaded compared to the end of the file. This because the number of expected records is very high at the beginning and less at the end. In Spiral Hashing we should also consider that at the end of the spiral we have far far more pages than at the start, so the content is spread across these more pages. There is more free space and in general is more efficient.
The density could be calculated as:
Sources:
Clustered storage (or sorted storage)
Say we have a table with students and one of the fields is their nationality. A possible way to organize data in memory would be with consecutive records with the same value in the field “nationality”.
Why should i do this? Think of a students table, with matricola, surname, name and so on. Say i have another table with exams that each students did, so a foregin key connect an exam with the matricola of the student. We can use clustered storage for these two table: in a single page we memorize the student and the exames they did.
This operation is in certain way similar to a join operation. We pre-joined the table. This is advantageous because sometimes, data is so BIG that a join operation would break the server. It’s also advantageous if a joined table would be memorized across many different pages because of redundancy data. In our example, the “matricola” and other information about the students are redundant.
If we implement data in this say, we “don’t pay the join” (costs) because we can just scan the page and get the same result.
Sources:
- Lecture
< Index