[database] iterators and joins

Pipe

SQL query -> query parser & optimizer -> relational algebra -> B+ tree indexed scan iterator

Tuple-in -> Tuple-out (dataflow graph)

Query executor instantiates operators

Iterator interface (pull based computation model)

Heap Scan

Does not have any children but call file manager for the next page.

Sort (2-passes)

Group By on Sorted Input

the implement is memory efficient while merge each group with one tuple.

Full Query Plan

Join Operators (binary operators)

Simple Nested Looks Theta Join

Page Nested Loop Join (as page block)

'Memory Chunk' Nested Loop Join

[C++] update for hinnant16 map

 

[C++] compare_exchange_weak / compare_exchange_strong and why spuriously fail happens

reference:
compare_exchange_weak / compare_exchange_strong

compare_exchange_strong; no spuriously fail

compare_exchange_weak; spuriously fail due to using timed lock; compare_exchange_weak is useful inside a loop;

[DB study] Serializable Snapshot Isolation (SSI) and write skew; how Spanner works.

Reference:
Serializable Snapshot Isolation in PostgreSQL paper 
A Read-Only Transaction Anomaly Under Snapshot Isolation paper
A Critique of ANSI SQL Isolation Levels paper

Two main properties that characterize Snapshot Isolation:

1. A transaction in Snapshot Isolation has two significant timestamps: the one at which it performs its reads, and the one at which it performs its writes. The read timestamp defines the “consistent snapshot” of the database the transaction sees. If someone else commits writes at a point after a transaction T’s read timestamp, T will not see those changes (this is generally enforced using MVCC. We’ll refer to a transaction named “x” as Tx and its read and write timestamps as Rx and Wx, respectively.
2. Two transactions are concurrent if the intervals during which they are executing overlap (R1 < W2 and W1 > R2). In Snapshot Isolation, the database enforces that two committed transactions which are concurrent have disjoint write sets (meaning they don’t write to any of the same memory locations). Any transaction whose commit would cause this restriction to be violated is forced to abort and be retried.

Consider two transactions, P and Q. P copies the value in a register x to y, and Q copies the value in a register y to x. There are only two serial executions of these two, P, Q or Q, P. In either, the end result is that x = y. However, Snapshot Isolation allows for another outcome:

• Transaction P reads x
• Transaction Q reads y
• Transaction P writes the value it read to y
• Transaction Q writes the value it read to x

This is valid in Snapshot Isolation: each transaction maintained a consistent view of the database and its write set didn’t overlap with any concurrent transaction’s write set. Despite this, x and y have been swapped, an outcome not possible in either serial execution.

Conceptually, there are three types of conflicts: 

• wr-conflicts (Dirty Reads)
• ww-conflicts (Lost Updates)
• rw-conflicts.

PostgreSQL SSI data structure:

• SIREAD locks
• An SIREAD lock, internally called a predicate lock, is a pair of an object and (virtual) txids that store information about who has accessed which object.
• rw-conflicts
• A rw-conflict is a triplet of an SIREAD lock and two txids that reads and writes the SIREAD lock. The CheckForSerializableConflictIn function is invoked whenever either an INSERT, UPDATE, or DELETE command is executed in SERIALIZABLE mode, and it creates rw-conflicts when detecting conflicts by checking SIREAD locks.

SQL syntax:

• select-for-x: https://www.cockroachlabs.com/docs/stable/select-for-update#lock-strengths

[DB study] Serializable vs. Snapshot Isolation Level

Reference:
https://techcommunity.microsoft.com/t5/sql-server-blog/serializable-vs-snapshot-isolation-level/ba-p/383281

[2024] Reading index

[C++]

C++20 - lambda

C++20 - spaceship operator

[Concurrency] [C++][Go] Wrap up - 2018

[C++] memory model in depth

[Database]

Serializable Snapshot Isolation (SSI) and write skew

Serializable vs. Snapshot Isolation Level

[database] iterators and joins

[System Design]

[Ray][Notes] Papers and Design Doc

[Algorithm]

[Math]

[Calculus]

• Derivative as a function
• Differentiation rules
• The mean value theorem
• L'Hospital's rule
• Newton's method
• Antiderivatives

[Linear Algebra]

[Fiction/Prose]

成為真正的人 - 甘耀明

海幻 - 梨木香步

陽光小姐 - 吉田修一

國寶 - 吉田修一

哪啊哪啊神去村夜話 - 三浦しをん

九歌111年散文選 - 言叔夏(編者)

真夏方程式 - 東野圭吾

第十年的情人節 - 東野圭吾

克拉拉與太陽 - 石黑一雄

美國佬 - Chimamanda Ngozi Adichie

沒有的生活 - 言叔夏

[C++] avoid tail call based on different compiler

// BLOCK_TAIL_CALL_OPTIMIZATION
//
// Instructs the compiler to avoid optimizing tail-call recursion. This macro is
// useful when you wish to preserve the existing function order within a stack
// trace for logging, debugging, or profiling purposes.
//
// Example:
//
//   int f() {
//     int result = g();
//     BLOCK_TAIL_CALL_OPTIMIZATION();
//     return result;
//   }
#if defined(__pnacl__)
#define BLOCK_TAIL_CALL_OPTIMIZATION() if (volatile int x = 0) { (void)x; }
#elif defined(__clang__)
// Clang will not tail call given inline volatile assembly.
#define BLOCK_TAIL_CALL_OPTIMIZATION() __asm__ __volatile__("")
#elif defined(__GNUC__)
// GCC will not tail call given inline volatile assembly.
#define BLOCK_TAIL_CALL_OPTIMIZATION() __asm__ __volatile__("")
#elif defined(_MSC_VER)
#include 
// The __nop() intrinsic blocks the optimisation.
#define ABSL_BLOCK_TAIL_CALL_OPTIMIZATION() __nop()
#else
#define ABSL_BLOCK_TAIL_CALL_OPTIMIZATION() \
  if (volatile int x = 0) {                 \
    (void)x;                                \
  }
#endif