Database Storage Engines: Write Optimized Indices and Hashing

Write Optimized Indices

  • Performance of B+-trees can be poor for write-intensive workloads.
    • One I/O per leaf, assuming all internal nodes are in memory.
    • With magnetic disks, < 100 inserts per second per disk.
    • With flash memory, one page overwrite per insert.
  • Two approaches to reducing the cost of writes:
    • Log-structured merge tree (LSM tree).
    • Buffer tree.

Log Structured Merge (LSM) Tree

  • Consider only insert/queries for now.
  • Records are initially inserted into an in-memory tree (L0 tree).
  • When the in-memory tree is full, records are moved to disk (L1 tree).
    • A B+-tree is constructed using a bottom-up build by merging the existing L1 tree with records from the L0 tree.
  • When the L1 tree exceeds a certain threshold, it is merged into the L2 tree.
  • This process continues for more levels.
  • The size threshold for L<em>i+1L<em>{i+1} tree is kk times the size threshold for the L</em>iL</em>i tree.
  • Deletion is handled by adding special “delete” entries.
    • Lookups will find both the original entry and the delete entry, and must return only those entries that do not have a matching delete entry.
    • When trees are merged, if a delete entry matches an original entry, both are dropped.
  • Updates are handled using insert + delete.
  • LSM trees were initially introduced for disk-based indices but are also useful for minimizing erases with flash-based indices.
  • The stepped-merge variant of LSM trees is used in many BigData storage systems:
    • Google BigTable, Apache Cassandra, MongoDB.
    • More recently in SQLite4, LevelDB, and MyRocks storage engine of MySQL.

Benefits of LSM Approach

  • Inserts are done using only sequential I/O operations.
  • Leaves are full, avoiding space wastage.
  • Reduced number of I/O operations per record inserted compared to a normal B+-tree (up to some size).

Drawbacks of LSM Approach

  • Queries have to search multiple trees.
  • The entire content of each level is copied multiple times.

Stepped Merge Index

  • Stepped-merge index: A variant of the LSM tree with kk trees at each level on disk.
    • When all kk indices exist at a level, they are merged into one index of the next level.
    • This reduces write cost compared to the LSM tree.
    • However, queries are more expensive since many trees need to be queried.
  • Optimization for point lookups:
    • Compute a Bloom filter for each tree and store it in-memory.
    • Query a tree only if the Bloom filter returns a positive result.

Bloom Filters

  • A Bloom filter is a probabilistic data structure used to check the membership of a value in a set.
    • It may return true (with a low probability) even if an element is not present.
    • But it never returns false if an element is present.
    • Used to filter out irrelevant sets.
  • The key data structure is a single bitmap.
    • For a set with nn elements, a typical bitmap size is 10n10n.
  • Uses multiple independent hash functions.
    • With a single hash function h()h() with range = number of bits in bitmap:
      • For each element ss in set SS, compute h(s)h(s) and set bit h(s)h(s).
      • To query an element vv, compute h(v)h(v), and check if bit h(v)h(v) is set.
    • Problem with a single hash function: significant chance of false positive due to hash collision.
      • 10% chance with 10n10n bits.
  • Key idea: reduce false positives by using multiple hash functions hi()h_i() for i=1..ki = 1..k.
    • For each element ss in set SS, for each ii, compute h<em>i(s)h<em>i(s) and set bit h</em>i(s)h</em>i(s).
    • To query an element vv, for each ii, compute h<em>i(v)h<em>i(v), and check if bit h</em>i(v)h</em>i(v) is set.
    • If bit hi(v)h_i(v) is set for every ii, then report vv as present in the set.
    • Else report vv as absent.
    • With 10n10n bits and k=7k = 7, the false positive rate reduces to 1% instead of 10% with k=1k = 1.

Buffer Tree

  • Alternative to the LSM tree.
  • Key idea: each internal node of the B+-tree has a buffer to store inserts.
    • Inserts are moved to lower levels when the buffer is full.
    • With a large buffer, many records are moved to a lower level each time.
    • Per record I/O decreases correspondingly.

Benefits

  • Less overhead on queries.
  • Can be used with any tree index structure.
  • Used in PostgreSQL Generalized Search Tree (GiST) indices.

Drawback

  • More random I/O than LSM tree.

