Module 06

Indexes, sorted sets & access strategy

There are four ways to reach a record and nothing chooses between them for you. This module is the decision procedure: what each route costs to read, what it costs to maintain, and how to tell from a design which route the existing programs are actually using.

~40 min1 simulator8-question checkpoint
What this module is really about

Choosing how to find things. In a normal database you write a query and a planner picks the access path. Here there is no planner, so the programmer picks — in code, permanently.

The practical consequence for you: if no route exists for the question you want to ask, you cannot ask it. You read everything and filter in your own code. Recognising that a route is absent is as much a skill as knowing which one is fastest.

New words on this page, one line each
access path
A route to a record. There are four, and the program names one explicitly.
index
A sorted tree that finds a record by a value without scanning everything.
SR7 / SR8
The two kinds of internal record that make up an index: its root, and the blocks of sorted keys.
fan-out
How many keys fit in one index block. Decides how many levels deep the index is, and so how many disk reads a lookup costs.
sorted chain
Children kept in order on a chain. Ordered reading is free; searching still walks it one link at a time.
area sweep
Reading every record in a storage area in physical order. The fastest way to read all of something.

The four ways to reach a record

In plain English

By key formula — you know the unique key and arithmetic tells you the shelf. One read.

Follow a relationship — you have the parent and want its children. Nearly free if they were stored next to it.

Through an index — you have some other value, or you need a range, or you need results in order.

Read everything — shelf by shelf, front to back. Slow per record, unbeatable when you genuinely want all of them.

PathReachesCost to readCost to maintain
CALCOne record by its declared key1 I/O, plus 1 per synonym hopFree — the address is computed
Set traversalAll members of one owner, in set order1 I/O per page touched; near-free if members are clustered VIAA few pointer updates per connect/disconnect
IndexOne record, or a key range, or everything in key orderDepth of the index + 1Block reads and writes on every key change; splits on growth
Area sweepEverything in an area, in db-key order1 I/O per page in the areaNone

Notice what is missing: there is no way to say "find all employees whose surname starts with S" unless someone built an index on surname. If no access path supports your predicate, the only remaining option is to read everything and filter in the program. That is not a failure of the database; it is the design contract. Access paths are declared in advance, on purpose.

How an index is actually built

If you know B-trees

It is a B-tree, with one twist: the index blocks are ordinary records occupying ordinary slots on ordinary shelves, in a storage area you choose.

That is not a detail. It means index maintenance shows up in the change log alongside real data changes — so a copy of this database can see a burst of activity that corresponds to no business event at all. Module 10 comes back to this.

An IDMS index is a tree of SR8 index blocks rooted on an SR7 index owner record. Each block holds sorted key values, each paired with a db-key: either the db-key of a lower index block, or the db-key of the actual data record.

SR7 index owner the set's owner record SR8 · top block ARAKI | DELGADO | NOLAN | (hi) ADEYEMI · ARAKI · BAKER → db-key each BERGER · CRANE · DELGADO → db-key each ELLIS · FRANKLIN · IRELAND → db-key each EMPLOYEE 71003:1 EMPLOYEE 71018:1 EMPLOYEE 71042:1
The index blocks are ordinary records occupying lines on ordinary pages, in an area you choose. Reading a key costs one I/O per level plus one for the data record.
the clauses that shape an index
SET NAME IS EMP-NAME-NDX
    ORDER IS SORTED
    MODE IS INDEX
        BLOCK CONTAINS 30 KEYS       *> fan-out: keys per SR8 block
        DISPLACEMENT IS 0 PAGES      *> where index blocks sit relative to the owner
    OWNER IS SYSTEM                  *> system-owned: a standalone index
    MEMBER IS EMPLOYEE
        MANDATORY AUTOMATIC
        INDEX DBKEY POSITION IS 4    *> prefix slot holding the index pointer
        ASCENDING KEY IS ( EMP-LAST-NAME-0415 )
        DUPLICATES ARE LAST.

Why block size is the whole performance story

BLOCK CONTAINS n KEYS sets the fan-out. With 30 keys per block, 27,000 records need three levels. With 200 keys per block they need two. Each level is an I/O on every single lookup, so the difference between a well-sized and a badly-sized index is measured in millions of I/Os per day.

The counter-pressure: a bigger block is a bigger record, and index blocks that do not fit comfortably on a page defeat the purpose. Block size, key length and page size have to be chosen together.

Three different things people call “an index”

Picture it

Three different things get called an index, and telling them apart when reading a design matters.

A sorted chain is the cards on one string kept in alphabetical order. Reading them in order is free. Finding one particular card still means walking the string.

An index is a separate catalogue that takes you straight there.

A sorted, indexed relationship is both. If a design says only “sorted”, you get the order and not the speed.

System-owned index

OWNER IS SYSTEM, MODE IS INDEX. A standalone index over every occurrence of a record type. The closest thing IDMS has to CREATE INDEX.

Indexed set

