Column stores and the Cassandra data model

Wide-column stores and the workload behind them

Picture a messaging service: many users writing and reading small messages all day, in no particular order, and no two mailboxes alike. Page 399, "Issues with today's workloads", describes exactly this:

• "Data large and unstructured" — too big for one machine, with no fixed set of fields;
• "Lots of random reads and writes" — many small operations, not one long scan;
• "Foreign keys rarely needed" — each record is read on its own.

Its "Actual Needs": "Incremental Scalability", "Speed", "No Single point of failure", "Low cost (TCO) and admin" (TCO: total cost of ownership) and "Scale out, not up" — add ordinary machines instead of buying a bigger one (lesson 3).

Page 397 places the systems built for this among the NoSQL families of lesson 5: "Data stored in 4 types: Document, Graph, Key-value, Wide-column". Page 398, the title page of this part of the deck, reads "Big Column Stores"; the course notes explain the name: a single row can have "a huge number of different columns and that is why columnar db are also often called Big Column stores".

Page 400 recalls the CAP theorem of lesson 5 — "Consistency: all nodes have same data at any time", "Availability: the system allows operations all the time", "Partition-tolerance: the system continues to work in spite of network partitions" — and places Cassandra: "Eventual (weak) consistency, Availability, Partition-tolerance". For a mailbox that is right: a message a second late hurts nobody, a mailbox that will not open does.

"Eventual" is only the default: each read or write says how many copies must answer (the CL of section 4), so one operation can buy consistency with waiting — p. 438's "tuneably consistent" (lesson 22).

Column-oriented storage: read less, write more

Before Cassandra, pp. 401–408 describe a different design that shares the word "column". Take a chain of shops that records every sale with the five columns of p. 402: date, store, product, customer, price. The cashier adds a sale every few seconds. The analyst asks, once a night, for the revenue of each store — two of the five columns, over every sale ever made.

Page 401: "The Column Oriented Database stores data in columns", "mainly used in OLAP(online Analytical Processing), Data Mining operations". OLAP is the analyst's question: few columns, very many rows. Its opposite, OLTP (online transaction processing), is the cashier's: whole records, one at a time.

Page 402 sets the two layouts side by side. A row store keeps each record in one piece: "+ easy to add/modify a record", "- might read in unnecessary data". A column store keeps each column in a piece of its own: "+ only need to read in relevant data", "- tuple writes require multiple accesses" (a tuple is a record). Verdict: "suitable for read-mostly, read-intensive, large data repositories".

In numbers: with \(N\) records of \(m\) columns of \(w\) bytes, a query that needs \(k\) columns reads

so the column store reads the fraction \(k/m\): 2 of 8 columns, a quarter. Page 403 lists four "Pros" by name only; their mechanisms (background):

• "Data compression": a column's values share a type and repeat (below).
• "Improved Bandwidth Utilization": every byte moved belongs to a needed column.
• "Improved Code Pipelining": one tight loop over an array of one type — why a NumPy operation on a whole array beats a Python loop.
• "Improved cache locality": neighbouring values in memory are the ones read next.

The "Cons" of p. 404 are the price of cutting records apart, and the widget showed each one: "Increased Disk Seek Time" (a record lives in \(m\) files), "Increased cost of Inserts" (one record, \(m\) writes), "Increases tuple reconstruction costs" (whole records must be glued back together).

Page 405, "Tuple Reconstruction", measures the trade (Fig. 1). The row store takes the same time whatever the query selects, because it always reads whole tuples; the column store's time grows with the bytes selected and catches up only near 125 of 148. The bullet "Large prefetch hides disk seeks in columns" answers the first con: reading each column file in large chunks turns many small jumps into a few long reads.

On the right of the same slide, a box labelled Construct rebuilds the records. Position \(i\) of every column belongs to record \(i\): reconstruction is a zip by position, with no keys. And prodID is stored as the single box (4,1,4) — the value 4, from position 1, four times: the compression of the next two slides.

Page 406: compression "Trades I/O for CPU" — fewer bytes to read, a little decoding — and a scan waits for the disk, so the trade pays. Column stores profit most: "Higher data value locality in column stores" (neighbours belong to one attribute), "Techniques such as run length encoding far more useful", and the space saved "Can use extra space to store multiple copies of data in different sort orders", one per kind of query.

Page 407 encodes a sales table sorted by quarter (Fig. 2): Quarter collapses to four triples, Product ID to short runs, and Price stays raw — neighbouring prices rarely repeat, and the encoding is chosen per column.

Read one row of p. 407's table without decoding anything else:

1. A triple \((v, s, l)\) stands for \(l\) copies of \(v\) from position \(s\):

   \[ c[i] = v \quad \text{for } s \le i \le s + l - 1 \]

   (Q1, 1, 300) covers 1–300, (Q2, 301, 350) covers 301–650.

2. Each run starts where the last one ended, \(s_{j+1} = s_j + l_j\): 1 + 300 = 301, 301 + 350 = 651, 651 + 500 = 1151. The last ends at 1151 + 600 − 1 = 1750: the table has 1,750 rows.

3. Ask for row 304. It lies in 301–650: the quarter is Q2.

4. Product ID: (2, 304, 1) covers exactly 304, so the product is 2.

5. Price is raw: its 304th value. The slide's Q2 block starts at 301 with 3, 8, 1, 4, so the price is 4.

6. Zip by position: row 304 is (Q2, 2, 4) — tuple reconstruction again.

Run-length encoding needs runs. Sort the widget's sixteen sales by customer and no two neighbouring quarters are alike: sixteen runs of length 1, three times the raw column — the widget's last task.

A column store reads only the columns a query names, and pays one access per column whenever a whole record is read or written.

Page 408 closes with a "List of Databases": Cassandra, Vertica, SybaseIQ, C-Store, BigTable, MonetDB, LucidDB. Five are column stores in the sense of pp. 401–407 (C-Store, a university prototype, lives on as Vertica — background), like Snowflake (lesson 23) and Spark's columnar files (lesson 40). Cassandra and BigTable are something else.

Cassandra: Bigtable's data model on Dynamo's ring

Page 410: Cassandra was "Originally designed at Facebook" and is "Open-sourced and now within Apache foundation".

Page 411, "innovation at scale", gives the family tree. "google bigtable (2006)": "consistency model: strong", "data model: sparse map", "clones: hbase, hypertable". "amazon dynamo (2007)": "O(1) dht", "consistency model: client tune-able", "clones: riak, voldemort". In large type: "cassandra ~= bigtable + dynamo".

The data model comes from Bigtable, the distribution from Dynamo. A sparse map is a table whose rows fill only the cells they have; empty cells cost nothing. A DHT (distributed hash table) spreads keys over machines by hashing them; O(1) means any node reaches a key's owner in one hop, because every node knows the whole ring (lesson 22). The "~=" is honest: unlike Bigtable, Cassandra has no master at all.

Page 412 draws the model as the "blog keyspace" (Fig. 3): "Column Families: Like SQL tables; but may be unstructured (client-specified); Can have index tables", "No schemas", "Some columns missing from some entries", "Supports get(key) and put(key, value) operations", "Often write-heavy workloads".

Rows are found by a key — here user names. time_ordered_blogs_by_user is not an entity but an answer prepared in advance: "the entries of jbellis, in time order" is one row read. The asterisks mark secondary indexes on two columns: keep them in mind for section 4.

Pages 413–417 give the vocabulary, from the outside in:

Page 417 is the slide of the hook: "think of cassandra as row-oriented" — one key opens a row, and its columns come back together. Page 414 draws a "Row Key" pointing to pairs of "Column Keys/Names" and "Column Values"; p. 418 shows two rows of one family with different columns; p. 419 writes them as nested maps:

// p. 419: User as nested maps
User {
  123 : { email: alison@foo.com,
          icon:  [the Cassandra eye] },
  456 : { email: eben@bar.com,
          location: The Danger Zone }
}

Think of a column family as a map of maps: row key → that row's columns, sorted by name, each one a name, a value and a timestamp.

A column has three parts, a super column has columns

Zoom into one cell. Page 420, "a column has 3 parts":

