Niv Dayan

We will first introduce the course and its logistics. We will then take a deep dive into the topic of how to expand an array data structure when it runs out of space while managing a contention between write and space overheads. We discuss how for a contiguous array, it is desirable for the growth factor to be lower than the golden ratio to allow the memory allocator to reuse deallocated space. We then study how to employ a layer of indirection to overcome the cost contention between write and space costs, and we use CPU tricks to make the indirection layer efficient. The slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_1544d30f3b00476381aafc7800197927.pdf) The lecture video is here.(https://utoronto.zoom.us/rec/share/Q4y6RSPNe5p51P8QSuPg9-UWgH2ZocV7u8HhJiSUwyjSHvvEiQB-GyhSSEPUYdRB.iWZPjEJMFHfTdsHK?startTime=1767816321000) Passcode: ?zPx.PCRp7 Papers covered: Resizable Arrays in Optimal Time and Space. WADS 1999. Additional Resources https://github.com/facebook/folly/blob/main/folly/docs/FBVector.md

We will cover the analysis of Bloom filters from the ground up, and we will exlore recent optimizations to better tailor Bloom filters to modern hardware by making them cache-efficient and and parallel. We'll also cover XOR filters as a more space-efficient counterpart to Bloom filters. We will see how to construct such a filter using "peeling", a general probabalistic technique to assign items to buckets while ensuring low collision probability. The slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_beb1c14bdd8e489da44f23aff7d6bdb2.pdf) The lecture video is here.(https://utoronto.zoom.us/rec/share/ulXrmQfsBvGCXJt_NIRCgxD8yJMKRVuiI4VGy7RvnIBi-Kaf9pGEsHQcBK8DxNnd.14m1vG65Ut-dMmcp) Passcode: 9AEmCVwRR+ Papers covered: Performance-Optimal Filtering: Bloom Overtakes Cuckoo at High Throughput - VLDB 2019 Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters - JEA 2020. Additional Resources For background on Bloom filters, please have a look at the lecture on Bloom filters on week 5 of CSC443 here.(https://www.nivdayan.net/database-system-technology-csc443)

We will then explore Quotient Filters, a recent type of filter that can support dynamic inserts and deletes. We will see how it achieves this by efficiently encoding its state using a small amount of metadata, and how it supports deletes using Robin Hood hashing. Finally, we will see how to efficiently expand a quotient filter using InfiniFilter, a recent advancement that scaling performance and the false positive rate by supporting variable-sized fingerprints within slots. The slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_43c6919ddc1f42a7969784cecb5d229f.pdf) The lecture recording is here.(https://utoronto.zoom.us/rec/share/SOo51WPe0E1qhu5gxq8PFbGSEJQMWFlaMHHGYuGdr9hJx8B1PNymI1nIIBBDxMyk.Y-BWHJI0zpDLDIAb?startTime=1769026020000) Passcode: 0cgVWpq!RF Core Papers Covered: A General-Purpose Counting Filter: Making Every Bit Count - SIGMOD 2017 InfiniFilter: Expanding Filters to Infinity and Beyond - SIGMOD 2023 Optional: Aleph Filter: To Infinity in Constant Time - VLDB 2024

This week we'll explore how to efficiently encode exact sets (a collection of some N entries out of a universe of U keys). We'll do so using Golomb coding to maximize space efficiency. We'll then cover Elias-Fano encoding and how to query this encoding for the existance of an element in constant time using rank and select. The slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_1b76fef27fee430799afd6df3f396c90.pdf) The video recording is here.(https://utoronto.zoom.us/rec/share/vPlYrjuUcxdf8XAJS4I9Sc4NAGTRstQTuIGkJZrc9KjHLGDCMK20bgOITVHz9vBo.KGtuByggy9Iiva-T?startTime=1769631057000) Passcode: =Tt$#dcU=8 Class Reading Golomb Codes An efficient coding scheme for integers. Link (https://experiencestack.co/golomb-codes-d189eba4a64d) Sorted Integers Compression with Elias-Fano Encoding. Link (https://www.antoniomallia.it/sorted-integers-compression-with-elias-fano-encoding.html) Optional Further Reading: Space-Efficient, High-Performance Rank & Select Structures on Uncompressed Bit Sequences. SEA 2013.

The problem we'll look at this week is how to store static sorted variable-length string keys and values in storage. Our case study will be RocksDB, an LSM-tree based database. Though this case study, we'll cover various compression techniques including delta encoding, LZ4, Huffman coding, dictionary training, etc. The slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_0f97cf6b42ab4152a5d343ca0f77769f.pdf) The lecture video is here.(https://utoronto.zoom.us/rec/share/tgrG6gOC1mVEd7BlJDZNA_HTQ8X2qDsZeAgX2By9ZrSrXL1phDMQaxs_hD0THsQB.l-rpQgnpdIDi8ijz?startTime=1770235818000) Passcode: FA7BX4#vAX Background A few of the lectures in CSC443 would serve good background for this lecture. In particular, it would help to watch lecture 1 on storage devices, lecture 2 on page formats (only the second part of the lecture), and lecture 4 on LSM-trees (only a basic understanding of the structure is needed). Reading for Class Optimizing Space Amplification in RocksDB, CIDR 2017.

This week we'll learn about various forms of hashing schemes. The lecture slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_b0722e5045004230a8273f539868a750.pdf) The lecture video is here.(https://utoronto.zoom.us/rec/share/5ZNCANS8Sb3vDwIg5hvwpgJEA0gpU4S4OI_JHaTR01fxv7WF-m89lx1pxccKPgGV.rpb7Lz6D4hrl84jq?startTime=1770840983000) Passcode: qAsh$#n!G7 Reading Fast and Scalable Minimal Perfect Hashing for Massive Key Sets. SEA 2017. The End of Moore’s Law and the Rise of The Data Processor. VLDB 2021.

Catch up on all the reading and start thinking about your project.

This lecture will cover various index data structures for multi-dimensional data. We'll cover topics such as KD-trees, R-trees, and Z-ordering. The slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_608861427986451f873b5b88692de4a1.pdf) The lecture video is here.(https://utoronto.zoom.us/rec/share/FdoBrHAwvbiP6CXgFyf4Lj67OqK6omh7yXu4FSGKfUf9wO9KrdsECBzsV94GTvyq.al4FzQPenIfBL4GN?startTime=1772050472000) Passcode: 2brCM4T=NG Papers Multidimensional Binary Search Trees Used for Associative Searching. Comms of the ACM 1975. R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD 1984. Integrating the UB-Tree into a Database System Kernel. VLDB 2000.

We'll cover classic buffer pool techniques including LRU-K and 2Q. For this lecture, recommended background is lecture 2 on buffer management from CSC443. I also recommend catching up on min-heaps from lecture 6 of CSC443. The slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_bc10977b484740ee8aea1330a9a9125c.pdf) The lecture video is here.(https://utoronto.zoom.us/rec/share/tIi3xW9uS6m_oGQe_IhRvaLTWYwT4n1zDYoKI0CWCQNxE0PEOsRduV9Ns7xuaBSG.MDQGTJPBKgfu4Ufd?startTime=1772655221000) Passcode: 36vs.@Cq4b Lecture papers The LRU-K page replacement algorithm for database disk buffering. SIGMOD Record 1993. 2Q: a low overhead high performance bu er management replacement algorithm. VLDB 1994.

In previous courses, you have learned about balanced binary trees as good methods of indexing data in memory. As we'll see in this lecture, such methods aren't particularly well-optimized for modern CPUs and memory architectures. In this lecture, we'll cover various state-of-the-art in-memory indexes. We'll also cover methods that exploit the data distribution to improve on the worst-case bounds, including interpolation search and learned indexes. The slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_e920ba8cef3e4bd8ba7ef86d6181c543.pdf) The presentation video is here.(https://utoronto.zoom.us/rec/share/-9neVKau3SaDuJ2aQOfk4oFVRnrD5ZfcK8a3kR6qCWb74UdXeabTUoYZXhdQySLM.3Ba7OWfl1CnJxUcf?startTime=1773256284000) Passcode: !PmsjGd1x9 Papers Covered in Lecture A study of index structures for main memory database management systems. 1985. Cache conscious indexing for decision-support in main memory. VLDB 1999. Making B+- trees cache conscious in main memory. SIGMOD 2000 The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases. ICDE 2013. FITing-Tree: A Data-aware Index Structure. SIGMOD 2019. You can find an analysis of interpolation search here.(https://cadmo.ethz.ch/education/lectures/HS18/SAADS/reports/17.pdf)

This week we'll focus on how to achieve fast scans in column-stores via hardware-optimized designs. Recommended background is the lecture on column-stores from CSC443. The lecture slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_9ff40829c35a4f80a824c00617cd8d62.pdf) The lecture video is here.(https://utoronto.zoom.us/rec/share/afhpzlqYVxn3kDrjxk19dxLtvgJKjGpyIquqWMxNPlyqLVtj15zvgFD2b_dlggqF.fJ844ZxhhO8b10n9?startTime=1773861124000) Passcode: 819Kkv&1vm Papers BitWeaving: Fast Scans for Main Memory Data Processing. SIGMOD 2013. Optional Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation. SIGMOD 2018. Rethinking the Encoding of Integers for Scans on Skewed Data. SIGMOD 2024.

Visit by Vast Data Speakers: Moshe Gabel and Vlad Zdornov Title: Exascale LSMs at VAST Data Abstract: The VAST Data Platform (AI OS) is a unified platform for storing, querying, processing, streaming, enriching and indexing all types of structured and unstructured data. It is built on a novel disaggregated architecture (DASE), allowing it to scale to exabytes of capacity while maintaining exceptional performance, reliability and ease of operation. The VAST Data Platform comprises a multi-protocol all-Flash storage solution (VAST DataStore), a transactional, analytical and vector database coupled with an event streaming broker (VAST DataBase) and a pipeline orchestration infrastructure (VAST DataEngine). VAST AI OS now powers some of the world's most demanding workloads: AI training, financial forecasting, high performance scientific computing (including Canada Compute), academic research, and more. This two-part talk will focus on the design and challenges of building the VAST DataBase: an LSM-based database with multi-version concurrency control that supports both analytical as well as vector workloads. Optimized for multi-PB sized tables with trillions of rows and vectors, the VAST DataBase provides high-performance during inserts, query and delete operations – with guaranteed transactional consistency, durability, isolation and availability. We will first briefly present the DASE architecture and the different platform components, focusing on VAST DataStore and VAST DataBase. The main part of the talk will provide a detailed tour of our LSM variant, how it works within the VAST Database, and some of the unique challenges caused by our scale and our unique architecture -- which renders many common approaches infeasible. About the company VAST Data was founded in 2016 and is one of the fastest growing infrastructure companies in history. VAST Data is enabling the AI revolution with industry giants like CoreWeave and xAI being among its customers. The company has more than 1200 employees globally and a growing R&D center in the Toronto area. The Toronto branch operates as a startup-like organization developing the core of the database product and is engaged in the related research activities.      About the speakers Vlad Zdornov has been with VAST Data since 2017, serving in different roles as an early-stage startup developer, architect and VP R&D. He holds a M.Sc.(http://M.Sc) degree in Computer Engineering. Currently, Vlad is leading the VAST Data R&D center in Toronto. Dr. Moshe Gabel joined VAST Data from academia in 2025 as a senior software engineer. Before that, he was a professor of computer science and a researcher at University of Toronto and York University.

This week we'll cover range filters, which can tell whether a whole range of keys is empty or not to allow range queries to skip accessing storage. The lecture slides on intro and SuRF are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_a866116662df467dab33cda0d17dd66f.pdf) The slides on Memento Filter etc are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_76d0b7aea55946fbbdc31d977de1526c.pdf) The lecture video is here.(https://utoronto.zoom.us/rec/share/57QaCPDJG18NVTkQZaXTWhUMrNHE_wtH-x1KmL0GACxnSSbdwyUBq87EFJhX5X2y.3w9ZlIq8sKDAutWA?startTime=1775070855000) Passcode: sJ^5!nwDbr Reading SuRF: Practical Range Query Filtering with Fast Succinct Tries. SIGMOD 2018. Memento Filter: A Fast, Dynamic, and Robust Range Filter. SIGMOD 2025. Diva: Dynamic Range Filter for Var-Length Keys and Queries. VLDB 2025.

We'll first introduce the course and what's to come. Please read Chapter 1 in the textbook. We'll then take a deep look at the memory hierarchy. As we will see throughout the course, the properties of the memory hierarchy give rise to how modern databases are architected. For information on storage, read Chapter 8 Part 8.1, and Chapter 9 Parts 9.1 and 9.2. As you will notice, the textbook was written before SSDs became popular. I have written some background on SSDs here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_a8d4def3b5d94b4f98c2238c064f28b2.pdf) Please study this carefully. This will also be useful when we study circular logs. You may also skim the following article.(https://flashdba.com/2014/09/17/understanding-flash-the-flash-translation-layer/) The intro slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_c8925cfe35a94e0f9e97e4fe3253a579.pdf) The storage slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_20bb30c0b0cd40998cc23b609466cc49.pdf) The intro lecture video is here.(https://utoronto.zoom.us/rec/share/zdauRUBj2rBGMTz26KaVct-_s_GJSx6o5SzVNBgX2ANg1pOk6pnlZMAM_Qus6dT3.eP5JLUZEtqZOnOU_?startTime=1756839862000) Passcode: aX@53KDBN* The slides on RAID are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_b1469eb3b94645839acc974e7a5744eb.pdf) The lecture video on RAID is here.(https://www.youtube.com/watch?v=po-sZrxWemI) Note that this is the video from last year used a backup. There was a glitch with recording the lecture this time, so we are using last year's recording. The material is identical, and there are only minor differences between the slides.

A table in a relational database contains data, but how do we store tables in storage devices such that we can scan them quickly and also insert, update and delete elements efficiently? This week we’ll learn how to efficiently store tables. We’ll also learn how to bring this data in and out of main memory efficiently for processing using buffer management techniques. In the textbook, read all of Chapter 9. The lecture slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_ae1248a1a10d48c1940d0e8af0a7eee8.pdf) The lecture video is here.(https://utoronto.zoom.us/rec/share/TQMA6_bb_-hC1G8TB_ilEbG74HHX5UrYwHV6GD27YOvnoEyPwCy6xMuH-g16gXMX.DvVDpQV0PDaGcRic) Passcode: WpLS*3KF%h The tutorial slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_367a450d26f1406cadcf12276d629bf6.pdf) The tutorial video is here.(https://www.youtube.com/watch?v=3Gvuij4kc8M) Note that we had another glitch in recording, so we are giving you instead the recording of this tutorial from last year. The material is the same.

Some queries only need to access a small amount of data in a given table. To avoid having to scan the entire table, indexes are used to navigate to a given data entry quickly. This week, we'll learn about the numerous indexing options of database systems. There is a lot of textbook reading for this week, so start early. Please read all of Chapter 8 as an introduction to indexing. Chapter 10 will provide an in-depth look at B-trees (you can pay less attention to Part 10.2 as this technology is largely obsolete, though it's still worth reading about to understand how technology evolves). Please also read Chapter 11 Parts 11.1 and 11.2. You are encouraged to read the rest of Chapter 11 as well, but we won't cover it in the course. The slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_687fcc2d198c46f3a255c3057894d52a.pdf) The lecture from section 1 is here.(https://utoronto.zoom.us/rec/share/7_eGb3iUJ5FUMXcxXQHofl4YJH1CrxacUW7q7FUvnvnaDrC5SRb3UDCn9Jbrfh3e.BXsDEvRgthY-b1Y-?startTime=1758049765000) Passcode: 3h?AazaM3! The tutorial questions are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_54b3b590f7964fdaa649c97aa6b02ba5.pdf) The tutorial question & answer slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_a6eb26f5494b4ad78a423835b4497279.pdf) The tutorial video is here.(youtube.com/watch?v=K3fN8Gt0pZ8&feature=youtu.be) We had another recording glitch, so this video is from last year. The questions & answers are identical, though there are a few insignificant differences in wording and aesthetics.

