Scan vs Query performance comparison in DynamoDB - Performance Comparison

Time Complexity: Scan vs Query performance comparison

O(n) for Scan, O(1) for Query

Understanding Time Complexity

When working with DynamoDB, it is important to know how fast your data requests run.

We want to see how the time to get data changes when using Scan versus Query.

Scenario Under Consideration

Analyze the time complexity of these DynamoDB operations.

// Query example
const paramsQuery = {
  TableName: "Users",
  KeyConditionExpression: "UserId = :id",
  ExpressionAttributeValues: { ":id": { S: "123" } }
};

// Scan example
const paramsScan = {
  TableName: "Users"
};

The Query fetches items by a specific key, while Scan reads the whole table.

Identify Repeating Operations

Look at what repeats as the table grows.

• Primary operation: Scan reads every item in the table; Query reads only matching items.
• How many times: Scan checks all items (n times); Query checks only items with the key (usually fewer).

How Execution Grows With Input

Think about how many items the database looks at as the table gets bigger.

Input Size (n)	Approx. Operations (Scan)	Approx. Operations (Query)
10	10	1-2
100	100	1-5
1000	1000	1-10

Pattern observation: Scan grows directly with table size; Query stays small if keys are selective.

Final Time Complexity

Time Complexity: O(n) for Scan, O(1) for Query

Scan time grows with table size; Query time stays mostly constant by using keys.

Common Mistake

[X] Wrong: "Query always scans the whole table like Scan."

[OK] Correct: Query uses keys to jump directly to matching items, so it does not read everything.

Interview Connect

Understanding how Scan and Query scale helps you design fast database requests and shows you know how to handle big data.

Self-Check

"What if we add a filter to Scan? How would that affect the time complexity?"