A normal owner-member set whose mode is INDEX rather than CHAIN. Members are reached through an index scoped to that owner — useful when one owner has thousands of members.

Sorted chain

Not an index at all: ORDER IS SORTED, MODE IS CHAIN. Members sit in key order on a linked list. Ordered retrieval is free; keyed positioning still walks.

The distinction matters when reading a schema. ORDER IS SORTED tells you the members are in key order. MODE IS INDEX tells you there is a tree. A sorted chain of 5,000 members gives you ordered retrieval and a 2,500-hop average search; a sorted indexed set gives you both.

What an index costs you on every write

The bit with no equivalent in a normal database

Every index costs work on every write — that part is familiar. What is not familiar is that nothing here will decline to use a bad index.

In PostgreSQL, an index on a two-value status column would simply be ignored by the planner. Here the program names the route explicitly, so a useless index gets used, walks half a chain of hundreds of thousands of entries, and nobody notices for a year.

Every index costs something on write. Specifically:

  • STORE — insert the key into the correct leaf block. If the block is full it splits, which writes two blocks and updates the parent.
  • ERASE — remove the key; blocks may need consolidating.
  • MODIFY of an indexed field — remove the old key and insert the new one. A "one-column update" becomes several block writes.
  • Duplicates — DUPLICATES ARE FIRST/LAST chains equal keys, so a low-cardinality index degenerates into long chains and gives you very little.
Low-cardinality indexes are worse than useless An index on a two-value status field turns into two enormous duplicate chains. Every lookup walks half of one of them, and every insert pays maintenance. In IDMS there is no optimiser to notice and ignore it — if the program says to use it, it is used.

Indexes also fragment. As blocks split and records are erased, the tree becomes less dense and deeper than it needs to be. Rebuilding an index — through the appropriate maintenance utility for your release — restores density. IDMSDBAN reports index depth and block occupancy so you can tell when it is time.

How to choose, step by step

The counter-intuitive one

To read everything, do not use the index. Sweep the storage area in physical order.

An index scan reads the sorted keys in order, then jumps to a data shelf per record — in effectively random order, worst case one disk read per record. A sweep reads each shelf exactly once, sequentially, and the hardware can read ahead. For a full extract, always sweep.

  1. Do you know the unique key? If the record is CALC on it: OBTAIN CALC. One I/O, done.
  2. Do you have the record's owner and want all its members? Walk the set. If members are clustered VIA the same set, this is close to free.
  3. Do you have a non-CALC key value, or need a range? You need an index on that field, or you are sweeping.
  4. Do you need everything in key order? Index scan — but if you need everything in any order and there are a lot of them, an area sweep is often cheaper than an index scan, because it reads each page once instead of jumping.
  5. Do you have a saved db-key? OBTAIN … DB-KEY IS. Always the cheapest thing available.
Step 4 is counter-intuitive and important For a full extract, an area sweep in db-key order beats an index scan almost every time. The index scan reads the leaf blocks in key order and then jumps to a data page per record, in effectively random order — worst case, one I/O per record. The sweep reads every page exactly once, sequentially, and the access method can prefetch. When you build an initial load, sweep.

What this means for replication

  • Sweep for the initial load; do not scan an index. Sequential page order is the fastest consistent read of an area, and it gives you a natural chunking boundary (page ranges) for parallelism.
  • Index maintenance shows up in the journal as structural change. SR8 block updates are real journal activity that corresponds to no user-visible data change. Capture must recognise and discard them, or your change volumes will be inexplicably high.
  • Index definitions are hints about business keys. Somebody built an index on that field because applications search by it. That is strong evidence about what your target model should index too — and a sorted set with DUPLICATES NOT ALLOWED is a real uniqueness constraint you can carry over.
  • An indexed set with thousands of members per owner is a red flag for the target model. It usually means the "owner" is a category, not a parent, and the relational analogue is an indexed foreign key rather than anything that needs preserving as an ordered structure.
Exercise 6.1 — Read the access paths off a schema

Given: EMPLOYEE is CALC on EMP-ID, is an OPTIONAL AUTOMATIC member of DEPT-EMPLOYEE (sorted chain on surname) and of OFFICE-EMPLOYEE (chain, order NEXT), and is a MANDATORY AUTOMATIC member of the system-owned index EMP-NAME-NDX on surname. State the cheapest access path for each requirement:

  1. The employee with number 0033.
  2. Every employee in department 3200, in surname order.
  3. Every employee in the company whose surname is DELGADO.
  4. Every employee in the company, any order, for a nightly extract.
  5. The employee who sits in office C02 and started most recently.

Answers: (1) OBTAIN CALC. (2) Walk DEPT-EMPLOYEE — it is already sorted by surname, so no sort is needed. (3) EMP-NAME-NDX, positioned by key. (4) Area sweep. (5) There is no access path for this — OFFICE-EMPLOYEE is ordered NEXT, not by date, and no index exists on start date. You must walk the office's members and compare in the program. Recognising the absence of a path is the skill being tested.

Checkpoint