skip to content

You sum the per-column byte figures for a 40-column table to size it — what does that sum still leave out?

level: seniorimportance: should knowfreq 46%

answer

  1. sum the columns first
  2. then ask what is not a column
  3. row labels have no header
  4. masks and held-once value sets
  5. shared buffers get counted twice

basics

~20 s

The sum covers column value buffers only. It leaves out the row labels, each column's absence mask, the value set held once behind a coded column, and the real cost of any column measured shallowly — and it double-counts buffers shared with another live table.

solid answer

~50 s

Adding per-column figures is the right first move, and for a table of packed numeric buffers each owned by exactly one column it is the whole answer. Real tables are not that table. Four things sit outside the sum: the **row labels**, if the table carries a row-label structure, which has no column header and so falls out of a per-column inventory; **each column's absence mask**, roughly one bit per row per nullable column; **the distinct values held once** behind a column of short codes, since the multiplication counts only the codes; and **the deep part of any column measured shallowly**, which is concentrated in whichever columns hold text or references and can exceed everything else combined. A fifth problem makes the sum itself unsafe: if two live tables share buffers, adding both totals counts those bytes twice. Report the sum, then report the additions as separate lines.

code

pseudocode · 16 lines
pseudocode
table_bytes = 0
for column in table:
    table_bytes = table_bytes + per_column_bytes(column)   # width * rows, or the deep figure

# none of the following was in the loop above
table_bytes = table_bytes + row_label_structure_bytes

for column in table:
    if column.records_absence_beside_the_value:
        table_bytes = table_bytes + row_count / 8           # one validity bit per row
    if column.stores_repeated_values_as_codes:
        table_bytes = table_bytes + value_set_held_once_bytes(column)

# and count each buffer once, not once per table that reaches it
for buffer in distinct_buffers_reachable_from(tables_in_scope):
    ...

go deeper

for a junior

Recall that adding the columns up is only the first step. A table also carries row labels and, depending on the design, a mask per column — none of which appear in any column's own figure.

for a middle

Explain each omission and put arithmetic on it: an eighth of the row count in bytes per mask, the row labels sized like any other column, the held-once values behind a coded column.

for a senior

Hand over a figure with its weakest term named. Say which columns were measured shallowly, which tables were in scope, and whether any of them share buffers — that is the difference between a number someone can plan with and one they will regret.

for a principal

Decide once, for the team, what a reported table figure means: which measurement, which scope, and whether shared buffers are attributed or deduplicated. Two engineers quoting incomparable numbers is a costlier problem than either number being slightly wrong.

## What the sum is Sizing a table starts with the obvious move: get a per-column byte figure and add them up. For a table of fixed-width numeric columns whose buffers each belong to exactly one column, that really is the table — declared width times rows, summed, finished. The reason the move is worth interrogating is that the tables people actually size are not that table. Four things sit outside the sum, and a fifth makes the sum itself unsafe. ## The four things outside the sum 1. **The row labels.** A table that carries a row-label structure pays for it. It has no column header, so it drops straight out of a per-column inventory. Its own cost follows the same rules as any column — a declared width times rows if the labels are numbers, and the whole reference-or-contiguous problem again if they are text. A table with no such structure pays nothing here, which is itself worth stating, because it is one of the honest differences between a labelled table and a plain rectangle of values. 2. **Each column's absence mask.** Where a design records absence in a validity bit beside the value rather than inside it, there is one bit per row for every column that can be absent. On a forty-column table that is forty masks, and forty times an eighth of the row count in bytes is not nothing on a wide table. 3. **The value set held once behind a coded column.** A column that keeps each distinct value once and stores a short whole number per row has two parts. Width times rows counts the codes. The distinct values themselves are a separate structure sitting beside the codes and are not in that figure at all. 4. **The per-column figures that were shallow.** Any column storing one reference per row has a per-column figure that describes its slots, not its contents. Summing shallow figures gives a shallow total, and the error is not spread evenly — it is concentrated in whichever columns hold text or separately allocated values, and it can exceed every other column put together. ## The fifth problem: counting the same bytes twice The sum assumes each buffer belongs to exactly one column of exactly one table. That assumption breaks the moment an earlier step produced a table that shares buffers with this one and is still alive. Add both tables' figures and the shared bytes appear twice, and the total is then larger than anything that exists. The fix is to count buffers rather than tables: identify the distinct buffers reachable from the tables you care about, count each one once, and say in the report which tables were in scope. ## Putting numbers on it Ten million rows, forty columns — thirty fixed-width numeric at 8 bytes, eight coded at one byte per code, two text columns held as references. | Part | Arithmetic | Bytes | |---|---|---| | 30 numeric value buffers | 8 × 10,000,000 × 30 | 2,400,000,000 | | 8 coded columns' codes | 1 × 10,000,000 × 8 | 80,000,000 | | 2 text columns, shallow | 8 × 10,000,000 × 2 | 160,000,000 | | **Naive sum** | the three lines above | **2,640,000,000** | | Row labels, if numeric | 8 × 10,000,000 | +80,000,000 | | 40 validity masks | 10,000,000 ÷ 8 × 40 | +50,000,000 | | 8 held-once value sets | small per column, but real | + | | 2 text columns, the deep part | the values themselves | + a large unknown | The first three lines are the arithmetic everyone does. The four lines below the sum are the answer's honesty. ## How to report the number 1. Say which measurement produced each per-column figure — shallow, or reference-following. Mixing the two in one sum without saying so is how the number stops meaning anything. 2. Report the sum, then report the additions as separate lines rather than folding them in. A reader can argue with a line they can see, and cannot argue with a single rolled-up figure. 3. Say which tables were in scope, and whether any of them share buffers with each other. 4. Stop at the table. This arithmetic tells you what these columns occupy; it is not a measurement of everything the program is holding while it runs, and presenting it as one invites a comparison it cannot survive. ## What a good answer sounds like "Two point six gigabytes for the column buffers, of which a hundred and sixty megabytes is two text columns measured shallowly — those two are the terms I cannot bound without following the references. Add about eighty megabytes of row labels and fifty of validity masks. So: two point seven gigabytes plus whatever the text really is, and I would measure that before anyone plans around the total." That is the answer. It has an arithmetic, it names its own weakest term out loud, and it does not pretend to be a measurement it is not. The candidate who simply says "about two and a half gigabytes" has done the same multiplication and left out the part that would have changed the decision.

  • How do you avoid double counting when two live tables share the same buffers?
    Count distinct buffers rather than tables. Walk the tables in scope, collect the buffers each one reaches, deduplicate by buffer identity, and total those. Then say in the report that the figure is per-buffer across a named set of tables, so nobody adds two of your figures together later and recreates the problem you just solved.
  • Does the sum get better or worse as the table gets wider?
    Worse in absolute terms. Every additional column brings its own absence mask, its own held-once value set if it is coded, and its own shallow-measurement error if it holds references. The row labels are paid once whatever the width, so on a very wide table they shrink to a rounding error while the per-column omissions grow linearly.
  • If every column is fixed-width numeric with no absence, is the sum the table?
    Essentially yes, apart from the row-label structure and a small fixed header per column. That is the case the simple arithmetic was built for, and it is worth saying explicitly when it applies, because it tells the reader your figure has no weak terms in it for once.

saying these in an interview costs you the question

  • Reports the column sum as the table's size without qualifying it.
  • Forgets the row labels because they carry no column header.
  • Counts a coded column's codes and ignores the values held once beside them.
  • Adds two tables' figures when the two share the same buffers.
  • Mixes shallow and reference-following figures in one total silently.
  • Presents a column inventory as a measurement of the running program.