Traditional indexing techniques are optimized for reading but slow at ingesting new data. This week, we'll examine other types of database indexes used to optimize for data ingestion. Write-optimized indexes became popular over the past 15 years, so they do not appear in your textbook. Please read sections 1, 2, and 3 in the following: https://nivdayan.github.io/monkeykeyvaluestore.pdf (https://nivdayan.github.io/monkeykeyvaluestore.pdf) The lecture slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_c65e7d3f56ce42e9853180c15ad224fe.pdf) The lecture video is here.(https://utoronto.zoom.us/rec/share/RyfIIsLeI7MRn738RFe74AxmRC9XVopViLygyptVTVdRNJt6k4WDY_dGuzgFCgRr.gCxnx44jTeKXH1Ao?startTime=1758654481000) Passcode: #R7D7hhh=k The tutorial question slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_137606f1f584463cafa5690e541d4b73.pdf) The tutorial question and answers are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_b26d083dc3f1418ebeec5eb5216e4515.pdf) The tutorial video is here.(https://utoronto.zoom.us/rec/share/_Z6MMnSbABL4Qs7WEx5-KfM8XGmOaHP1i_B9B7gt6zG8RW-77YfzVJCfn_6Sd7eP.e-DiTuA5mTSWaBAf) Passcode: 0.Lc=S1@Qx

