Logical replication basics in PostgreSQL - Time & Space Complexity

Time Complexity: Logical replication basics

O(n)

Understanding Time Complexity

Logical replication copies data changes from one database to another in real time.

We want to understand how the work grows as more data changes happen.

Scenario Under Consideration

Analyze the time complexity of this logical replication setup.

-- Create a publication for all tables
CREATE PUBLICATION my_pub FOR ALL TABLES;

-- Create a subscription to receive changes
CREATE SUBSCRIPTION my_sub CONNECTION 'host=source_db dbname=your_db user=your_user password=your_password' PUBLICATION my_pub;

-- Changes on source tables are sent to subscriber
-- Subscriber applies changes as they arrive

This code sets up logical replication to send all table changes from source to subscriber.

Identify Repeating Operations

Logical replication repeatedly sends and applies changes.

• Primary operation: Sending each data change (insert, update, delete) from source to subscriber.
• How many times: Once per change event, continuously as changes happen.

How Execution Grows With Input

As more changes happen, more operations are sent and applied.

Input Size (number of changes)	Approx. Operations
10	About 10 send-and-apply steps
100	About 100 send-and-apply steps
1000	About 1000 send-and-apply steps

Pattern observation: The work grows directly with the number of changes.

Final Time Complexity

Time Complexity: O(n)

This means the time to replicate grows in a straight line with the number of changes.

Common Mistake

[X] Wrong: "Logical replication sends all data every time, so time grows with table size, not changes."

[OK] Correct: Logical replication only sends new changes, so time depends on how many changes happen, not the total table size.

Interview Connect

Understanding how replication time grows helps you design systems that handle data changes efficiently.

Self-Check

"What if we replicated only specific tables instead of all tables? How would the time complexity change?"