The Crux: Fairness Over Speed. Unlike the schedulers we explored in Chapter 8 (like Shortest Job First or Multi-Level Feedback Queues) that optimize for "turnaround time"  or "response time", proportional-share schedulers introduced in this Chapter aim to guarantee that each job receives a specific percentage of CPU time.

(This is part of our series going through OSTEP book chapters.)

Basic Concept: Tickets

Lottery Scheduling serves as the foundational example of proportional-share schedulers. It uses a randomized mechanism to achieve fairness probabilistically. The central concept of Lottery Scheduling is the ticket. Tickets represent the share of the resource a process should receive.

The scheduler holds a lottery every time slice. If Job A has 75 tickets and Job B has 25 (100 total), the scheduler picks a random number between 0 and 99. Statistically, Job A will win 75% of the time. The implementation is incredibly simple. It requires a random number generator, a list of processes, and a loop that sums ticket values until the randomly picked counter (300 in the below example) exceeds the winning number.

Advanced Ticket Mechanisms

1.  Ticket Currency: Users can allocate tickets among their own jobs in local currency (e.g., 500 "Alice-tickets"), which the system converts to global currency. This delegates the "fairness" decision to the user.

2.  Ticket Transfer: A client can temporarily hand its tickets to a server process to maximize performance while a specific request is being handled.

3.  Ticket Inflation: In trusted environments, a process can unilaterally boost its ticket count to reflect a higher need for CPU. In competitive settings this is unsafe, since a greedy process could grant itself excessive tickets and monopolize the machine. In practice, modern systems prevent this with control groups (cgroups), which act as an external regulator that assigns fixed resource weights so untrusted processes cannot simply print more tickets to override the scheduler.

Lottery Scheduling depends on randomness to decide which job runs next. This randomness helps avoid the tricky cases that can trip up traditional algorithms, like LRU on cyclic workloads, and keeps the scheduler simple with minimal state to track. However, fairness is only achieved over time. In the short term, a job might get unlucky and lose more often than its share of tickets. Studies show that fairness is low for short jobs and only approaches perfect fairness as the total runtime increases.

Lottery vs. Stride vs. CFS scheduling

Stride Scheduling emerged to address the probabilistic quirks of Lottery Scheduling. It assigns each process a stride, inversely proportional to its tickets, and maintains a pass value tracking how much CPU time the process has received. At each decision point, the scheduler selects the process with the lowest pass value.

This guarantees exact fairness each cycle, but it introduces challenges with global state. When a new process arrives, assigning it a fair initial pass value is tricky: set it too low, and it can dominate the CPU; too high, and it risks starvation. In contrast, Lottery Scheduling handles new arrivals seamlessly, since it requires no global state.

The Linux Completely Fair Scheduler (CFS) builds on these earlier proportional schedulers but removes randomness by using Virtual Runtime (vruntime) to track each process’s CPU usage. At every scheduling decision, CFS selects the job with the smallest vruntime, ensuring a fair distribution of CPU time. To prevent excessive context-switching overhead when there are many tasks (each receiving only a tiny slice of CPU time), CFS enforces a min_granularity. This ensures every process runs for at least a minimum time slice, and it balances fairness with efficient CPU utilization.

To prioritize specific processes, CFS uses the classic UNIX "nice" level, which allows users to assign values between -20 (highest priority) and +19 (lowest priority). CFS maps these values to geometric weights; a process with a higher priority (lower nice value) is assigned a larger weight. This weight directly alters the rate at which vruntime accumulates: high-priority processes add to their vruntime much more slowly than low-priority ones. When determining exactly how long a process should run within the target scheduling latency (sched_latency), instead of simply dividing the target latency equally among all tasks (e.g., 48ms/n), CFS calculates the time slice for a specific process k as a fraction of the total weight of all currently running processes.

Consequently, a high-priority job can run for a longer physical time while only "charging" a small amount of virtual time, allowing it to claim a larger proportional share of the CPU compared to "nicer" low-priority tasks.

Finally, because modern systems handle thousands of processes, CFS replaces the simple lists of Lottery Scheduling with Red-Black Trees, giving $O(\log n)$ efficiency for insertion and selection.

Challenges in Proportional Sharing

