RonDB training · module 08 of 25 · 16 min

Index structures

The hash index that finds and locks every row, the T-tree that orders them, and the hidden tables behind unique keys.

Indexes · two structures, neither stores keys

Every table has a hash index; ordered indexes are T-trees

Hash index · DBACC

  • On the primary key of every table, also hidden, unique index and BLOB tables.
  • Key lookups and all row locks. Full table scans read the rows in DBTUP.
  • About 15 bytes per row.

Ordered index · DBTUX

  • A T-tree per fragment, for every KEY and, unless USING HASH, the primary key.
  • Range scans and sorted access.
  • About 10 bytes per row.

Neither stores key values: the hash index points to rows by row id, an ordered index by physical page and offset (module 07). That is why an index costs the same whatever its columns.

docs: rondb_block_arch.md (DBACC, DBTUX) · basic_sql.md (Index sizes) · code: dblqh/DblqhMain.cpp (initScanrec: a scan runs in DBTUP or DBTUX, never DBACC)

Hashing · one value, two uses

Two hashes: one finds the partition, another the bucket inside it

hash(partition key)in DBTC or the API one of 3840 bucketsthe table's hashmap partition → node group → replicamodule 02 hash(primary key)in DBLQH and DBACC bucket in the fragmentthe hash index element → row id → rowthis module

Routing hashes the partition key (by default the primary key) to find where the row lives.

Inside the owning ldm thread, the primary key hash picks a bucket of the fragment's hash index. Each table records its hash function: xxHash, or MD5 for tables from older versions.

docs: basic_sql.md (Index sizes: the address calculation) · code: src/common/util/rondb_hash.cpp (rondb_calc_hash: xxhash or md5) · dbdict/Dbdict.cpp (HashFunctionFlag)

PART 1

The hash index

DBACC: pages, containers, elements, linear hashing.

Addressing · bits of the hash value

Hash addressing: the low 6 bits pick a bucket, the rest pick the page

hash(primary key)32 bits hash >> 6logical page of the index hash & 63bucket in that page: 64 per page page map→ physical page bucket's container

K = 6: each index page holds 64 buckets, so the bottom 6 bits of the hash pick the bucket and the rest pick the page.

A page map turns the logical page into a physical one, as for rows. The bucket's container holds the elements to search.

docs: basic_sql.md (hash(PrimaryKey) >> 6, hash(PrimaryKey) & 63) · code: dbacc/Dbacc.hpp (k = 6, ZNO_CONTAINERS 64) · ndb_desc prints "K Value: 6"

Index page · 8 KB, four to a 32 KB page

Hash index pages: 64 bucket containers and 8 overflow containers

page header · 32 words · page id, checksum, heads of the free lists 8 KB page buckets 0–7 buckets 8–15 buckets 16–23 buckets 24–31 buckets 32–39 buckets 40–47 buckets 48–55 buckets 56–63 overflow 64–71 13 · full13 · 2nd13 · 3rd

DBACC splits each 32 KB page into four 8 KB index pages: a 32-word header, then 72 buffers of 28 words. Buffers 0 to 63 hold the first container of buckets 0 to 63; 64 to 71 wait for overflow.

A full bucket chains on: first to a free left end in 64 to 71, then to a free right end of any buffer. When the page has none left, to an overflow page.

code: dbacc/Dbacc.hpp (ZHEAD_SIZE 32, ZBUF_SIZE 28, ZNO_CONTAINERS 64, Page8, Page32) · Container.hpp (CONTAINERS_PER_PAGE 72) · DbaccMain.cpp (initPage, getfreelist, insertElement)

Container · a 28-word buffer used from both ends

Containers: one grows forward from the left end, another backward from the right

buffer 5 bucket 5 · grows forward → headerelementelementelement free endheaderelementelement← grows backward · an overflow containerfree words, shared by both ends buffer 9right end free: past 14 words, bucket 9 takes the whole buffer · up to 12 elementsheader123456789101112

Bucket 5 starts at the left end of its buffer: a 2-word header, then 2-word elements, growing forward. The right end is free.