We will begin this lecture by studying Bloom filters and their use in storage systems - especially with LSM-trees. We will then have a one hour research lecture covering advanced topics the co-optimization of LSM-trees and Bloom filters. Required reading: Section 1 in: https://www.eecs.harvard.edu/~michaelm/postscripts/tempim3.pdf (https://www.eecs.harvard.edu/~michaelm/postscripts/tempim3.pdf)(you may also skim section 2 for the mathematical analysis) Sections 1-4 in https://nivdayan.github.io/monkeykeyvaluestore.pdf (https://nivdayan.github.io/monkeykeyvaluestore.pdf) Sections 1-4 in: https://nivdayan.github.io/dostoevsky.pdf (https://nivdayan.github.io/dostoevsky.pdf) If you find this material to be interesting, you are also welcome to read the following papers, though we won't cover them in the course. https://nivdayan.github.io/LSM-bush.pdf (https://nivdayan.github.io/LSM-bush.pdf) https://nivdayan.github.io/chucky.pdf (https://nivdayan.github.io/chucky.pdf) https://nivdayan.github.io/spooky.pdf (https://nivdayan.github.io/spooky.pdf) The lecture slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_4344ad6e977441c6b7e29e379ff0ed19.pdf) The lecture video is here.(https://utoronto.zoom.us/rec/share/SGcmeo3h2Nq9_57K_2OCQTlf9Xsgf4ZKnLTtgOk98fnaSgF1tvWu1HL3appVvXNX.ZB5OTL3PH4AMo5z4?startTime=1759270484000) Passcode: e#6L+1@.1a The tutorial questions are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_663d4307380a4bb6840745b8bcf53432.pdf) The tutorial answers are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_8e11c91930cf4a0aabbe2ebfd17694e8.pdf) Please only look after class.

