Assignment is due Friday, January 25 at 5:00PM.
Last updated January 16, 2019 at 10:30PM.
In this assignment you will have these tasks to complete:
These tasks are described in detail in the following sections.
Before you can begin working on this project, you must be able to check out and build your team's codebase. You are also strongly encouraged to set up IntelliJ IDEA so that you may easily navigate the code, build the project, and run the debugger. Lots of detailed information is available in the introductory documentation. If you have any questions or issues not addressed by the documentation, please don't hesitate to contact Donnie and/or the TAs.
Once you have completed all of your work, along with the design document for the project, your team will need to fill out and upload a short document containing logistical details to the course website. Part of this information includes how much time each teammate spent working on the assignment. This information is essential for us to get good feedback on the scope of assignments, so you will receive point deductions if it is not included. Future generations of CS122 will thank you!
As it stands, NanoDB does not yet support updating or deleting tuples. Your first tasks will be to complete the operations of updating and deleting tuples in a table. Tables and indexes are both implemented as "tuple files" in NanoDB, which allows us to use the same storage implementation to manage both tables and indexes.
NanoDB heap tuple files have a simple structure. The major aspects are described here, along with the classes that provide the associated functionality. All of these classes are in the edu.caltech.nanodb.storage.heapfile package; you should go to this package and read through the classes mentioned here.
Page 0 (or block 0; we use the terms interchangeably) is the header page of the table file, and stores details such as the table’s schema. No tuples are stored in page 0.
The HeaderPage class provides some lower-level operations for reading and writing fields within the header page; these operations are exposed as static methods.
All other pages in the table file are data pages, implementing the slotted-page data structure as described in class. The DataPage class provides lower-level operations for manipulating data pages; again, these are exposed as static methods.
The HeapTupleFileManager class provides the ability to create, open and delete tuple files that use the heap-file organization. When a table is opened for scanning, this class is used to open the table’s corresponding tuple file.
The HeapTupleFile class provides operations like scanning a tuple file, inserting a record into a tuple file, and so forth. The implementation of these operations relies heavily on the HeaderPage and DataPage classes.
The HeapFilePageTuple class represents individual tuples whose data is backed by the file block that contains the tuple. You will see that the bulk of the page-tuple abstraction is implemented in the edu.caltech.nanodb.storage.PageTuple class, so that the tuple-storage code can be used in multiple file formats. (For example, if you were to implement a hash-file format, you could make a subclass of PageTuple to read and write tuples in your hash files.)
When a tuple is to be deleted, the HeapTupleFile.deleteTuple() method is called with the specific tuple to be deleted. This method determines the slot-index of the tuple, and then uses the DataPage.deleteTuple() method to delete the tuple at this slot.
Enable tuple deletion by completing the implementation of the DataPage.deleteTuple() method. Your implementation should conform to these guidelines:
Reclaim the space that was previously occupied by the tuple being deleted by using the deleteTupleDataRange() helper function. Make sure you don’t accidentally clobber adjacent tuples.
Set the tuple’s slot to the EMPTY_SLOT value.
Finally, if there are empty slots at the end of the header, remove them so that this space can also be reclaimed. Remember that you cannot remove an empty slot if it is followed by one or more non-empty slots.
Enable tuple updating by completing the implementation of the setNullColumnValue() and setNonNullColumnValue() methods of the PageTuple class. These methods are somewhat tricky to get right. They are called by PageTuple.setColumnValue() to modify an existing tuple’s column values.
The setNullColumnValue() method sets the bit in the tuple's null-bitmask to indicate that the column’s value is now NULL. Then it removes the space that the old value used to occupy. (Obviously, none of these steps are necessary if the old value for the column was NULL.)
The setNonNullColumnValue() method must replace any existing value for the column with a new value.
Some general implementation details are included as comments in these methods.
The Buffer Manager has a challenging job; among other things, it must decide which file buffers to keep in memory, and which should be evicted. Further complicating this task is the fact that queries may be accessing many different tuples, and the page containing that tuple data must be kept in memory until the query is finished using it.
A simple and common approach to solve this problem is to "pin" disk pages in memory while they are being used; the Buffer Manager cannot evict a page that is currently pinned. When a page is no longer in use, it is "unpinned," allowing the Buffer Manager to evict the page. This is a simple reference-counting mechanism, but it works very well to let the Buffer Manager know what it may safely evict.
In NanoDB, both DBPage objects and Tuple objects may be pinned and unpinned. The Buffer Manager works with pages, and queries work with tuples. When a DBPage is retrieved from the Buffer Manager, its pin-count is always incremented so that it won't immediately be evicted out from under the requester. Similarly, when a new tuple is retrieved, the tuple pins its backing DBPage to prevent the page from disappearing out from under it. When a tuple is unpinned, it will automatically unpin its backing DBPage. Of course, these objects may also be re-pinned by various components (e.g. a sort plan-node that needs to keep the tuple around for a while). However, they must eventually be unpinned, or else the Buffer Manager will not be able to reclaim the corresponding buffer space.
Make sure your implementation properly unpins tuples (and disk pages, if necessary) when they are no longer needed. (Recall that unpinning a tuple will also unpin its corresponding disk page, so you only have to unpin a disk page if you read it separately, e.g. for the header page which contains no tuples.)
We can simplify this task by recognizing that we only need to unpin a tuple when it is no longer being used by the database engine. For example, a "select" plan-node only needs to unpin tuples that don’t satisfy the selection predicate; these tuples will no longer be used in the execution plan. Another example is, all tuples produced by an execution plan should be unpinned once we have finished using them (e.g. to update or print them).
For now, concentrate on the following areas:
The HeapTupleFile implementation (including the changes you make to it) may need to pin and/or unpin pages as they are traversed.
To illustrate how to approach the management of page- and tuple-pins, the HeapTupleFile.getFirstTuple() method already manages page-pinning and unpinning properly. There are explanatory comments in the code as well.
The HeapTupleFileManager implementation may also need to pin and unpin the header page.
Inserts, selects, updates and deletes all operate on tuples produced by a query plan. Once the tuple has been processed, it must be unpinned. This is easy to accomplish within the QueryEvaluator class (in edu.caltech.nanodb.queryeval), in the executePlan() method.
(These are tuples that made it all the way up through the execution plan.)
The SelectNode class (in edu.caltech.nanodb.plannodes) must unpin tuples that don't satisfy the selection predicate. (See the getNextTuple() method.) Since file-scans and simple selects both derive from this class, they will both properly unpin tuples after this class is updated.
(This will take care of tuples that don't make it all the way up through the execution plan.)
The NanoDB Buffer Manager maintains a strict upper bound on the size of the buffer pool. The size is exposed as the "nanodb.pagecache.size" property, and can be read or written during operation. While you are implementing the proper pinning/unpinning steps in your database, you may want to leave the pool size very large (its max size is 1GiB), but once you have pinning/unpinning working properly then you should be able to shrink the buffer-pool size down to very small sizes (the minimum is 64KiB, the largest size of a single data page) and still see correct operation.
Fortunately, even if you don’t get this exactly correct, the Buffer Manager will forcibly unpin all disk pages still held at the end of each SQL command. However, it will also nag you about this if too many pages are still pinned at the end of your queries. Releasing pages when they are no longer necessary means your database will operate more efficiently. Therefore, you will have point deductions on your submission if your implementation leaks too many buffer pages during operations.
Initially, NanoDB has a very simplistic approach to managing its heap files. In each heap file, NanoDB devotes the first page (page 0) to schema and other high-level details, and the remaining pages are devoted to tuple storage.
When NanoDB inserts a new tuple into a heap file, it follows a very simple process: Starting with page 1, it looks for enough space to store the tuple. If the page being considered has enough space then the tuple is added to that page. (Note that this is a first-fit strategy, not a best-fit strategy.) If not, NanoDB goes on to page 2, and then page 3, and so forth. If NanoDB reaches the end of the file then it creates a new page and stores the tuple there.
This approach is very slow (O(N2)) for adding a large number of tuples, but it does have the benefit of using space reasonably effectively. However, there is no reason why we shouldn’t be able to have both benefits; fast inserts as well as efficient space usage.
The implementation of this strategy is in the addTuple() method of the HeapTupleFile class, in the edu.caltech.nanodb.storage.heapfile package.
Note that two configuration properties also affect NanoDB storage performance.
Key constraints cannot be enforced efficiently without indexes. NanoDB includes code to enforce them inefficiently, because constraints are part of what makes relational databases nifty. You will want to avoid using tables with primary or foreign keys in your testing. If you wish to use such tables, you may want to disable key-constraint enforcement with the "nanodb.enforceKeyConstraints" property.
In the first assignment, the Buffer Manager is configured to flush all in-memory pages out of the pool after every command. This is not a good strategy in normal operation, because if one command accesses a data page, chances are good that a subsequent command will access the same data page, and therefore we would prefer to read it from memory instead of from the disk.
The reason why we flush the Buffer Manager after every command is so that all storage-layer performance issues will be fully evident. We will disable this behavior in subsequent labs, but in this lab we will retain this behavior.
(Note: The "nanodb.flushAfterCmd" property can be used to enable or disable this behavior. It must be enabled for this assignment.)
You can give NanoDB a try on this front by creating a simple table. After building NanoDB, start it with the nanodb script (or nanodb.bat on Windows), and create a simple table:
CREATE TABLE insert_perf (
id INTEGER,
str VARCHAR(200),
num FLOAT
);
INSERT INTO insert_perf VALUES ( 1, 'hello', 3.14 );
INSERT INTO insert_perf VALUES ( 2, 'goodbye', 6.28 );
EXIT;(A .sql file for this schema is in the schemas/insert-perf directory.)
If you run the above commands and then look in the datafiles directory, you should now see a file named insert_perf.tbl. This is the table that we just created and then added the tuples to. It will be 16KiB in size since the default page-size is 8KiB. (You can change the default page size via the nanodb.pageSize property.) If you want to get rid of this table, you can either delete the insert_perf.tbl file from this directory (but make sure NanoDB isn't running when you do this!), or you can use the command "DROP TABLE insert_perf;" in NanoDB.
How do we measure the actual performance? Wall-clock time (i.e. the actual time that the test takes to run) is not useful, because the test will be very dependent on computer hardware. Therefore, NanoDB includes a "SHOW 'STORAGE' STATS" command (Note that the string "storage" must be in single quotes! It is case-insensitive.), which prints out some statistics that give us an approximation of the storage performance:
storage.pagesRead and storage.pagesWritten are the number of disk pages that have been read and written since the NanoDB server was started. (Note that this statistic is independent of the actual size of the pages.)
storage.fileChanges is the number of times NanoDB accessed a different file from the previous file that was accessed. In a typical scenario using an HDD, a large disk seek would be performed every time a different file is accessed. This value will be 1 for these tests since they only use a single file.
storage.fileDistanceTraveled is an approximation of the absolute distance traveled within files as pages are accessed, in units of 512-byte sectors. For example, if sector 15 in the file is accessed, and then sector 29 is accessed, and then sector 3 is accessed, the distance traveled will be abs(29 – 15) + abs(3 – 29) = 40. In a typical scenario using an HDD, this would approximate the amount of distance that the disk head would have to move. It is an extremely rough approximation, though.
Ideally, as you improve your insert performance, you should see both the total number of accesses and the distance traveled decrease dramatically.
You can try some larger files, also provided in the schemas/insert-perf directory:
ins20k.sql – 20,000 rows of data. With the initial implementation, this file occupies 2.7MB of space, reads 3,306,267 pages, and has a "distance traveled" value of 105,144,752.
ins50k.sql – 50,000 rows of data. With the initial implementation, this file occupies 6.7MB of space, reads 20,645,580 pages, and has a "distance traveled" value of 659,042,640.
ins50k-del.sql – 50,000 rows of data, but also includes a smattering of DELETE statements that remove collections of rows from the table. Try this when you want to see how well you reclaim space! The initial implementation's final result occupies 5MB of space.
You can try these operations simply by piping these files into the nanodb script. For example:
rm datafiles/*
./nanodb < schemas/insert-perf/make-insperf.sql
./nanodb < schemas/insert-perf/ins20k.sqlYou can also generate much larger files if you want to really exercise your work. Note that we have a large insert/delete script that we will run against your database, so it would be advisable for you to exercise your code heavily!
Here are your tasks:
Modify the storage format to improve the insert performance. You can modify the HeapTupleFileManager class in any way that you see fit. You can also modify the HeaderPage and DataPage classes, which do the actual work of reading and writing table pages.
For example, you might want to add a linked-list of blocks with available space to the table-file, anchored from block 0. You might find it easiest to store such a list at the end of each block, but the design is entirely up to you. You could subtract some space from the value that the getTupleDataEnd() method in the DataPage class returns, to open up some extra space for bookkeeping.
You could also create some kind of bitmap that records which blocks have available space. If you do this, your design must still support the maximum number of blocks in NanoDB files, which is 65,536 (64K). Recall that page sizes may vary from 512B to 65,536B; your implementation must work properly regardless of a table’s page size.
Don't forget to update your bookkeeping structures during tuple updates and deletes as well! Even though your primary focus is insert performance, you should make sure that selects (i.e. tuple scans), inserts, updates and deletes all continue to function properly, and that all operations properly include your storage modifications.
Do not use the table statistics as part of your implementation. This is actually not the intended use of table statistics. Table stats are updated infrequently by the database (because this is an expensive operation requiring many disk IOs), and are therefore almost always out of date. Plus, stats-collection is not currently implemented; you will implement this yourself in a future assignment.
When you need to add a new page to a table file, you should be aware that the DBFile class provides a method getNumPages() that returns how many pages are currently in the file. Every DBPage has a reference to the DBFile object that it came from, so it should be very easy to tell where the new page should reside.
Provide detailed documentation of your approach in the class-level comments for the HeapTupleFile.
Additional requirements:
Although you could easily improve performance by simply putting every new tuple in its own data page, you should endeavor to keep your data file to within 3-5% of the size of the original data file. Excessively large data files will be penalized.
Additionally, you must actually modify the storage file format to improve this operation; do not simply modify the in-memory data tracked by the table manager.
Once you are finished with the above tasks, your team needs to complete the design document for this assignment, available in your repository at "doc/lab1design.txt".
When you are ready to submit your code, and your design document includes your team's answers to the design questions, you can fill out this short document and submit it on the course website. Only one teammate should submit this document so that we don't get confused!