SQL or NoSQL, and which kind

Every design keeps data somewhere. So interviewers ask: "Which database will you use, and why?" Your answer shows if you think about the data or only about tool names.

A weak answer picks a database because it is popular. It says "this kind is faster" and gives no numbers.

A strong answer first says how the app uses data. For example: "The app always reads the latest 50 messages of one chat, and about 600 messages arrive each second." Then it picks the kind of database that fits, and says what the choice costs.

At SDE-1 level you should know the main kinds of database and one use for each. At SDE-2 level you should choose with numbers and name the cost. At SDE-3 level you should also say when using two kinds of database is worth the extra work.

Think of three ways to keep records in a school office:

• A register has fixed columns. Every student has one line with the same columns. You can match a line in one register to a line in another, such as a student to a fee record.
• A folder holds everything about one student. Each folder can look different.
• A cloakroom is a counter where you leave a bag and get a token number. You hand over the token and get your bag. Nobody can ask, "which bags hold a red shirt?"

Databases work in these three ways, and in two more. First, a few words. A read looks at data. A write adds or changes data. A query is a request to a database to read or change data. In this lesson, a store means any kind of database.

An access pattern is how your app uses its data. It covers what the app looks things up by, how many items one request touches, and how many reads and writes happen each second. It also covers what else the app asks, such as sorting, searching or combining two kinds of data.

The method. Write down the three to five most important reads and writes, each with a number. Then choose the store that fits them.

Relational database (the register)

A relational database keeps data in tables. A table has columns (the fields) and rows (one item per row). An orders table has the columns id, customer_id, amount and created_at.

• The schema is the list of tables and columns with their types. The database checks it: every row has the same columns.
• A primary key is a column whose value identifies one row.
• A foreign key is a column that holds the primary key of a row in another table. Here customer_id points to a row in customers.
• A join is a query that combines rows from two tables using such a key.
• SQL (Structured Query Language) is the language for these queries.
• An index is an extra sorted list beside a table. It lets the database find rows without reading the whole table, like the index at the back of a book.
• A transaction is a group of changes that the database applies all together or not at all. When Rs 500 moves between two accounts, the debit and the credit both happen, or neither does.

It is strong when you do not know all the questions in advance: any column can be searched and any two tables joined. Its cost: when one server is not enough, it is hard to run the tables on many servers, because joins and transactions must then work across servers. Examples: Postgres, MySQL.

What "NoSQL" means

NoSQL is a general name for databases that are not relational. It is not one design. It covers the four kinds below. Each gives up something a relational database offers, such as joins. Each gets something back, such as easy ways to add servers or speed for one access pattern.

Document database (the folder)

A document is a record written in JSON (JavaScript Object Notation). JSON is a text format with names and values, such as {"name": "Paneer pizza", "price": 299}. A document can hold lists and other records inside it. A document database stores each document whole, under an id, in a collection. Documents in one collection can have different fields.

You read or write a whole document in one step, such as a restaurant's whole menu. This is strong when data is used as one unit and items have different shapes. The costs: links between documents are harder, and a fact copied into many documents must be updated in every copy. Example: MongoDB.

Key-value store (the cloakroom)

A key-value store has two main actions: put a value under a key, and get the value back by that key. The store does not look inside the value, so you cannot ask "find all carts that hold milk". It is simple, very fast, and easy to spread over servers, because the key says where the data lives. It suits shopping carts, login sessions (the record that says you are signed in) and counters. Example: Redis.

Wide-column store (one diary per person)

In a wide-column store, rows are grouped by a partition key. A partition is all the rows that share one partition key. The store keeps a partition together on one server and puts different partitions on different servers. Inside a partition, rows stay sorted by a second key, often the time.

Picture one diary per rider, with entries in time order. Reading "the last 30 minutes of one rider" is one short read from one diary. Writing is fast too. The costs: you can only ask questions that follow the partition key, and there are no joins. You make one table for each question. Example: Cassandra.

Graph database (a map of links)

A graph database stores nodes (things, such as people) and edges (links between them, such as "follows"). Its main question is a walk along the links: "friends of friends who live in Pune". In a relational database, each step of the walk is a join of a table with itself, and the work grows with each step. A graph database is built for long walks, or walks of unknown length. The costs: fewer tools, and a poor fit for plain tables. Example: Neo4j.

How to choose

Ask these questions in order:

