❖ File Management |
Aims of file management subsystem:
Builds higher-level operations on top of OS file operations.
❖ File Management (cont) |
Typical file operations provided by the operating system:
fd = open(fileName,mode) // open a named file for reading/writing/appending close(fd) // close an open file, via its descriptor nread = read(fd, buf, nbytes) // attempt to read data from file into buffer nwritten = write(fd, buf, nbytes) // attempt to write data from buffer to file lseek(fd, offset, seek_type) // move file pointer to relative/absolute file offset fsync(fd) // flush contents of file buffers to disk
❖ DBMS File Organisation |
How is data for DB objects arranged in the file system?
Different DBMSs make different choices, e.g.
❖ Single-file DBMS |
Consider a single file for the entire database (e.g. SQLite)
Objects are allocated to regions (segments) of the file.
If an object grows too large for allocated segment, allocate an extension.
What happens to allocated space when objects are removed?
❖ Single-file DBMS (cont) |
Allocating space in Unix files is easy:
❖ Single-file Storage Manager |
Consider the following simple single-file DBMS layout:
E.g.
SpaceMap = [ (0,10,U), (10,10,U), (20,600,U), (620,100,U), (720,20,F) ]
TableMap = [ ("employee",20,500), ("project",620,40) ]
❖ Single-file Storage Manager (cont) |
Each file segment consists of a number fixed-size blocks
The following data/constant definitions are useful
#define PAGESIZE 2048 // bytes per page typedef long PageId; // PageId is block index // pageOffset=PageId*PAGESIZE typedef char *Page; // pointer to page/block buffer
Typical PAGESIZE
❖ Single-file Storage Manager (cont) |
Possible storage manager data structures for opened DBs & Tables
typedef struct DBrec { char *dbname; // copy of database name int fd; // the database file SpaceMap map; // map of free/used areas TableMap names; // map names to areas + sizes } *DB; typedef struct Relrec { char *relname; // copy of table name int start; // page index of start of table data int npages; // number of pages of table data ... } *Rel;
❖ Example: Scanning a Relation |
With the above disk manager, a query like
select name from Employee
might be implemented as
DB db = openDatabase("myDB"); Rel r = openRelation(db,"Employee"); Page buffer = malloc(PAGESIZE*sizeof(char)); for (int i = 0; i < r->npages; i++) { PageId pid = r->start+i; get_page(db, pid, buffer); for each tuple in buffer { get tuple data and extract name add (name) to result tuples } }
❖ Single-File Storage Manager |
// start using DB, buffer meta-data DB openDatabase(char *name) { DB db = new(struct DBrec); db->dbname = strdup(name); db->fd = open(name,O_RDWR); db->map = readSpaceTable(db->fd); db->names = readNameTable(db->fd); return db; } // stop using DB and update all meta-data void closeDatabase(DB db) { writeSpaceTable(db->fd,db->map); writeNameTable(db->fd,db->map); fsync(db->fd); close(db->fd); free(db->dbname); free(db); }
❖ Single-File Storage Manager (cont) |
// set up struct describing relation Rel openRelation(DB db, char *rname) { Rel r = new(struct Relrec); r->relname = strdup(rname); // get relation data from map tables r->start = ...; r->npages = ...; return r; } // stop using a relation void closeRelation(Rel r) { free(r->relname); free(r); }
❖ Single-File Storage Manager (cont) |
// assume that Page = byte[PageSize] // assume that PageId = block number in file // read page from file into memory buffer void get_page(DB db, PageId p, Page buf) { lseek(db->fd, p*PAGESIZE, SEEK_SET); read(db->fd, buf, PAGESIZE); } // write page from memory buffer to file void put_page(Db db, PageId p, Page buf) { lseek(db->fd, p*PAGESIZE, SEEK_SET); write(db->fd, buf, PAGESIZE); }
❖ Single-File Storage Manager (cont) |
Managing contents of space mapping table can be complex:
// assume an array of (offset,length,status) records // allocate n new pages PageId allocate_pages(int n) { if (no existing free chunks are large enough) { int space_end = last address within space mapping + 1 addNewEntry(db->map, space_end, n); } else { grab "worst fit" chunk split off unused section as new chunk } // note that file itself is not changed }
❖ Single-File Storage Manager (cont) |
Similar complexity for freeing chunks
// drop n pages starting from p void deallocate_pages(PageId p, int n) { if (no adjacent free chunks) { markUnused(db->map, p, n); } else { merge adjacent free chunks compress mapping table } // note that file itself is not changed }
Changes take effect when closeDatabase()
❖ Multiple-file Disk Manager |
Most DBMSs don't use a single large file for all data.
They typically provide:
Using multiple files (one file per relation) can be easier, e.g.
❖ Multiple-file Disk Manager (cont) |
Example of single-file vs multiple-file:
Consider how you would compute file offset of page[i] in table[1] ...
❖ Multiple-file Disk Manager (cont) |
Structure of PageId
If system uses one file per table, PageId
PageId
❖ DBMS File Parameters |
Our view of relations in DBMSs:
❖ DBMS File Parameters (cont) |
Typical DBMS/table parameter values:
Symbol | E.g. Value | |||
r | 106 | |||
R | 128 bytes | |||
b | 105 | |||
B | 8192 bytes | |||
c | 60 | |||
Tr ,Tw | 10 msec | |||
one page in memory |
- | ≅ 0 |
Produced: 30 Apr 2023