COMP9315 24T1

Exercises 03
Pages and Tuples

Assume that a data file is composed of 4KB pages, where each page is structured as follows:

The start of the page contains a tuple directory which is a sequence of three-byte values, where the first 12 bits contain the offset into the page of the tuple and the second 12 bits contain the tuple length.

Write a C function that takes three parameters: an open file descriptor, a page number and a record number and reads the data for the corresponding record. Do not read the whole page; read just enough of the data to solve the problem. Dynamically allocate a memory buffer large enough to hold the tuple data when read in. The function should return a pointer to the start of the tuple memory buffer.

The function should do appropriate error-checking and return NULL in the case that any operation cannot be completed. Use the following function template:

char *getTuple(int inFile, int pageNumber, int recNumber) { ... }

Hint: when a directory value is read into memory, the high-order bits contain the offset and the low-order bits contain the length.

Use only the low-level i/o operators (system calls) such as open(), read(), write(), lseek(), etc.

Answer:

We assume that all of the relevant .h files have been included.

#define PAGE_SIZE 4096

char *getTuple(int inFile, int pageNumber, int recNumber)
{
	// position file at start of page

	off_t pageAddr = pageNumber * PAGE_SIZE;
	if (lseek(inFile, pageAddr, SEEK_SET) < 0)
		return NULL;

	// re-position the file to the start of the tuple directory entry

	off_t dirOffset = recNumber * 3; // 3 bytes per directory entry
	if (lseek(inFile, dirOffset, SEEK_CUR) < 0)
		return NULL;

	// read 3-byte directory entry for this tuple

	unsigned int dirEntry;
	if (read(inFile, &dirEntry, 3) != 3)
		return NULL;

	// extract tuple offset and length from directory entry

	unsigned int tupOffset, tupLength;
	unsigned int lengthMask = 0x00000fff; // low-order 12 bits
	unsigned int offsetMask = 0x00fff000; // high-order 12 bits

	tupOffset = (dirEntry & offsetMask) >> 12;
	tupLength = dirEntry & lengthMask;

	// allocate memory buffer to hold tuple data

	char *tupBuf;
	if ((tupBuf = malloc(tupLength)) == NULL)
		return NULL;

	// position file at tuple location

	off_t tupAddr = pageAddr + tupOffset;
	if (lseek(inFile, tupAddr, SEEK_SET) < 0)
		return NULL;

	// read tuple data into buffer

	if (read(inFile, tupBuf, tupLength) != tupLength)
		return NULL;

	return tupBuf;
}

Consider a data file containing tuples with a page structure similar to that in the previous question. Pages are 4KB in size, and each page contains a tuple directory with 100 entries in it, where each entry is 3-bytes long. Assuming that the (minimum,average,maximum) tuple lengths are (32,64,256) bytes and that the file has 100 pages, determine the following:
1. The minimum number of tuples that the file can hold
2. The maximum number of tuples that the file can hold
Answer:
1. The minimum number of tuples is zero (trick question)
2. Maximum occurs when all tuples are minimum size (or close to it). Each page uses 300 bytes for the tuple directory, leaving 4096-300=3796 bytes of space for tuples. In theory, this amount of space could hold floor(3796/32) = 118 tuples; however, the page directory only has space for 100 tuples, so 100 tuples is the maximum number of tuples per page. Since we have 100 pages, the file can hold 100*100=10000 tuples.

Consider a variation on the above scenario. Rather than pages having a fixed size tuple directory, the tuple directory can grow and shrink depending on the number of tuples in the page. For this to work, the tuple directory starts at the bottom of the page (address 0) and grows up, while tuples are added from the top of the page (address 4095) and grow down. If all other factors are the same (total 100 pages, (min,avg,max) tuple lengths (32,64,128)), what is the maximum number of tuples that the file can hold? You may assume that tuples can begin at any address (i.e. they do not have to start at a 4-byte address).

Answer:

The maximum number of tuples still occurs when all tuples are minimum size. However, in this case we need to balance the tuple space against the directory space. For example, if we have 100 tuples, then the top 3200 bytes of the page are occupied by tuple data, leaving 896 (4096-3200) bytes for the slot directory. We can clearly add more tuples, since we have space for them and space to hold their directory entries. Eventually, though, there will be enough tuples that there is no more room to add directory entries for them and the page is full. Since each tuple requires space for its data (32 bytes) plus 3 bytes for a directory entry, we can compute the maximum tuples that will fit in a page by finding the maximum N such that (3*N + 32*N) < 4096. In this case, N=117 and so this the file can hold at most 11700 tuples.

This scenario is not totally implausible since some common tables have fixed-size tuples (consider a "link" table with just two foreign keys). Of course, in such a case, we wouldn't need the tuple directory either, since we could simply compute the tuple offset based on its number in the page.

[Based on Garcia-Molina/Ullman/Widom 13.7.1]
Consider the following relational table:
```
create table Patient (
   id       integer primary key,
   ssn      char(20), 
   name     varchar(30),
   addr     varchar(60),
   history  varchar(200),
   born     date
);
```
Consider how records of this type might be represented when stored in disk blocks. If a pointer within a record requires 4 bytes and the record length is also stored as a 4-byte quantity, how many bytes would be needed for each Patient record, excluding of the space required to store the variable-length fields?
For variable-length records (varchar), assume that we don't need a terminating char (e.g. '\0') but we do need to allocate a multiple of 4 bytes to the field to ensure alignment of possible following integer fields. (These additional bytes would not be necessary if the fixed-length fields were all stored at the front of the record.)

How many bytes would be required for the following instances of Patient records:
```
insert into Patient values (
   12345678, '222-444-555-7777',
   'John Smith', (10)
   '50 Smith  St, Smithton, 2345', (28)
   'Previously diagnosed with URTI, also weak ankles', (48)
   '1966-12-2'
);
insert into Patient values (
   87654321, '123-456-654-4321',
   'Jane Brown', (10)
   '15 Brown  St, Brownsville, 2427', (31)
   'Prior history of urinary tract infections', (41)
   '1966-12-2'
);
```
(Note that the (string lengths) given after each string are not part of the insert statement).
Answer:

Assume that the record has the following structure:
The fixed storage cost includes:
- the record length (4 bytes)
- offsets for each of the fields (4 bytes times 6)
- fixed-length fields id (4 bytes), ssn (20 bytes), born (4 bytes for date)
This gives a total fixed storage cost of 4+24+4+20+4 = 56 bytes

For the John Smith record, add additional bytes for
- name (12 bytes ... 10 bytes rounded up for alignment)
- addr (28 bytes ... no rounding up needed)
- name (48 bytes ... no rounding up needed)
giving a total of 56+12+28+48 = 144 bytes

For the Jane Brown record, add additional bytes for
- name (12 bytes ... 10 bytes, rounded up for alignment)
- addr (32 bytes ... 31 bytes, rounded up)
- name (44 bytes ... 41 bytes, rounded up)
giving a total of 56+12+32+44 = 144 bytes
It is a coincidence that both records come out with the same length.