The I/O Problem. Proportional schedulers face a challenge when jobs sleep, such as waiting for I/O. In a straightforward model, a sleeping job lags behind, and when it resumes, it can monopolize the CPU to catch up, potentially starving other processes. CFS addresses this by resetting the waking job’s vruntime to the minimum value in the tree. This ensures no process starves, but it can penalize the interactive job, leading to slower response times.

The Ticket Assignment Problem. Assigning tickets is still an open challenge. In general-purpose computing, such as browsers or editors, it’s unclear how many tickets each application deserves, making fairness difficult to enforce. The situation is a bit more clear in virtualization and cloud computing, where ticket allocation aligns naturally with resource usage: if a client pays for 25% of a server, it can be assigned 25% of the tickets, providing a clear and effective proportional share.

Throughput for the write-heavy steps of the Insert Benchmark look like a distorted sine wave with Postgres on CPU-bound workloads but not on IO-bound workloads. For the CPU-bound workloads the chart for max response time at N-second intervals for inserts is flat but for deletes it looks like the distorted sine wave. To see the chart for deletes, scroll down from here. So this looks like a problem for deletes and this post starts to explain that.

tl;dr

• Once again, blame vacuum

History of the Insert Benchmark

Long ago (prior to 2010) the Insert Benchmark was published by Tokutek to highlight things that the TokuDB storage engine was great at. I was working on MySQL at Google at the time and the benchmark was useful to me, however it was written in C++. While the Insert Benchmark is great at showing the benefits of an LSM storage engine, this was years before MyRocks and I was only doing InnoDB at the time, on spinning disks. So I rewrote it in Python to make it easier to modify, and then the Tokutek team improved a few things about my rewrite, and I have been enhancing it slowly since then.

Until a few years ago the steps of the benchmark were:

• load - insert in PK order
• create 3 secondary indexes
• do more inserts as fast as possible
• do rate-limited inserts concurrent with range and point queries

 MariaDB 12.3 has a new feature enabled by the option binlog_storage_engine. When enabled it uses InnoDB instead of raw files to store the binlog. A big benefit from this is reducing the number of fsync calls per commit from 2 to 1 because it reduces the number of resource managers from 2 (binlog, InnoDB) to 1 (InnoDB).

My previous post had results for sysbench with a small server. This post has results for the Insert Benchmark with a similar small server. Both servers use an SSD that has has high fsync latency. This is probably a best-case comparison for the feature. If you really care, then get enterprise SSDs with power loss protection. But you might encounter high fsync latency on public cloud servers.

tl;dr for a CPU-bound workload

• Enabling sync on commit for InnoDB and the binlog has a large impact on throughput for the write-heavy steps -- l.i0, l.i1 and l.i2.
• When sync on commit is enabled, then also enabling the binlog_storage_engine is great for performance as throughput on the write-heavy steps is 1.75X larger for l.i0 (load) and 4X or more larger on the random write steps (l.i1, l.i2)

MariaDB 12.3 has a new feature enabled by the option binlog_storage_engine. When enabled it uses InnoDB instead of raw files to store the binlog. A big benefit from this is reducing the number of fsync calls per commit from 2 to 1 because it reduces the number of resource managers from 2 (binlog, InnoDB) to 1 (InnoDB).

In this post I have results for the performance benefit from this when using storage that has a high fsync latency. This is probably a best-case comparison for the feature. A future post will cover the benefit on servers that don't have high fsync latency.

tl;dr

• the performance benefit from this is excellent when storage has a high fsync latency
• my mental performance model needs to be improved. I gussed that throughput would increase by ~2X when using binlog_storage_engine relative to not using it but using sync_binlog=1 and innodb_flush_log_at_trx_commit=1. However the improvement is larger than 4X.

Relational composition is to joins what the cartesian product is to tables: it produces every result that could be true, not just what is true. This often leads to SQL mistakes and can often be suspected when a SELECT DISTINCT is added after a query starts returning more rows than expected, without the root cause being understood.

In its mathematical definition, relational composition is the derived relation obtained by existentially joining two relations on a shared attribute and projecting away that attribute. In a database, it is meaningful only when a real‑world invariant ensures that the resulting pairs reflect actual facts. Otherwise, the result illustrates what E. F. Codd, in his 1970 paper A Relational Model of Data for Large Shared Data Banks, called the connection trap.

Codd uses two relations in his example: a supplier supplies parts, and a project uses parts. At an intuitive level, this connection trap mirrors a syllogism: if a supplier supplies a part and a project uses that part, a join can derive that the supplier supplies the project—even when that conclusion was never stated as a fact.

Codd observed that the connection trap was common in pre‑relational network data models, where users navigated data by following physical pointers. Path existence was often mistaken for semantic relationship. The relational model solved this problem by replacing navigational access with declarative queries over explicitly defined relations, and modern document models now do the same.

However, while the relational model removes pointer‑based navigation, it does not eliminate the trap entirely. Joins can still compute relational compositions, and without appropriate cardinality constraints or business invariants, such compositions may represent only possible relationships rather than actual ones. In this way, the connection trap can be reintroduced at query time, even in modern relational systems such as PostgreSQL, and similarly through $lookup operations in MongoDB.

PostgreSQL — reproducing the connection trap

This model declares suppliers, parts, projects, and two independent many‑to‑many relationships:

CREATE TABLE suppliers (
    supplier_id TEXT PRIMARY KEY
);

CREATE TABLE parts (
    part_id TEXT PRIMARY KEY
);

CREATE TABLE projects (
    project_id TEXT PRIMARY KEY
);

-- Supplier supplies parts
CREATE TABLE supplier_part (
    supplier_id TEXT REFERENCES suppliers,
    part_id     TEXT REFERENCES parts,
    PRIMARY KEY (supplier_id, part_id)
);

-- Project uses parts
CREATE TABLE project_part (
    project_id TEXT REFERENCES projects,
    part_id    TEXT REFERENCES parts,
    PRIMARY KEY (project_id, part_id)
);

This follows Codd’s classic suppliers–parts–projects example, where suppliers supply parts and projects use parts as independent relationships.

The following data asserts that project Alpha uses parts P1 and P2, that supplier S1 supplies parts P1 and P2, and that supplier S2 supplies parts P2 and P3:

INSERT INTO suppliers VALUES ('S1'), ('S2');
INSERT INTO parts     VALUES ('P1'), ('P2'), ('P3');
INSERT INTO projects  VALUES ('Alpha');

-- Supplier capabilities
INSERT INTO supplier_part VALUES
('S1', 'P1'),
('S1', 'P2'),
('S2', 'P2'),
('S2', 'P3');

-- Project uses parts P1 and P2
INSERT INTO project_part VALUES
('Alpha', 'P1'),
('Alpha', 'P2');

The following query is valid SQL:

SELECT DISTINCT
    sp.supplier_id,
    pp.project_id
FROM supplier_part sp
JOIN project_part pp
  ON sp.part_id = pp.part_id;

However, this query falls into the connection trap:

 supplier_id | project_id
-------------+------------
 S2          | Alpha
 S1          | Alpha
(2 rows)

As we defined only supplier–part and project–part relationships, any derived supplier–project relationship is not a fact but a relational composition. We know that Alpha uses P1 and P2, and that part P2 can be supplied by either S1 or S2, but we have no record of which supplier actually supplies Alpha.

This query asserts “Supplier S1 supplies project Alpha”, but the data only says: “S1 and S2 supply P2” and “Alpha uses P2”.

This is the connection trap, expressed purely in SQL.

PostgreSQL — the correct relational solution

If a supplier actually supplies a part to a project, that fact must be represented directly. We need a new table:

CREATE TABLE supply (

    supplier_id TEXT,
    project_id  TEXT,
    part_id     TEXT,

    PRIMARY KEY (supplier_id, project_id, part_id),

    FOREIGN KEY (supplier_id, part_id)
        REFERENCES supplier_part (supplier_id, part_id),

    FOREIGN KEY (project_id, part_id)
        REFERENCES project_part (project_id, part_id)
);

These foreign keys encode subset constraints between relations and prevent inserting supplies of parts not supplied by the supplier or not used by the project.

This relation explicitly states who supplies what to which project. We assume that the real‑world fact is “Alpha gets part P2 from supplier S1”:

