Datenbanksysteme und moderne CPU-Architekturen Flashcards part 2

1. start on the root node
2. look for the first entry ≥ search key
   1. if found entry = search key, return entry
   2. if no entry ≥ search key found, follow to the right-end pointer
   3. else go to the pointer before the first entry > search key (first entry serves as upper limit)
3. repeat step 2 until entry found or determined that entry is not in search tree

1. lookup leaf node where value should be inserted
   1. if there is free space on the leaf, insert and end
2. split the leaf in two, and insert the value to the proper side
3. insert maximum of the left page as separator into the parent node
   1. if parent had enough space, end
   2. else repeat step2 and 3 until B+ Tree properties are satisfied (create a new root node if needed)

1. lookup leaf node of the value
2. remove entry
   1. if leaf node is at least half full (it has at least ⌈m/2⌉ children), end
   2. else if neighboring page is more than half full, balance the pages and end
3. merge neighboring node into current node
4. remove the separator entry between the two node in the parent node
5. if necessary, repeat from step 2.1 until B+ Tree properties are satisfied

1. lookup the start value
2. start enumerating on the pointers of the node
3. stop when stop value is reached

compound keys are compared lexicographically:

(a_1, a_2) < (b_1, b_2) ⇔ (a_1 < b_1) ∨ (a_1 = b_1 ∧ a_2 < b_2)

(and so on with larger keys)

if all attributes of the compund key are bound, it's the same as atomic keys

otherwise, the unbound properties are specified as range between −∞ and ∞ (so they can have any value)

index on the value but also secretly index on the tupleID, so when value is equal the tupleID can be compared.

this guarantees O(logn) access

if condition value == c is only true for a maximum of 10% of the entries for any given c constant (otherwise linear read is faster)

a lock holds for the whole transaction, while a latch only holds for a short period of time

classical technique for locking multiple pages in a B+ Tree

first latch the root, latch the first level, release root, latch second level, release first level, ...

extension on the lock coupling technique, ensures that we can insert without deadlocks

when traversing down the tree, check for every node if the node would have enough space for one more entry. If not, split it.

However, doesn't work for variable-length keys (strings)

alternative extension on the lock coupling technique, ensures that we can insert without deadlocks but also works with variable-length keys

first naively try to insert using simple lock coupling. If fails (we need to split a node), restart the operation from root, but this time don't release any of the latches

B+ Tree but every inner node is also connected via next pointer (not just the leaf nodes)

using this variation, we can do a lookup with only latching the appropriate child page (because even if it has been split during our lookup, we can use the next pointer to get to the other half of the split)

build-up technique for B+ Trees for large amounts of data

1. sort the data
2. spool data into fully filled leaf nodes
   1. save largest value of the node separately, as it will work as separator
3. spool the separators into inner nodes
4. repeat step 3 until only 1 node remains, which will be the root node

problem: bulk operations make the B-Tree offline

solution: partition the B-Tree into columns, and only load into the right-most column

• rest of the tree and the index stays online
• partitions can be merged laziliy when benefitial
• but lookups have to access all partitions, because global order only exists inside the partitions

technique to optimize space consumption on B+Trees with variable-length keys.

Instead of storing the complete keys in each node, only the differing parts of the keys are stored, along with a common prefix for the keys in that node.

Such B+Trees have their data usually lexicographically sorted

• promises O(1) lookup
• good in memory, but bad on disks because it uses random I/O
• growth means rehashing (which is a problem)
• only supports value search, no range search
• keys must be unique, or the hash entry must point to a tree

technique to allow hash-table growth on the disk without rehashing

1. we first use 1 bit as hash-index, and both of its values point to the same bucket
2. when adding a new value
   1. if there is space in the bucket, add to the bucket
   2. else create a new bucket, and use the other value of the hash-index bit to access it (table size doubles)
3. do this until both buckets are full
4. add a new bit to the hash-index (which now consists of 2 bits) (table size doubles), and use the new values of the hash-index to create new buckets
5. if hash-table reaches maximum size, start chaining the buckets

• existing buckets are not disturbed and doesn't need rehashing
• but table grows exponentially 

extendible hashing, but instead of adding a new bit to the whole table, only add 1 bit to 1 index entry on demand (e.g. there is the table entries 0 and 1, we only add 1 more bit to entry 0 so now we have entries 00, 10 and 1)

• index grows linearly
• but still includes chaining. Also, how do you even implement this? (quoted from the prof.)

dynamic hashing technique for large datasets. Minimizes collision.

creates a tree-like structure of hash tables:

• in the root there is a directory (usually an array of pointers)
• each pointer of the directory points to a bucket that stores key-value pairs (effectively each bucket is a hash table)
• the keys are distributed between these buckets (tables)
• at insertion, if the destination bucket is full, a new bit starts being used to index buckets on that level, effectively doubling the number of buckets of that level
  • if all the buckets are full, the directory needs to be expanded, by using one more bit in the index

problem: when uniformly filled, there will be a point where each bucket has just been split, so we have a lot of 2nd level tables with only a few entries.

solution: share the inner page between buddies (pointers to the same page) and undo split if at specific buckets if all pointers of the bucket point to the same value

indexing technique for small domains where only a combination of attributes is selective