The name is the key of the row's inner map: sorted, so a range of names is one contiguous read, and indexed inside the row, so a name is found without scanning. The value is opaque bytes — a string, a number, the eye picture of p. 418 — stored as it comes and never sorted.

The timestamp settles disagreements between copies. One replica of row 456 holds email = eben@bar.com with timestamp 1004, another email = eben@new.com with 1010: when they are compared, 1010 wins on both. The client supplies the clock with every write (p. 428); a delete carries one too, so it can beat an older value. Simple and fast, at a price: of two concurrent writes, one is silently lost.

The sort order is set by the column family's comparator (p. 421): "byte", "utf8", "long", "timeuuid", "lexicaluuid", "<pluggable>", "ex: lat/long" — the type of the column names. For the names 2 and 10, utf8 compares characters and puts "10" first, long compares numbers and puts 2 first; timeuuid orders time-based identifiers by time, the natural choice for a timeline.

Page 422 adds a level: "super columns group columns under a common name". A super column has a name, "name: byte[]", and instead of a value a map of columns, "cols: Map<byte[], IColumn>". A column family is standard or super (the "type" of p. 413); in a super column family every row holds super columns.

Pages 423–424 fill one: PointOfInterest, keyed by ZIP code. Row 85255 holds the super columns Phoenix Zoo and Spring Training, row 10019 Central Park and Empire State Building; each holds phone and desc — or only desc, for Central Park: "flexible schema".