Another chain can take the free right end: its container grows backward from the last word, and the two share the free words between them.

If the right end stays free, a container that passes 14 words takes the whole buffer, up to 12 elements. Below 12 words it gives the end back.

code: dbacc/Container.hpp (CONTAINER_SIZE 28, HEADER_SIZE 2, UP_LIMIT 14, DOWN_LIMIT 12, "can be used from both ends") · DbaccMain.cpp (insertContainer, shrink: releaseRightlist) · Dbacc.hpp (getBackwardContainerPtr)

Element · one per row, 2 words

An index element is a row id, a slice of the hash and a lock bit

Word 1 · unlocked 0 page index of the rowbits 1–13 14–15 reduced hashbits 16–31 Word 2 · page number of the row: with the page index, the row id Word 1 · locked 1 pointer to the operation holding the lockbits 1–31 · the page index and hash move into that operation

Eight bytes per row: the row id split over two words, and 16 bits of the hash to rule out most non-matching rows without touching them.

When a row is locked, the first word is replaced by a pointer to the lock owner. The hash index is the lock table.

code: dbacc/Dbacc.hpp (class ElementHeader: "l = Locked, i = page index, h = reduced hash, o = operation ptr"; elementLength 2)

Key lookup · inside DBACC and DBTUP

Key lookup: compare 16 bits of hash first, the full key only on a match

  1. Hash the primary key; the bits give page and bucket.
  2. Walk the bucket's elements, comparing each reduced hash with the key's: a cheap filter.
  3. On a match, read the key from the row in DBTUP and compare it in full: the index holds no keys.
  4. Found: lock it if asked, hand the row id to DBTUP. Not found: follow the container chain, or answer "no such row".

The reduced hash means a lookup almost never reads a row that is not the one it wants.

docs: basic_sql.md (Index sizes) · code: dbacc/DbaccMain.cpp (getElement, readTablePk: the key compare reads from TUP)

Growing · linear hashing, one bucket at a time

Linear hashing: the index grows one bucket split at a time, never all at once

0 1 2 3 4 5 6 7 next to split 8 one more hash bit decides: stay in 0, or move to 8 then 1 ndb_desc: K Value: 6 · Min load factor: 78 · Max load factor: 80

Buckets split in order, following a pointer. Each split moves only that bucket's elements.

Above the maximum load factor the next bucket splits; one more hash bit divides its elements. The cost is spread over many inserts, so no insert ever waits for a rebuild.

Below the minimum, buckets merge back. Every table shows its settings in ndb_desc.

code: dbacc/Dbacc.hpp (linear hashing: p, maxp) · mysql-test/suite/ndb/r/ndb_desc_extra.result (K Value, Min/Max load factor) · bucket numbers are an illustration

PART 2

Row locks

Kept in the hash index, in a queue per row.

Lock queue · one per locked row

Lock queue: a locked row points to its owner; others queue in parallel or in series

elementlocked lock ownerT1 · exclusive T1 · second operationparallel queue · runs now T2 · shared · waits T3 · shared · waits with T2 serial queue exclusive or shared, owner first

The first operation to lock the row becomes the lock owner; the element now points to it.

Operations that may run with the owner, such as the same transaction's next write, join its parallel queue and run at once.

Conflicting ones wait in the serial queue, grouped so that shared locks behind the owner are granted together when it releases.