create a bitmap for every possible value of a given attribute, where a tuple has bit 1 if its value of that attribute is that signed by the bitmap (e.g. create a bitmap for a=5, here every tuple where a is actually 5 will have bit 1, the others bit 0)

makes queries answerable by simple bit-operations

bitmaps are also sparse and contain only 1 bit per tuple, so they can be well compressed

some data chunks rarely change (the old static chunks), so we can calculate frequent aggregates on them (like min, max, count, sum, ...) and answer queries using only the aggregates

• begin of transation (often implicit)
• commit: terminates successfully, all changes permanent
• abort: terminates unsuccessfully, changes get undone
• read data item
• write data item

properties all transactions should adhere to

• Atomicity: transactions are either executed completely or not at all
  • in concept of recovery: all in-flight transaction must be rolled back
• Consistency: transactions bring the DB form one consistent state into another
• Isolation: transactions can run unaware ("isolated") from one another, concurrently
• Durability: changes made by transactions are never lost
  • in concept of recovery: all data must be saved, even if it's in transient memory

problem between 2 concurrent transactions if not run as serializable

happens if T1 writes x and T2 also writes x before T1 commits (T1's changes are now gone)

problem between 2 concurrent transactions if not run as serializable

happens if T1 writes x, after this T2 reads x, but T1 actually aborts at the end (T2 read a false value)

problem between 2 concurrent transactions if not run as serializable

happens if T1 works with x multiple times during its run, and T2 writes x while T1 is running (T1 now read 2 different values for x)

problem between 2 concurrent transactions if not run as serializable

happens if T1 works with all tuples of relation R during its run, but T2 inserts a new tuple into R while T1 is running (T1 now reads a new tuple during second access)

solution: add a lock for the "next" pseudo-tuple. Scans lock it shared, inserts lock it exclusive and apply trick to enable concurrent inserts.

transaction Ti is a partial order of operations, where

• Ti ⊆ {ri[x],wi[x] | x is a data item} ∪{ai,ci}
  • all operations in a transaction are either data reads, data writes, aborts or commits
• ai ∈Ti,iff ci ̸∈Ti
  • a transaction only aborts if and only if it doesn't commit
• Let t be ai or ci. Then for all other operations pi: pi <i ti
  • every operation must be before the commit or abort
• If ri[x] ∈ Ti and wi[x] ∈ Ti, then either ri[x] <i wi[x] or wi[x] <i ri[x]
  • in a transaction concerning data x, either all reads must come before writes, or the other way around

partial ordering over the operations of a set of the transactions made by the scheduler

a schedule shall contain all operations of the contained transactions, operation order in any given transaction shall remain the same, and conflicting operations shall not be executed concurrently

operations of two transactions are in conflict if they both operate on the same data and at least one of them is write

conflicting operations must not be executed in parallel

Two schedules are conflict equivalent if they contain the same transactions and they order the conflicting operations of those transactions the same way

in other words, they always yield the same result

a schedule is serializable, if there exists a serial (not concurrent, every transaction runs after one another) schedule, which yields the same committed transactions and end-results as the schedule (their comitted projections are equal)

a serializable schedule's serializability graph must be acyclic

a directed graph where the nodes are comitted transactions, and there is a directed edge between T1 and T2 if they have conflicting operations p_1∈ T1 and q_1∈T2 where p_1 is ordered before q_1 in the schedule

a schedule is recoverable if for all T1 T2 transaction pairs in the schedule: if T1 reads value x after that x is written by T2 and T1 commits, then T2 must commit before T1

(transactions must adhere to a certain commit order)

example: w1[x] r2[x] w2[y] c2 a1 is not recoverable

can happen if T1 writes value x, T2 reads value x after this and writes value y, T3 reads value y and writes value z, T4 reads value z....

Now if T1 (or any of the subsequent transactions) aborts, all the subsequent transactions after it must abort too

avoided by: whenever a transaction T1 reads value x after it has been modified by T2, the schedule must make sure that T2 commits before T1 reads

a schedule is strict if for any two transactions T1 and T2 in the schedule, if T1 writes value x T2 only works (reads or writes) with x after T1 has committed or aborted

creates schedules

3 options for transactions:

• execute
• reject
• delay

2 main classes:

• pessimistic: delays all incoming operations and always picks safe execution order for concurrent operations
  • e.g. lock-based scheduler
• optimistic: execute incoming operations as fast as possible, but may have to rollback
  • e.g. time-stamp based scheduler

uses two-phase locking:

• for all accessed data items, the transactions must acquire a shared (read) or exclusive (write) lock
• if they can't acquire the needed lock, they are put on the waiting list
• two-phase: a transaction first acquires all locks, only after that it starts releasing them (it doesn't get new locks after the first release) (also it releases all yet-to-release locks at commit/abort)

• strict two-phase: all locks must be held until the end of the transaction (avoids cascading aborts)
  • we can also reduce sizes of the locks, since we only need to contain the owner transaction and not the wait list

• locks managed by Lock Manager: uses a queue for each lock with one mutex per queue

done via waits-for graph: directed graph, nodes are transactions, there is an edge between two nodes T1 and T2 if T1 is waiting for a lock that T2 has. 

The schedule has a deadlock if the waits-for graph is cyclic

Calculating waits-for graphs is expensive => use time-out too: at time-out, calculate waits-for graph and abort one transaction if needed