1. What does the app look things up by: one key, a range, any column, or a walk along links?
2. Does one request need data from several kinds of items (a join)?
3. Must changes to several items succeed together (a transaction)?
4. How many writes per second, and how much data? Does it fit one server?
5. Do all items have the same fields?

If you are not sure, start with a relational database, because it answers questions you did not plan for. Change this when a number says it does not fit.

Postgres and MongoDB in one table

The two are close. Postgres can store JSON in a column of type jsonb, and MongoDB can check the shape of documents.

SwadKart is a food-delivery app. We choose a store for each kind of its data.

Assumptions (made up to teach with, not real traffic):

• 1,000,000 orders per day. The busiest time is dinner, called the peak. At the peak, orders arrive at 10 times the daily average.
• One relational database server takes about 1,000 simple writes per second. This is a low, round number to keep the arithmetic easy. Real servers often take more.
• 50,000 riders are online at dinner. Each sends its location every 5 seconds.
• 2,000,000 active carts of 1 KB each (1 KB = 1,000 bytes; 1 GB = 1,000,000 KB). Each restaurant menu has 80 dishes of 400 bytes each.

Step 1: orders and payments.

• Average = 1,000,000 / 86,400 seconds = about 12 orders per second (rounded from 11.6). Peak = 12 x 10 = 120 per second.
• Load = 120 / 1,000 = 12% of one server.
• Access pattern: "my last 10 orders", "sales per restaurant", "refund an order and its payment together". This needs joins and a transaction.
• Choice: relational.

Step 2: menus.

• One menu = 80 x 400 bytes = 32,000 bytes = 32 KB.
• Access pattern: open one restaurant, read its whole menu. A pizza has a size, a thali has a list of items, a cake has a weight. The fields differ.
• Choice: document. One read gets the menu. A relational design needs a dishes table, an options table and a join.

Step 3: carts.

• 2,000,000 x 1 KB = 2,000,000 KB = 2 GB. This is small.
• Access pattern: one user id, the whole cart, no search inside.
• Choice: key-value. This answers the predict box. A key-value store fits best. A relational database would also work, because 2 GB and one lookup by id are easy for it.

Step 4: rider locations.

• Writes = 50,000 / 5 = 10,000 per second. That is 10,000 / 1,000 = 10 times what one relational server takes (by our assumption), so the writes must be spread over many servers.
• Access pattern: add a location for one rider. Read the last 30 minutes of one rider, which is 30 x 60 / 5 = 360 locations in time order. No joins.
• Choice: wide-column. Partition key = rider id, rows sorted by time.

Step 5: referral bonus. The app pays a bonus up to 3 levels up a chain of referrals. A table of "who referred whom" answers this with 3 joins. A graph database pays off only for long chains.

Result: four kinds of store, and each is another system to run and watch. A small team could use Postgres for the rest (menus in a jsonb column) and one extra store for rider locations. Only that number is too high for one server.

• Relational. It solves questions you did not plan, rules the database checks, and all-or-nothing changes. It costs extra work when one server is not enough. I would change it when writes or data size pass what one server takes.
• Document. It solves data of different shapes read as one unit. It costs hard links between documents and many copies to update. I would change it when the app often asks across documents.
• Key-value. It solves very fast lookups by one key. It costs every other kind of question. I would change it when someone must search by something else.
• Wide-column. It solves a very high write rate and ordered reads of one partition. It costs flexible queries and joins. I would change it when new questions ignore the partition key.
• Graph. It solves long walks along links. It costs a smaller tool set. I would change it when walks stay short.

"NoSQL is faster and scales better than SQL." Not by itself. In the example, a relational server took the orders easily at 120 writes per second. Only the 10,000 writes per second of rider locations needed a different store. Speed comes from the fit between store and access pattern.

"SQL databases cannot store JSON, and NoSQL has no schema." Postgres stores and searches JSON in a jsonb column. A document database does not check a schema unless you ask. The schema then lives in your code, and every reader must handle old shapes.

"Each kind of data needs its own kind of store." Each extra store can fail. In the example, one Postgres could hold four of five data sets. Add a store only when a number makes you.

1. Name the five kinds of store in this lesson. Give one good use for each.
2. A chat app gets 3,000,000 messages per day, 200 bytes each. At the busiest time the rate is 10 times the daily average. (a) How many writes per second on average and at the peak? (b) If one relational server takes 1,000 writes per second, is one server enough?
3. A teammate wants a graph database because "users have friends". The only friend question in the app is "show my friends list". What do you say?