Bird
Raised Fist0

Design an In-Memory SQL Database - Table, Row, Column, Query Parser, Indexing

LLDhardInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Design an In-Memory SQL Database - Table, Row, Column, Query Parser, Indexing
Design a thread-safe, extensible in-memory SQL database with indexing and query parsing
hardAdvanced LLD ChallengesFreq: medium
Prerequisites:OOP FundamentalsJava ConcurrencyData StructuresDesign Patterns
⚙️
Functional Requirements
  • Support creation of tables with named columns and data types
  • Support insertion, update, and deletion of rows
  • Support SELECT queries with WHERE clause filtering
  • Support indexing on columns to speed up queries
  • Ensure thread-safe concurrent access to tables and rows
  • Provide a query parser that converts SQL strings into executable query objects
  • Allow extensibility to add new query types or index types without modifying existing code
👤
Use Cases
  • Create a new table with specified columns and data types
  • Insert rows into a table concurrently
  • Execute SELECT queries with WHERE filters and projections
  • Create and use indexes on columns for faster query execution
  • Update and delete rows based on query conditions
  • Handle concurrent read and write operations safely
🧑‍💻
Actors
  • Database Administrator
  • Application Developer
  • Concurrent Client Threads
❓
Clarifying Questions to Ask
  • How many concurrent client threads are expected to access the database?
  • Should the database support multi-version concurrency control or simple locking?
  • Is there a pricing or resource quota strategy for limiting table or row counts?
  • What are the expected data types for columns (e.g., int, string, float)?
  • How should the system handle schema changes after table creation?
  • Are indexes mandatory or optional for query execution?
  • What is the expected maximum size of tables and rows?
Out of Scope
✗ Durability and persistence to disk
✗ Distributed database features
✗ Complex SQL features like joins, transactions, or stored procedures
✗ Query optimization beyond basic indexing
⚡
QPS Calculation
read qps1000
write qps500
🖥️
Server Estimate
3
Estimates based on expected concurrent clients and data size for capacity planning.
🔢
Enumerations
enum DataType
INTEGER | STRING | FLOAT | BOOLEAN
Defines supported column data types explicitly to prevent invalid data insertion and enable type-safe operations.
enum QueryType
SELECT | INSERT | UPDATE | DELETE
Enumerates query categories to enable exhaustive switch statements in query execution and parsing.
enum IndexType
HASH | BTREE
Specifies index implementations to allow polymorphic index strategies and extensibility.
📦
Column
2 fields
private final String nameprivate final DataType dataType
Represents a column schema with a name and data type; immutable after creation.
Key Methods
public String getName()Returns the column name.
public DataType getDataType()Returns the data type of the column.
📦
Row
1 fields
private final Map<String, Object> values
Holds column-value mappings for a single row; supports thread-safe read and write of values.
Key Methods
public synchronized Object getValue(String columnName)Returns the value for the specified column in a thread-safe manner.
public synchronized void setValue(String columnName, Object value)Sets the value for the specified column with synchronization to prevent race conditions.
📦
Table
5 fields
private final String nameprivate final List<Column> columnsprivate final List<Row> rowsprivate final Map<String, Index> indexesprivate volatile boolean isLocked
Manages schema (columns), stores rows, maintains indexes, and ensures thread-safe operations on data.
Key Methods
public synchronized boolean insertRow(Row row)Inserts a row atomically, updates indexes, returns success status.
public synchronized boolean deleteRow(Row row)Deletes a row atomically and updates indexes.
public synchronized List<Row> getRows()Returns a copy of current rows to prevent concurrent modification.
public synchronized void addIndex(String columnName, Index index)Adds an index on a column; enforces Open-Closed by allowing new index types.
📦
Index
1 fields
protected final String columnName
Abstract base for indexes; defines interface for adding, removing, and querying indexed values.
Key Methods
public abstract synchronized void add(Row row)Adds a row to the index in a thread-safe manner.
public abstract synchronized void remove(Row row)Removes a row from the index safely.
public abstract synchronized List<Row> search(Object value)Returns rows matching the indexed value.
📦
HashIndex
1 fields
private final Map<Object, Set<Row>> indexMap
Concrete Index implementation using a hash map for fast equality lookups.
Key Methods
public synchronized void add(Row row)Adds row to hash bucket keyed by column value.
public synchronized void remove(Row row)Removes row from hash bucket.
public synchronized List<Row> search(Object value)Returns list of rows matching the value.
📦
Query
0 fields
Interface defining contract for executing queries on tables.
Key Methods
public List<Row> execute(Table table)Executes the query on the given table and returns matching rows.
📦
SelectQuery
2 fields
private final List<String> selectColumnsprivate final Map<String, Object> whereConditions
Implements Query interface for SELECT statements with projection and filtering.
Key Methods
public List<Row> execute(Table table)Filters rows based on whereConditions and returns projected columns.
📦
QueryParser
0 fields
Parses raw SQL strings into Query objects; extensible for new query types.
Key Methods
public Query parse(String sql)Parses the SQL string and returns a Query object.
🗄️
User
PK: user_id
user_id (INTEGER)name (STRING)email (STRING)creation_date (STRING)
🗄️
Order
PK: order_id
order_id (INTEGER)user_id (INTEGER)amount (FLOAT)order_date (STRING)
🔌
POST /tables
Request
{
  "tableName": "string",
  "columns": [
    {
      "name": "string",
      "dataType": "DataType"
    }
  ]
}
Response
{
  "success": "boolean",
  "message": "string"
}
Creates a new table with specified columns.
🔌
POST /tables/{tableName}/rows
Request
{
  "rowData": {
    "columnName": "value"
  }
}
Response
{
  "success": "boolean",
  "message": "string"
}
Inserts a new row into the specified table.
🔌
POST /query
Request
{
  "sql": "string"
}
Response
{
  "rows": [
    {
      "columnName": "value"
    }
  ],
  "success": "boolean",
  "message": "string"
}
Executes a SQL query and returns matching rows.