code: dbacc/Dbacc.hpp (Operationrec: OP_LOCK_OWNER, OP_LOCK_MODE, nextParallelQue, nextSerialQue) · docs: rondb_concurrency_control.md (RonDB's Row Locking)

Locking · whatever the access path

Every lock goes through the hash index, even for ordered index scans

Read committed

No lock at all: reads the committed row (module 07). The default.

Key lookup with lock

Finds the element and locks it in the same step.

Scan with lock

Ordered index and row-order scans ask the hash index for a lock on each row they return.

There are no range locks: only rows that exist can be locked. Module 09 covers lock modes and deadlocks.

docs: rondb_concurrency_control.md (RonDB's Row Locking, Range Locks)

PART 3

The T-tree

DBTUX: an ordered index built for main memory.

Ordered index · designed for memory, not disk

A T-tree is a balanced binary tree whose nodes hold many entries

AVL tree

One entry and two pointers per node: many pointers, many cache misses.

T-tree

Up to 28 entries in a 256-byte node: two child pointers per node, and the first columns of its smallest key kept at hand.

B-tree

Built for disk blocks. RonDB's indexes never live on disk.

Nodes are 64 words, stored as fixed-size rows in DataMemory. One tree per fragment of the index.

docs: basic_sql.md (The ordered index is implemented as a T-Tree, 256-byte mini-pages) · code: ndb_limits.h (MAX_TTREE_NODE_SIZE 64) · dbtup/DbtupIndex.cpp

T-tree node · 64 words

A T-tree node: header, a prefix of the smallest key, then 2-word entries

header7 words min prefix≤ 4 words entry2 words entry entry entry … entry free slots header · left child, right child, parent · balance · number of entries · scans positioned here min prefix · whole leading columns of the smallest key, a header word each; none if the first column needs over 3 words entry · physical page and offset of the row, 15-bit row version, sorted by key · (64 − 7 − prefix) / 2 entries: 26 to 28

Entries are sorted by key but hold no key: just the row's physical page and offset, not its row id, so a comparison reads the row without the page map. The prefix of the node's smallest key is the exception.

Nodes may vary by 2 entries (min = max − 2) before the tree rebalances, so inserts rarely restructure it.

code: dbtux/Dbtux.hpp (TreeNode: 28 bytes since m_nodeScanInstance, though its comment says 6 words · TreeEnt: m_tupLoc, m_tupVersion:15) · dbtux/DbtuxMeta.cpp (m_prefBytes, m_maxOccup, m_minOccup = max − 2) · DbtuxNode.cpp (setNodePref) · ndb_limits.h (MAX_TTREE_PREF_SIZE 4, MAX_TTREE_NODE_SLACK 2)

Maintenance · triggers, restarts, scans

T-tree maintenance: triggers keep it current; restarts rebuild it from the rows

Triggers

DBTUP fires an internal trigger on every insert, update and delete, even when no indexed column changes: each entry holds the row version. The new entry goes in at once; the old one leaves at commit.

Not on disk

Neither logged nor checkpointed, like the hash index. Every node and cluster restart rebuilds them from the recovered rows.

One tree per fragment

A range scan visits every fragment's tree unless the partition key is fixed (module 04).

More partitions mean more CPUs rebuilding trees in parallel at restart, and more trees to visit per unpruned scan.

docs: rondb_block_arch.md (DBTUX) · alter_table.md (Create Ordered Index) · table_options.md (Considerations for selecting number of partitions) · code: DbtupExecQuery.cpp (every update calls executeTuxUpdateTriggers, no column check) · DbtupTrigger.cpp (addTuxEntries for every ordered index; executeTuxCommitTriggers removes the old version)

Unique index · a hash index on a hidden table

A lookup by unique key is two key lookups

where b = 7unique key b$uniquehash index on b, partitioned by breturns a = 42lookup 1 · some node t1hash index on a, partitioned by areturns the rowlookup 2 · maybe another node

The hidden table is partitioned by the unique key, so the first lookup goes straight to the right node.

It returns the primary key, and a second lookup fetches the row. Writes keep both in step with triggers (module 03).

docs: basic_sql.md (unique index) · alter_table.md (Create Unique Index)

Recap · module 08

What to take away

  • Ordered indexes store no keys, only a physical page; the hash index holds a row id.
  • Hash: 6 bits pick the bucket, 16 bits of hash filter elements, the key is compared in the row.
  • Linear hashing grows one bucket at a time; no insert waits for a rebuild.
  • Row locks live in the hash index: owner, parallel queue, serial queue.
  • T-tree nodes of 64 words, kept by triggers, rebuilt at every restart.

Next · 09 · Transactions and concurrency

RonDB training · 25 modules · you are at 08

Next · 09 · Transactions