Sorting is a basic operation in database systems to construct indices or return sorted output for queries. You've probably encountered sorting algorithms like merge-sort and quick-sort in the past. However, it turns out these algorithms are no longer the best choice when most of our data reside in storage. This week, we'll learn about multi-way sort-merge, a sorting algorithm for vast amounts of data. Read Chapter 13 in the textbook. The lecture slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_ae71878c62294232a7b0acd9ad4cc5a6.pdf) The lecture video is here.(https://utoronto.zoom.us/rec/share/5OGQJRHXfGUKfDtC2XYAxDvGS2wYQcM_pOaldp5YWyiywU7OJOc0o2R57CT-JPb4.L1qxEuDfwY8dUGT6?startTime=1759864222000) Passcode: p8YjL^J1C2 The tutorial questions are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_6e2cbd9eb0e2478eb17c87ab03d75f93.pdf) The tutorial slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_50af8f63a51e4ac88b6581c8f3dd0def.pdf) The tutorial video is here.(https://utoronto.zoom.us/rec/share/upnpodXLg4tiSELWJtgSqqjdSXCKz3t5eCnChyR4Hd5-ayXM4Af6TablD1eyf9Xa.scBL29NIhPqH8zZ7?startTime=1760037066000) Passcode: Z*v4dddj+Z

The midterm is taking place on Oct 14th. It takes two hours. It will cover all the material covered so far in the course. Be prepared and ask for help if you need it! In the tutorial session on Oct 16, we will go through the answers in person.

This week, we'll take a deeper look at how queries in a relational database are executed and planned. Please read Chapters 12, 14 and 15 in the textbook. The slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_c7ae7caefe9045f2bf6a72cb23ab695a.pdf) The lecture video is here.(https://utoronto.zoom.us/rec/share/tKKpXQh7rETtJQBN5GvFiY0pz6EsXAs7aWO97OAuIu8FIWc5vsX07sM7_eeUeHEt.54CYzUX4C7AXJf25?startTime=1761084924000) Passcode: X*ZS&U5.am (X*ZS&U5.am) The tutorial video is here.(https://utoronto.zoom.us/rec/share/jeoTORzDRZLisK48PUhjaXQjvRsN9fjq1zsyjFwjJL2iGhkA5qSxiqb19FyBm_rW.D0edg5pz6NPQg4fw?startTime=1761246639000) Passcode: qZr1.WPtf. The tutorial slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_696282a1ab83430885397f6a52c85571.pdf)

A good time to finish up the project :)

While traditional databases store data in each table row by row, a newer breed of databases is storing the data column by column to optimize more for analytical queries and statistical calculations. This week, we'll learn about column-stores, the cornerstone of modern data warehousing. As Column-Stores rose to prominence over the past 15 years, they do not appear in your textbook. Therefore, please have a look at "The Design and Implementation of Modern Column-Oriented Database Systems" by Abadi et al: https://stratos.seas.harvard.edu/files/stratos/files/columnstoresfntdbs.pdf (https://stratos.seas.harvard.edu/files/stratos/files/columnstoresfntdbs.pdf) Read Parts 1, 2, 3, 4.1, 4.2, 4.3, 4.4, 4.7, 4.8, and 5. The slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_23900d33f8d24ae19c643e763c9c9f40.pdf) The lecture video is here.(https://utoronto.zoom.us/rec/share/byKhVkiXT0z9JY4zLMfc_QkpYmtac7aTN1--2nMFJbjSGJ2jBfYl77meiqbsLOxb.op2rK1osDHUO9s6F?startTime=1762286969000) Passcode: yM^uw!my7D The tutorial questions are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_0b9bb89de6ec45bf91ca3742a5ad5585.pdf) The tutorial questions and answers are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_aa81134cb7e44b06acbd2bcc15181bac.pdf) The tutorial video is here.(https://utoronto.zoom.us/rec/share/oi0O4Tv1_nAYXvpYsFEbedWT1Xeq7Z1x39Dlw40nUgchUT4-0iHfO4yPYqgB-3g7.Kw1OftcPQ5FMLFw-?startTime=1762459700000) Passcode: Nxzi@4M#y%