INSERT INTO supply VALUES
('S1', 'Alpha', 'P2');

The correct query reads from this relation:

SELECT supplier_id, project_id
FROM supply;

 supplier_id | project_id
-------------+------------
 S1          | Alpha
(1 row)

The relationship is now real and asserted, not inferred. In total, we have six tables:

postgres=# \d
             List of relations
 Schema |     Name      | Type  |  Owner
--------+---------------+-------+----------
 public | parts         | table | postgres
 public | project_part  | table | postgres
 public | projects      | table | postgres
 public | supplier_part | table | postgres
 public | suppliers     | table | postgres
 public | supply        | table | postgres
(6 rows)

In practice, you should either store the relationship explicitly or avoid claiming it exists. Although the relational model avoids pointers, it is still possible to join through an incorrect path, so the application must enforce the correct one.

In ad-hoc query environments such as data warehouses, data is typically organized into domains and modeled using a dimensional ("star schema") approach. Relationships like project–supplier are represented as fact tables within a single data mart, exposing only semantically valid join paths and preventing invalid joins.

MongoDB — reproducing the connection trap

The following MongoDB data mirrors the PostgreSQL example. MongoDB allows representing relationships either as separate collections or by embedding, depending on the bounded context. Here we start with separate collections to mirror the relational model:

db.suppliers.insertMany([
  { _id: "S1" },
  { _id: "S2" }
]);

db.parts.insertMany([
  { _id: "P1" },
  { _id: "P2" },
  { _id: "P3" }
]);

db.projects.insertMany([
  { _id: "Alpha" }
]);

// Supplier capabilities
db.supplier_parts.insertMany([
  { supplier: "S1", part: "P1" },
  { supplier: "S1", part: "P2" },
  { supplier: "S2", part: "P2" },
  { supplier: "S2", part: "P3" }
]);

// Project uses parts P1 and P2
db.project_parts.insertMany([
  { project: "Alpha", part: "P1" },
  { project: "Alpha", part: "P2" }
]);

Using the simple find() API, we cannot fall into the trap directly because there is no implicit connection between suppliers and projects. The application must issue two independent queries and combine the results explicitly.

Simulating the connection trap in a single query therefore requires explicit composition at the application level:

const partsUsedByAlpha = db.project_parts.find(
  { project: "Alpha" },
  { _id: 0, part: 1 }
).toArray();

const suppliersForParts = db.supplier_parts.find(
  { part: { $in: partsUsedByAlpha.map(p => p.part) } },
  { _id: 0, supplier: 1, part: 1 }
).toArray();

const supplierProjectPairs = suppliersForParts.map(sp => ({
  supplier: sp.supplier,
  project: "Alpha"
}));

print(supplierProjectPairs);

When forced by the application logic, here is the connection trap associating suppliers and projects:

[
  { supplier: 'S1', project: 'Alpha' },
  { supplier: 'S1', project: 'Alpha' },
  { supplier: 'S2', project: 'Alpha' }
]

As with SQL joins, a $lookup in an aggregation pipeline can fall in the same connection trap:

db.supplier_parts.aggregate([
  {
    $lookup: {
      from: "project_parts",
      localField: "part",
      foreignField: "part",
      as: "projects"
    }
  },
  { $unwind: "$projects" },
  {
    $project: {
      _id: 0,
      supplier: "$supplier",
      project: "$projects.project"
    }
  }
]);

The result is similar and the projection removed the intermediate attributes:

{ "supplier": "S1", "project": "Alpha" }
{ "supplier": "S1", "project": "Alpha" }
{ "supplier": "S2", "project": "Alpha" }

We reproduced the connection trap by ignoring that $lookup produces a derived relationship, not a real one, and that matching keys does not carry business meaning.

MongoDB — normalized solution

As with SQL, we can add an explicit supplies collection that stores the relationship between projects and suppliers:

db.supplies.insertOne({
  project: "Alpha",
  supplier: "S1",
  part: "P2"
});

Then we simply query this collection:

db.supplies.find(
  { project: "Alpha" },
  { _id: 0, supplier: 1, part: 1 }
);

[ { supplier: 'S1', part: 'P2' } ]