Hashing

  • A hash table implements an unordered associative array that maps keys to values.
  • It uses a hash function to compute an offset into this array for a given key, from which the desired value can be found.
  • Space Complexity: O(n)O(n)
  • Time Complexity:
    • Average: O(1)O(1)
    • Worst: O(n)O(n)

Hash Functions

  • For any input key, return an integer representation of that key.
  • Aim: Fast and low collision rate.
    • CRC-64 (1975): Used in networking for error detection.
    • MurmurHash (2008): Designed as a fast, general-purpose hash function.
    • Google CityHash (2011): Designed to be faster for short keys (<64 bytes).
    • Facebook XXHash (2012): From the creator of zstd compression.
    • Google FarmHash (2014): Newer version of CityHash with better collision rates.

Hash Table

  • Assumptions:
    • The number of elements is known ahead of time and fixed.
    • Each key is unique.

Resolve Collisions: Linear Probe

  • A single giant table of fixed-length slots.
  • Resolve collisions by linearly searching for the next free slot in the table.
    • To determine whether an element is present, hash to a location in the table and scan for it.
    • Store keys in the table to know when to stop scanning.
    • Insertions and deletions are generalizations of lookups.
  • The table's load factor determines when it is becoming too full and should be resized.
    • Allocate a new table twice as large and rehash entries.

Resolve Collisions: Chaining

  • Bucket overflow can occur because of:
    • Insufficient buckets
    • Skew in the distribution of records. This can occur due to two reasons:
      • Multiple records have the same search-key value
      • The chosen hash function produces a non-uniform distribution of key values
  • Although the probability of bucket overflow can be reduced, it cannot be eliminated; it is handled by using chaining overflow buckets.
  • Overflow chaining – the overflow buckets of a given bucket are chained together in a linked list.

Deficiencies of Static Hashing

  • In static hashing, the function hh maps search-key values to a fixed set BB of bucket addresses. Databases grow or shrink with time.
    • If the initial number of buckets is too small, and the file grows, performance will degrade due to too many overflows.
    • If space is allocated for anticipated growth, a significant amount of space will be wasted initially (and buckets will be underfull).
    • If the database shrinks, again space will be wasted.
  • One solution: periodic re-organization of the file with a new hash function
    • Expensive, disrupts normal operations
  • Better solution: allow the number of buckets to be modified dynamically.

Dynamic Hashing

  • Periodic rehashing
    • If the number of entries in a hash table becomes (say) 1.5 times the size of the hash table,
      • create a new hash table of size (say) 2 times the size of the previous hash table
      • Rehash all entries to the new table
  • Linear Hashing
    • Do rehashing in an incremental manner
  • Extendible Hashing
    • Tailored to disk-based hashing, with buckets shared by multiple hash values
    • Doubling of # of entries in hash table, without doubling # of buckets

Extendible Hashing

  • Extendable hashing – one form of dynamic hashing
    • Hash function generates values over a large range — typically b-bit integers, with b=32b = 32.
    • At any time, use only a prefix of the hash function to index into a table of bucket addresses.
    • Let the length of the prefix be ii bits, 0≤i≤320 \leq i \leq 32.
    • Bucket address table size = 2i2^i.
    • Initially i=0i = 0
    • The value of ii grows and shrinks as the size of the database grows and shrinks.
    • Multiple entries in the bucket address table may point to the same bucket.
    • Thus, the actual number of buckets is < 2i2^i
    • The number of buckets also changes dynamically due to coalescing and splitting of buckets.
Use of Extendable Hash Structure
  • Each bucket j stores a value iji_j
    • All the entries that point to the same bucket have the same values on the first iji_j bits.
  • To locate the bucket containing search-key KjK_j,
    1. Compute h(Kj)=Xh(K_j) = X
    2. Use the first ii high-order bits of XX as a displacement into the bucket address table, and follow the pointer to the appropriate bucket
  • To insert a record with search-key value KjK_j,
    • Follow the same procedure as look-up and locate the bucket, say jj.
    • If there is room in the bucket jj, insert the record in the bucket.
    • Else the bucket must be split and insertion re-attempted