This week, we'll take a look at an emerging KV-stores paradigm that involves logging data in storage and indexing it from memory. We’ll study how to implement this index efficiently using Cuckoo hashing and Cuckoo filters. We’ll also examine the importance of separating hot and cold data to lower garbage-collection overheads, and we’ll introduce the count-min sketch to help us achieve this. We will also discuss how to recover the index when power fails. First, have a look at Bitcask,(https://riak.com/assets/bitcask-intro.pdf) a very simple and easy to understand KV-store that indexes the full keys of data entries in storage Then, have a look at Cuckoo hashing,(https://www.itu.dk/people/pagh/papers/cuckoo-undergrad.pdf) a hash table design that’s able to achieve very good hash table utilization and CPU efficiency at the same time. Then, read up on Cuckoo filters,(https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf) which store fingerprints rather than full keys within a cuckoo hash table to further reduce memory requirements. The wikipedia articles on these topics are also recommended. Finally, have a look at FlashStore,(https://dl.acm.org/doi/10.14778/1920841.1921015) a more memory-efficient KV-strore design than bitcask that stores fingerprints rather than full keys in memory and employs a Cuckoo filter variant to index them (since Cuckoo filters had still not been invented at the time). Two KV-stores out in the wild that employ this paradigm are FASTER (https://microsoft.github.io/FASTER/)and ForestDB.(https://dbdb.io/db/forestdb) Feel free to browse them. The notion of hot/cold data identification and separation has been explored more in the context of SSDs and flash translation layers. The following paper,( https://dl.acm.org/doi/abs/10.1145/1138041.1138043) for instance, employs a similar construction to count-min.(https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch) The lecture slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_84b2eeef1df148308135ce4acb7554d5.pdf) The lecture video is here.(https://utoronto.zoom.us/rec/share/zxZf6EBYDOQSH2RqxFAHWkJXiQiBRiRlmh3GlADloMEbKgcqcB06NeT7-dDTmI_y.ZWh-xv0805tr9-JQ?startTime=1762891786000) Passcode: kyqaWJU4^y The tutorial questions are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_61def25b412d4bc1bd9aa09201158fad.pdf) The tutorial video is here.(https://utoronto.zoom.us/rec/share/gO97tsaKzTRXvMCg3bFvfXY5gc5EoY7SgaD0w9WLP1l_uK-pfUMYPeZ0feO1YZto.1fdVOsICQOvyp9St?startTime=1763064666000) Passcode: MJ@3WO+5ZU The tutorial slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_0b969ac9cccd49948c4cd78d9ae25a9a.pdf)

