• Requires to store both key and value in the slot.

• Replace the deleted entry with a dummy entry to tell future lookups to keep scanning.
• Shift the adjacent entries which were originally shifted, i.e., those who were originally hashed to the same key.
  • Very expensive and rarely implemented in practice.

• If a rare cycle happens, rebuild all hash tables with new seeds or with larger tables.

• A key is only mod by \(2n\) if the result of \((k\ mod\ n)\) is above the split pointer, i.e., \(0 \leq k\ mod\ n < sp)\).
• Let \(r = k\ mod\ n\), then \(k = pn + r\) and \(0 \leq r < sp\).
• Let \(r' = k\ mod\ 2n\), then \(k = q(2n) + r'\).
• If \(p = 2m\), then we also have \(k = m(2n) + r = q(2n) + r'\), in this case \(0 \leq r = r' < sp\).
• If \(p = 2m + 1\), then we have \(k = m(2n) + r + n = q(2n) + r'\), in this case \(n \leq r' = n + r < n + sp\).

• Record ID: a unique identifier for a row in a table (cf. Tuple layout post).
• Object ID: a unique identifier for an object, used to reference a user-defined type.

• E.g., If pages are index-organized, the sibling pages can be pre-fetched.

• The timestamp can be stored in a queue for efficient sorting.

• With the LRU policy the oldest pages are evicted, but they are more likely to be scanned soon.

• Fast: only drop clean pages.
• Slow: write back dirty pages to ensure persistent change, and then evict them (if they will not be read again.).

• Most common: use fixed-length offsets, e.g., the value in a given column belong to the same tuple as the value in another column at the same offset.
• Less common: use embedded tuple ids, e.g., each attribute is associated with the tuple id, and the DBMS stores a mapping to jump to any attribute with the given tuple id.

• Why small chunk: must decompress before reading/writing the data every time, hence need o limit the compression scope.

• E.g., when SELECT DISTINCT with pattern-matching, the DBMS only needs to scan the encoding dictionary (but without DISTINCT it still needs to scan the whole column).

• madvise: tell the OS when DBMS is planning on reading some page.
• mlock: tell the OS to not swap ranges outs of disk.
• msync: tell the OS to flush memory ranges out to disk, i.e., write.

• Fragmentation: tuple deletions leave gaps in the pages.
• Inefficient disk I/O: need to fetch the entire block to update a tuple; users could randomly jump to multiple different pages to update a tuple.

• Most common: store a bitmap in a centralized header to specify which attributes are null.
• Designate a value, e.g., INT32_MIN.
• Not recommended: store a flag per attribute to mark a value is null; may need more bits to ensure word alignment.

Data definition language (DDL): CREATE.

CREATE TABLR student (
    sid INT PRIMARY KEY,
    name VARCHAR(16),
    login VARCHAR(32) UNIQUE,
    age SMALLINT,
    gpa FLOAT
);

Combine columns from one or more tables and produces a new table.

-- All students that get an A in 15-721
SELECT s.name
    FROM enrolled AS e, student AS s
WHERE e.grade = 'A' AND e.cid = '15-721'
    AND e.sid = s.sid

Take as input a bag of tuples and produce a single scalar value.

-- Get number of students and their average GPA with a '@cs' login
SELECT AVG(gpa), COUNT(sid) FROM student WHERE login LIKE '@cs';
-- Get the unique students
SELECT COUNT(DISTINCT login) FROM student WHERE login LIKE '@cs';

Non-aggregated values in SELECT output must appear in GROUP BY.

-- Get the average GPA in each course
SELECT AVG(s.gpa), e.cid
    FROM enrolled AS e, student AS s
WHERE e.sid = s.sid
GROUP BY e.cid;

HAVING: filter output results based on aggregation computation.

SELECT AVG(s.gpa), e.cid
    FROM enrolled AS e, student AS s
WHERE e.sid = s.sid
GROUP BY e.cid
HAVING AVG(s.gpa) > 3.9;

• % matches any sub-string,
• _ matches any one character

One can store the results into another table

-- output to a non-existing table
SELECT DISTINCT cis INTO CourseIds FROM enrolled;
-- output to an existing table with the same number of columns and column type
-- but the names do not matter
INSERT INTO CourseIds (SELECT DISTINCT cid FROM enrolled);

Use LIMIT, OFFSET to restrict the output number.

SELECT sid FROM enrolled WHERE cid = '15-721'
ORDER BY UPPER(grade) DESC, sid + 1 ASC;
    LIMIT 10 OFFSET 10;  -- output 10 tuples, starting from the 11th tuple

Inner queries can appear anywhere.

-- Output a column 'one' with 1s, the number of 1s
-- equals to the number of rows in 'student'
SELECT (SELECT 1) AS one FROM student;

-- Get the names of students that are enrolled in '15-445'
SELECT name FROM students
    WHERE sid IN (
        SELECT sid FROM enrolled
        WHERE cid = '15-445'
);

-- Get student record with the highest id
-- that is enrolled in at least one course.
SELECT student.sid, name
    FROM student
    -- the intermediate output is aliases as max_e
    JOIN (SELECT MAX(sid) AS sid FROM enrolled) AS max_e
    -- only select student who has the max_e
    ON student.sid = max_e.sid;

-- the above is same as below, but `join` syntax is more preferred
SELECT student.sid, name
FROM student AS s, (SELECT MAX(sid) AS sid FROM enrolled) AS max_e
WHERE s.sid = max_e.sid;

• ALL: must satisfy expression for all rows in sub-query.
• ANY, IN: must satisfy expression for at least one row in sub-query.

• EXISTS: at least one row is returned.

  -- Get all courses with no students enrolled in
  SELECT * FROM course
      WHERE NOT EXISTS(
          SELECT * FROM enrolled
              WHERE course.cid = enrolled.cid
  )
  
  -- Get students whose gpa is larget than the highest score in '15-712'
  -- and the login has a level > 3
  SELECT student.sid, name
      FROM student AS S
  WHERE s.gpa > ALL (
      SELECT course.score FROM course
          WHERE course.cid = '15-712'
  )
  AND student.login IN (
      SELECT login FROM enrolled
      WHERE level > 3
  );
  

CTEs use WITH to bind the output of an inner query to a temporary table.

WITH cteName (col1, col2) AS (
    SELECT 1, 2
)
SELECT col1 + col2 FROM cteName;