Insertion in Extendable Hash Structure (Cont.)
  • If i>iji > i_j (more than one pointer to bucket jj)
    • allocate a new bucket zz, and set i<em>j=i</em>z=(ij+1)i<em>j = i</em>z = (i_j + 1)
    • Update the second half of the bucket address table entries originally pointing to jj, to point to zz
    • remove each record in bucket jj and reinsert (in jj or zz)
    • recompute the new bucket for KjK_j and insert record in the bucket (further splitting is required if the bucket is still full)
  • If i=iji = i_j (only one pointer to bucket jj)
    • If ii reaches some limit bb, or too many splits have happened in this insertion, create an overflow bucket
    • Else
      • increment ii and double the size of the bucket address table.
      • replace each entry in the table by two entries that point to the same bucket.
      • recompute a new bucket address table entry for KjK_j
  • Now i>iji > i_j so use the first case above.
To split a bucket jj when inserting a record with search-key value KjK_j,
  • If i>iji > i_j (more than one pointer to bucket jj)
    • allocate a new bucket zz, and set i<em>j=i</em>z=(ij+1)i<em>j = i</em>z = (i_j + 1)
    • Update the second half of the bucket address table entries originally pointing to jj, to point to zz
    • remove each record in bucket jj and reinsert (in jj or zz)
    • recompute a new bucket for KjK_j and insert record in the bucket (further splitting is required if the bucket is still full)
  • If i=iji = i_j (only one pointer to bucket jj)
    • If ii reaches some limit bb, or too many splits have happened in this insertion, create an overflow bucket
    • Else
      • increment ii and double the size of the bucket address table.
      • replace each entry in the table by two entries that point to the same bucket.
      • recompute a new bucket address table entry for KjK_j
    • Now i>iji > i_j so use the first case above.
Deletion in Extendable Hash Structure
  • To delete a key value,
    • locate it in its bucket and remove it.
    • The bucket itself can be removed if it becomes empty (with appropriate updates to the bucket address table).
    • Coalescing of buckets can be done (can coalesce only with a “buddy” bucket having the same value of i<em>ji<em>j and same i</em>j–1i</em>j –1 prefix, if it is present)
    • Decreasing bucket address table size is also possible Note: decreasing bucket address table size is an expensive operation and should be done only if the number of buckets becomes much smaller than the size of the table

Extendable Hashing vs. Other Schemes

  • Benefits of extendable hashing:
    • Hash performance does not degrade with the growth of the file
    • Minimal space overhead
  • Disadvantages of extendable hashing
    • An extra level of indirection to find the desired record
    • The bucket address table may itself become very big (larger than memory)
    • Cannot allocate very large contiguous areas on disk either
    • Solution: B+-tree structure to locate desired record in the bucket address table
    • Changing the size of the bucket address table is an expensive operation
  • Linear hashing is an alternative mechanism
    • Allows incremental growth of its directory (equivalent to bucket address table)
    • At the cost of more bucket overflows

Trie Index

  • Use a digital representation of keys to examine prefixes one-by-one.
  • Also known as Digital Search Tree, Prefix Tree.
  • The shape depends on keys and lengths.
  • Does not depend on existing keys or insertion order.
  • Does not require rebalancing operations.
  • All operations have O(k)O(k) complexity where kk is the length of the key.
  • The path to a leaf node represents a key.
  • Keys are stored implicitly and can be reconstructed from paths.

Radix Tree

  • Vertically compressed trie that compacts nodes with a single child.
  • Also known as Patricia Tree.
  • Can produce false positives, so the DBMS always checks the original tuple to see whether a key matches.

String Index

  • Suppose you have to create a B+-tree index on a large number of names, where the maximum size of a name may be quite large (say 40 characters) and the average name is itself large (say 10 characters). Explain how prefix compression can be used to maximize the average fanout of non-leaf nodes.
  • Variable length strings as keys
    • Variable fanout
    • Use space utilization as a criterion for splitting, not the number of pointers
  • Prefix compression
    • Key values at internal nodes can be prefixes of the full key
      • Keep enough characters to distinguish entries in the subtrees separated by the key value
      • E.g., “Silas” and “Silberschatz” can be separated by “Silb”
    • Keys in the leaf node can be compressed by sharing common prefixes

Spatial Index

  • Databases can store data types such as lines, polygons, in addition to raster images
    • allows relational databases to store and retrieve spatial information
    • queries can use spatial conditions (e.g. contains or overlaps).
    • queries can mix spatial and nonspatial conditions
  • Nearest neighbor queries: given a point or an object, find the nearest object that satisfies given conditions.
  • Range queries: deal with spatial regions. e.g., ask for objects that lie partially or fully inside a specified region.
  • Queries that compute intersections or unions of regions.
  • Spatial join of two spatial relations with the location playing the role of join attribute.

Indexing of Spatial Data

  • k-d tree - early structure used for indexing in multiple dimensions.
    • Each level of a k-d tree partitions the space into two.
      • Choose one dimension for partitioning at the root level of the tree.
      • Choose another dimension for partitioning in nodes at the next level and so on, cycling through the dimensions.
    • In each node, approximately half of the points stored in the sub-tree fall on one side and half on the other.
    • Partitioning stops when a node has less than a given number of points.
    • The k-d-B tree extends the k-d tree to allow multiple child nodes for each internal node; well-suited for secondary storage.

Division of Space by Quadtrees

  • Each node of a quadtree is associated with a rectangular region of space; the top node is associated with the entire target space.
  • Each non-leaf node divides its region into four equal-sized quadrants
    • correspondingly each such node has four child nodes corresponding to the four quadrants and so on
  • Leaf nodes have between zero and some fixed maximum number of points (set to 1 in the example).

R-Trees

  • R-trees are an N-dimensional extension of B+-trees, useful for indexing sets of rectangles and other polygons.
  • Supported in many modern database systems, along with variants like R+-trees and R*-trees.
  • Basic idea: generalize the notion of a one-dimensional interval associated with each B+-tree node to an N-dimensional interval, that is, an N-dimensional rectangle.
  • Will consider only the two-dimensional case (N = 2)
    • generalization for N > 2 is straightforward, although R-trees work well only for relatively small N
  • The bounding box of a node is a minimum-sized rectangle that contains all the rectangles/polygons associated with the node
    • Bounding boxes of children of a node are allowed to overlap

Search in R-Trees

  • To find data items intersecting a given query point/region, do the following, starting from the root node:
    • If the node is a leaf node, output the data items whose keys intersect the given query point/region.
    • Else, for each child of the current node whose bounding box intersects the query point/region, recursively search the child
    • Can be very inefficient in the worst case since multiple paths may need to be searched, but works acceptably in practice.

Nearest Neighbor Search: Representation Learning

  • Objects => High dimensional feature vectors
  • Texts, documents, images, video, audio, graphs word2vec, doc2vec CLIP node2vec, graph2vec item2vec, user2vec

Hierarchical Navigable Small World (HNSW) graph Approximate Nearest Neighbor Search (ANNS)

  • Finding the exact nearest neighbors is hard due to the “curse of dimensionality”.
  • Approximate nearest neighbor search is critical in many applications.
    • Vector databases, Retrieval Augmented Generation (RAG), image retrieval, etc.

Data Warehouse

  • ETL: Extract Transform Load.
  • Vendors: Expensive
    1. Teradata
    2. Vertica
    3. SAP HANA
    4. ParAccel
    5. RedShift (Amazon)
  • Open Source
    • Apache Hive
    • Spark SQL
    • Cloudera Impala
    • Presto (Facebook)
    • Apache Tajo and Drill

Schemas for Analytics: Stars and Snowflakes

  • Star schema.
    • Fact table: records for individual events recording who, when, where, why and how of the event, typically 100+ columns.
      • Column: An attribute or A foreign key to a dimension table
    • Dimension table: a smaller table on one attribute, can also be wide.

Storage and Retrieval

  • Typical Query: Aggregate over all rows, only relate to a few columns.
  • For fact table with trillions of rows and hundreds of columns, column store is popular.

Storage and Retrieval: Column Store

  • Bit operation. AND, OR, XOR. A batch of 64 bits can be computed in one operation.
  • Bitmap encoding. WHERE product_sk IN (30,68,69):
    • Load the bitmaps of productsk= 30 productsk= 68 and product_sk= 69, and
    • Calculate the bitwise OR.
  • Further optimization.
    • Vectorized processing on Single-Instruction-Multi-Data (SIMD)
    • Sort the data in multiple orders for RAID Fast query processing Concurrency

Storage and Retrieval: Aggregation

  • Cross-tabulation (cross-tab, pivot-table).
    • Values for one of the dimension attributes form the row headers
    • Values for another dimension attribute form the column headers
    • Other dimension attributes are listed on top
    • Values in individual cells are (aggregates of) the values of the dimension attributes that specify the cell.
  • Data Cube.
    • A data cube is a multidimensional generalization of a cross-tab
    • Can have n dimensions; we show 3 above
    • Cross-tabs can be used as views on a data cube