Basic Querying and Predicates

Now your database can store data durably and load it back. The next piece is querying: given a condition (a predicate), return only the rows that match it.

A predicate is a function that tests a row: does age > 25? Is name == "Alice"? In C, you could pass a function pointer, but we'll use a predicate struct that describes one condition as data:

typedef struct {
    enum { PRED_EQ, PRED_LT, PRED_GT, PRED_LE, PRED_GE } op;
    char column[32];             /* "age" or "name" */
    uint32_t int_value;          /* for numeric comparisons */
    char str_value[256];         /* for string comparisons */
} Predicate;

Why a Struct and Not a Function Pointer?

A function pointer would work for filtering, but it's a black box: the engine can only call it, row by row. A predicate-as-data can be inspected. The engine can look at it and think: "this is an equality test on id, and id has an index — skip the scan entirely and do one lookup." That inspection step is the seed of a query optimizer, and it's only possible because the condition is data, not code.

This is the deep idea behind SQL itself. SQL is declarative: you say what you want, never how to get it. The database parses your WHERE age > 25 into exactly this kind of structure (a predicate tree), then chooses an execution strategy: which index to use, which table to scan first in a join, whether to sort or hash. Two systems can run the same query a million times apart in cost depending on that choice. Your Predicate struct is a one-node predicate tree; real ones combine nodes with AND/OR/NOT.

Why Push Filtering Into the Engine?

In the earliest data systems, applications read every record and filtered in application code. Moving the filter into the database — "predicate pushdown" — was a breakthrough for three reasons:

• Indexes. If id == 5 and id is indexed, the engine reads one row instead of n. The application can't make that decision; it doesn't know the indexes exist.
• Data movement. The filter runs where the data lives. Filtering 10 million rows down to 50 inside the engine means 50 rows cross the boundary to the app — not 10 million. In a client/server database, that boundary is the network; the difference is measured in seconds.
• Freedom to optimize. Once the engine owns evaluation, it can compile predicates, evaluate them over compressed data, parallelize across cores, or push them all the way into remote storage nodes — all without the application changing a line.

The predicate is the contract between the application and the engine: the app says what it wants; the engine decides how to get it efficiently.

Scan Cost and Selectivity

Our query is a full table scan: test every row, O(n) per query. Whether that's terrible depends on selectivity — the fraction of rows that match. For age > 0 (matches everything), a scan is optimal: you must touch every row anyway, and thanks to lesson 1, scanning our contiguous array is as fast as memory allows. For id == 5 (matches one row), a scan is absurd — that's what indexes fix in a later lesson. Real query planners keep statistics (histograms of column values) to estimate selectivity and choose between scan and index per query.

Note one design decision in the code below: table_query returns a new table containing copies of the matching rows, rather than pointers into the original. Copying costs memory, but pointers into t->rows would be invalidated by the next insert that triggers a realloc — a use-after-free handed to the caller. This tension (return copies = safe but slow; return references = fast but lifetime-fraught) is fundamental, and it returns with force in the concurrency lesson.