// p. 424: a super column family as nested maps
PointOfInterest {
  key: 85255 {
    Phoenix Zoo { phone: 480-555-5555,
      desc: They have animals here. },
    Spring Training { phone: 623-333-3333,
      desc: Fun for baseball fans. },
  }, //end phx
  key: 10019 {
    Central Park { desc: Walk around. It's pretty.} ,
    Empire State Building { phone: 212-777-7777,
      desc: Great view from 102nd floor. }
  } //end nyc
}

Page 425: "sub-column names in a SCF are not indexed", while "top level columns (SCF Name) are always indexed" — read the parenthesis as the super column names. So one sub-column costs a read of its whole super column. Super column families are "often used for denormalizing data from standard CFs": copying data to where a query reads it.

To ask for some of a row's columns you send a slice predicate, a "data structure describing columns to return" (p. 426). Its SliceRange: "start column name", "finish column name (can be empty to stop on count)", "reverse", "count (like LIMIT)". The names are sorted, so a slice is one stretch of the row:

Pages 427–428 list the calls of the API of the time, Thrift RPC. Every call on these slides names its rows by key — one key, a list of keys or a range — never by a value, and ends with CL, the consistency level: how many replicas must answer (lesson 22). That is "tuneably consistent" in practice.

// p. 428: write one column (name, value, clock)
client.insert(userKeyBytes, parent,
    new Column("band".getBytes(UTF8),
    "Funkadelic".getBytes(), clock), CL);

The insert is p. 420 in code: name, value, clock. There is no separate update: writing an existing column stores a new value with a newer clock, and the newer clock wins.

All this is the Cassandra of 2010. Current Cassandra offers the same model through CQL tables, the language of the exercise sessions and the past papers (lesson 21); Thrift was removed in version 4.0 (2021), and super columns no longer exist. Theory questions use the slides' words, exercises the CQL ones:

No SELECT … WHERE: start from the queries

Page 429 asks "what about… SQL?" and lists five habits: SELECT, WHERE, ORDER BY, JOIN ON, GROUP. The answer is a way of designing, not a clause.

Page 430: "rdbms: domain-based model — what answers do I have?"; "cassandra: query-based model — what questions do I have?"; "Start from queries, then design the data model". A relational designer models the domain — entities, relationships, normal forms (lessons 8–9) — and answers later questions with joins. Cassandra finds rows only by key and does not join, so a question with no structure built for it has no efficient answer: you list the questions first.

Page 431, "cassandra is an index factory": the column family USER has the key UserID and the columns username, email, birth date, city, state. It answers "give me user 123" in one read, and nothing else. "How to support this query?"

-- p. 431: the query that USER, keyed by UserID, cannot answer
SELECT * FROM User WHERE city = 'Scottsdale'

The slide's answer: "Create a new CF called UserCity", keyed by city, whose columns are the "IDs of the users in that city". The query becomes one row read, plus a multiget_slice on USER for the users. UserCity "uses the Valueless Column pattern": the information is in the column names, the values are empty. What an RDBMS does with an index, you do by hand, one column family per question, written together with USER — an index factory.

In CQL (lesson 21) UserCity is a table whose partition key is the city, with the user ids as clustering values — the valueless columns:

-- UserCity of p. 431 in CQL: one partition per city
CREATE TABLE user_city (
  city text,
  user_id text,
  PRIMARY KEY ((city), user_id)
);

-- all the users of Scottsdale: one partition read
SELECT user_id FROM user_city WHERE city = 'Scottsdale';

Two conditions at once? Page 432: "Use an aggregate key" — state:city: { user1, user2} — then "Get rows between AZ: & AZ; for all Arizona users" and "Get rows between AZ:Scottsdale & AZ:Scottsdale1 for all Scottsdale users". Why do those bounds work?

1. Four rows — AZ:Phoenix, AZ:Scottsdale, AZ:Tucson, CA:Fresno — each with its users as valueless columns. Keys compare as strings, character by character, and a prefix sorts first: AZ: comes before AZ:Phoenix.

2. In ASCII the colon is 58 and the semicolon 59. Every Arizona key has a colon in third place, so it sorts before AZ;. CA:Fresno sorts after AZ; because C comes after A. So AZ: to AZ; holds exactly the Arizona rows.

3. Likewise AZ:Scottsdale1 sorts right after AZ:Scottsdale: that range holds the one Scottsdale row.

4. This needs rows in key order: the order-preserving partitioner. The random one keeps rows in the order of the MD5 of their keys — AZ:Phoenix (ab66…), AZ:Tucson (f163…), CA:Fresno (f3ca…), AZ:Scottsdale (f412…) — so a Californian row sits between Arizona rows, and "the rows between AZ: and AZ;" no longer means the Arizona users.

Page 433, "ORDER BY": "Columns are sorted according to CompareWith or CompareSubcolumnsWith" (the comparators of names and sub-column names); "Rows are placed according to their Partitioner: Random: MD5 of key; Order-Preserving: actual key". No ORDER BY clause: to get entries by time, make the time the column name. The last line needs a correction:

No slide answers JOIN ON and GROUP in words; the hotel example of pp. 434–435 (Fig. 4) answers them by design. Eight relational tables tied by foreign keys, where a hotel page needs several joins, become seven column families with no foreign keys, each shaped for the reads it serves.

The price: names, phones and rates are stored twice, and the application keeps the copies in step — affordable because writes are cheap ("very fast writes", p. 438). Pages 436–437 compare Cassandra with an RDBMS:

The rows of p. 437 are the data model in one breath: no joins, no foreign keys, duplicated data — joins and integrity checks would make nodes coordinate on every query. "Enterprise Search" and "In-Memory Database Option" describe DataStax's commercial edition, the table's source (background).

Page 438 closes with the checklist: "tuneably consistent", "very fast writes", "highly available", "fault tolerant", "linear, elastic scalability", "decentralized/symmetric", "~12 client languages", "Thrift RPC API", "~automatic provisioning of new nodes", "0(1) dht" (read O(1), as on p. 411), "big data" — the mechanisms of lesson 22.

Start from the queries: one column family per question, the data copied to where it is read, and no joins.

Back to the puzzle. "The Column Oriented Database stores data in columns" (p. 401) and "think of cassandra as row-oriented" (p. 417) are both right, because "column" means two things. In Vertica or C-Store a column is a file: one attribute of every record, stored together, compressed and scanned — OLAP. In Cassandra a column is a name in a row's sorted map, stored with the rest of its row; a row can hold a huge number of them, hence "Big Column Stores". The deck and the papers ("you decide to store it in a columnar database", exam of 12 Sep 2025) call both "columnar": keep the label, and say which one you mean.