We'll introduce Transaction Management and Concurrency Control this week, the part of the database that ensures different operations can execute in parallel yet correctly, even if the system might fail at any moment. Please read Chapters 16 and 17 in the textbook. The lecture slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_87b96b632049491fbb789c3abf64a189.pdf) The lecture video is here.(https://utoronto.zoom.us/rec/share/7OH0M_pqF0L1tquv1XuFuxf241G0SjbaB7ouajStX68C2j75uUrY_x21ZO7cW56f.H3rmbtww6v-sTxFf?startTime=1763496555000) Passcode: QE79a&J%ox The tutorial slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_29b6473c2d8f40c78e7ce6a12cadca4b.pdf) The tutorial video is here.(https://drive.google.com/file/d/12sxae1z57OwuzztTNUzYnP5XToaZ2OIG/view)

This week, we'll look at how to recover the database into a consistent state if, say, power suddenly fails. Please read Chapter 18 in the textbook. The lecture slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_1d3715c8699744adb24f2464bb0e9a4e.pdf) The lecture video is here.(https://utoronto.zoom.us/rec/share/WPBqsXdxI2OhGaSLU9k1YtotSdFwMi-UajK2eF36ff-azZU4FHfrS1AJ82jIbI4.CcyHXyHsPBisVCe2?startTime=1764101665000) Passcode: @Ef^km5XeT The tutorial slides are here.(https://6c7de8b5-df3d-4a03-945a-9846af236553.usrfiles.com/ugd/6c7de8_b86bd51f30214c7983021be12d1e0849.pdf)