The document model is a superset of the relational model as relations can be stored as flat collections. The difference is that referential integrity is enforced by the application rather than in-database. To enforce relationships in the database, they must be embedded as sub-documents and arrays.

MongoDB — domain-driven solution

It's not the only solution in a document database, as we can store a schema based on the domain model rather than normalized. MongoDB allows representing this relationship as part of an aggregate. In a project‑centric bounded context, the project is the aggregate root, and the supplier information can be embedded as part of the supply fact:

db.projects.updateOne(
  { _id: "Alpha" },
  {
    $set: {
      parts: [
        { part: "P2", supplier: "S1" },
        { part: "P1", supplier: null }
      ]
    }
  },
  { upsert: true }
);

The query doesn't need a join and cannot fall into the connection trap:

db.projects.find(
  { _id: "Alpha" },
  { _id: 1, "parts.supplier": 1 }
);

[
  {
    _id: 'Alpha',
    parts: [ 
      { supplier: 'S1' },
      { supplier: null }
    ]
  }
]

This avoids the connection trap by construction. It may look like data duplication—the same supplier name may appear in multiple project documents—and indeed this would be undesirable in a fully normalized model shared across all business domains. However, this structure represents a valid aggregate within a bounded context.

In this context, the embedded supplier information is part of the supply fact, not a reference to a global supplier record. If a supplier’s name changes, it is a business decision, not a database decision, whether that change should be propagated to existing projects or whether historical data should retain the supplier name as it was at the time of supply.

Even when propagation is desired, MongoDB allows updating embedded data efficiently:

db.projects.updateMany(
  // document filter
  { "parts.supplier": "S1" },
  // document update using the array's item from array filter
  {
    $set: {
      "parts.$[p].supplier": "Supplier One"
    }
  },
  // array filter defining the array's item for the update
  {
    arrayFilters: [{ "p.supplier": "S1" }]
  }
);

This update is not atomic across documents, but each document update is atomic and the operation is idempotent and can be safely retried or executed within an explicit transaction if full atomicity is required.

Conclusion

The connection trap occurs whenever relationships are inferred from shared keys, at query time, instead of being explicitly represented as facts, at write time. In SQL, this means introducing explicit association tables and enforcing integrity constraints, rather than deriving then though joins. In MongoDB, it means modeling relationships as explicit documents or embedded subdocuments rather than deriving them through lookups.

In a relational database, the schema is designed to be normalized and independent of specific use cases. All many‑to‑many and fact‑bearing relationships must be declared explicitly, and queries must follow the correct relational path. Referential and cardinality constraints are essential to restrict to only actual facts.

In MongoDB, the data model is typically driven by the domain and the application’s use cases. In a domain-driven design (DDD), strong relationships are modeled as aggregates, embedding related data directly within a document in MongoDB collections. This makes the intended semantics explicit and avoids inferring relationships at query time. Apparent duplication is not a flaw here, but a deliberate modeling choice within a bounded context.

Ultimately, the connection trap is not fully avoided by the data model, but can be a query-time error with joins and projections: deriving relationships that were never asserted. Whether using normalized relations or domain‑driven documents, the rule is the same—if a relationship is a fact, it must be stored as one.

This has results for HammerDB tproc-c on a small server using MySQL and Postgres. I am new to HammerDB and still figuring out how to explain and present results so I will keep this simple and just share graphs without explaining the results.

The comparison might favor Postgres for the IO-bound workloads because I used smaller buffer pools than normal to avoid OOM. I have to do this because RSS for the HammerDB client grows over time as it buffers more response time stats. And while I used buffered IO for Postgres, I use O_DIRECT for InnoDB. So Postgres might have avoided some read IO thanks to the OS page cache while InnoDB did not.

tl;dr for MySQL

• With vu=40 MySQL 8.4.8 uses about 2X more CPU per transaction and does more than 2X more context switches per transaction compared to Postgres 18.1. I will get CPU profiles soon.
• Modern MySQL brings us great improvements to concurrency and too many new CPU overheads
• MySQL 5.6 and 8.4 have similar throughput at the lowest concurrency (vu=10)
• MySQl 8.4 is a lot faster than 5.6 at the highest concurrency (vu=40)