Practice

(1/5)
1. In the brokerage system, should the Order entity be designed as an abstract class or an interface? Consider that orders have common state fields like orderId and timestamp, but different types of orders have distinct execution logic.
easy
A. Abstract class, because it can hold shared state and provide default implementations for common behavior.
B. Interface, because Java 8+ interfaces can have default methods and fields for state.
C. Interface, because it allows multiple inheritance and enforces method signatures without state.
D. Abstract class, because it forces all subclasses to implement all methods explicitly.

Solution

  1. Step 1: Analyze state vs behavior requirements

    Orders share common state fields like orderId and timestamp, which require storage and possibly shared methods.

  2. Step 2: Why abstract class fits better

    Abstract classes can hold state and provide default method implementations, reducing code duplication. Interfaces cannot hold instance state.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Shared state + default behavior -> abstract class [check]
Hint: Stateful base class -> abstract class, not interface [check]
Common Mistakes:
2. In the Blackjack game, if the placeBet() method is not synchronized, which exact thread interleaving causes a player to double-bet?
medium
A. Thread 1 places bet, Thread 2 waits for Thread 1 to finish, then places bet safely
B. Thread 1 reads balance, Thread 2 reads balance, both update balance simultaneously without conflict
C. Thread 1 checks balance sufficient -> true, context switch, Thread 2 checks balance sufficient -> true, both place bets reducing balance incorrectly
D. Thread 1 and Thread 2 both fail to update balance due to deadlock

Solution

  1. Step 1: Identify check-then-act race condition

    Without synchronization, Thread 1 reads balance sufficient and is preempted before updating; Thread 2 also reads balance sufficient and proceeds.

  2. Step 2: Both threads place bets reducing balance twice, causing double-bet

    This classic check-then-act gap leads to inconsistent state and double deduction.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Unsynchronized check-then-act -> double bet race condition [check]
Hint: Check balance -> context switch -> both bet -> double deduction [check]
Common Mistakes:
3. In the Tic-Tac-Toe game server, the makeMove() method is not synchronized. Which exact sequence of events between Thread 1 and Thread 2 can cause two players to place their marks on the same cell (double-booking)?
medium
A. Thread 1 and Thread 2 both call makeMove() but on different board instances.
B. Thread 1 reads cell as empty, Thread 2 reads cell as occupied, both proceed to write.
C. Thread 1 locks the board, Thread 2 waits, then both mark different cells simultaneously.
D. Thread 1 checks cell is empty -> true, context switch before marking; Thread 2 checks cell is empty -> true, both mark cell concurrently.

Solution

  1. Step 1: Identify the race condition in makeMove()

    Without synchronization, the check-then-act sequence is vulnerable: Thread 1 checks if cell is empty and is preempted before marking.

  2. Step 2: Trace Thread 2's actions

    Thread 2 also checks the same cell, sees it empty, and proceeds to mark it. Both threads mark the same cell, causing double-booking.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Check-then-act gap without sync -> double-booking race [check]
Hint: Check empty -> context switch -> both mark same cell [check]
Common Mistakes:
4. In a Singleton class without synchronized on getInstance(), what EXACT sequence of Thread 1 and Thread 2 calls can cause two instances to be created?
medium
A. Thread 1 checks instance == null -> true, context switch before creation; Thread 2 checks instance == null -> true, both create separate instances.
B. Thread 1 calls getInstance(), completes instance creation; Thread 2 calls getInstance() and returns same instance.
C. Thread 1 calls getInstance() twice in a row; Thread 2 waits until Thread 1 finishes.
D. Thread 1 and Thread 2 both call getInstance() after instance is created, returning the same instance.

Solution

  1. Step 1: Identify the check-then-act race condition

    Without synchronization, both threads can see instance == null before either creates it.

  2. Step 2: Trace thread interleaving

    Thread 1 checks instance == null -> true, context switch before creating instance. Thread 2 also checks instance == null -> true, proceeds to create a second instance, causing double instantiation.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Unsynchronized lazy init -> check-then-act race causes two instances [check]
Hint: Check-then-act without sync -> double instance creation [check]
Common Mistakes:
5. In a parking lot system, if parkVehicle() is not synchronized, which exact thread interleaving causes double-booking of the same spot?
medium
A. Thread 1 checks spot availability -> true, context switch; Thread 2 checks availability -> true; both park simultaneously.
B. Thread 1 parks vehicle, Thread 2 parks vehicle after Thread 1 finishes.
C. Thread 1 parks vehicle, Thread 2 waits for lock release before parking.
D. Thread 1 releases spot, Thread 2 immediately occupies it without checking.

Solution

  1. Step 1: Identify the check-then-act race condition

    Without synchronization, Thread 1 reads spot as available but before marking it occupied, context switches to Thread 2 which also reads available.

  2. Step 2: Both threads proceed to park, causing double-booking

    Both threads believe the spot is free and park simultaneously, violating mutual exclusion.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Check-then-act gap without synchronization -> double-booking [check]
Hint: Check availability -> context switch -> both park -> double-booking [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard