Work_mem and effective_cache_size tuning in PostgreSQL - Time & Space Complexity

Time Complexity: Work_mem and effective_cache_size tuning

O(n log n)

Understanding Time Complexity

When tuning PostgreSQL settings like work_mem and effective_cache_size, we want to understand how query execution time changes as data size grows.

We ask: How does memory allocation affect the speed of sorting and joining operations as input grows?

Scenario Under Consideration

Analyze the time complexity impact of this query with memory settings:

SET work_mem = '4MB';
SET effective_cache_size = '128MB';

SELECT *
FROM orders
JOIN customers ON orders.customer_id = customers.id
ORDER BY orders.order_date DESC
LIMIT 100;

This query joins two tables and sorts orders by date, using memory settings to control sorting and caching.

Identify Repeating Operations

Look at what repeats during query execution:

• Primary operation: Scanning and sorting rows from the orders table.
• How many times: Once per row in orders, plus matching rows in customers.

How Execution Grows With Input

As the number of rows in orders grows, the sorting work grows too.

Input Size (n)	Approx. Operations
10	About 10 log 10 (small sorting)
100	About 100 log 100 (more sorting work)
1000	About 1000 log 1000 (much more sorting)

Pattern observation: Sorting work grows a bit faster than the number of rows, roughly proportional to n times log n.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to sort rows grows a little faster than the number of rows, because sorting compares items multiple times.

Common Mistake

[X] Wrong: "Increasing work_mem always makes queries run in constant time regardless of data size."

[OK] Correct: More memory helps sorting fit in RAM, but sorting still needs to compare many rows, so time grows with data size.

Interview Connect

Understanding how memory settings affect query time helps you explain performance tuning clearly and confidently in real situations.

Self-Check

"What if we increased work_mem enough to hold all rows in memory? How would the time complexity change?"

Practice

1. What does the work_mem setting control in PostgreSQL?

easy

A. The amount of memory used for sorting and joining operations during query execution

B. The total memory available for caching disk pages

C. The maximum size of a database connection pool

D. The memory allocated for background worker processes

Solution

1. Step 1: Understand the role of work_mem

   work_mem is the memory PostgreSQL uses for internal operations like sorting and joining during query execution.

2. Step 2: Differentiate from other memory settings

   Other settings like effective_cache_size relate to cache estimation, not sorting or joining memory.

3. Final Answer:

   The amount of memory used for sorting and joining operations during query execution -> Option A

4. Quick Check:

   work_mem = sorting/join memory [OK]

Hint: Remember: work_mem is per operation memory for sorting/joining [OK]

Common Mistakes:

• Confusing work_mem with effective_cache_size
• Thinking work_mem controls total server memory
• Assuming work_mem affects connection limits

2. Which of the following is the correct way to set effective_cache_size to 4GB in PostgreSQL's configuration file?

easy

A. effective_cache_size = 4000MB

B. effective_cache_size = '4GB'

C. effective_cache_size = 4g

D. effective_cache_size = 4GB

Solution

1. Step 1: Check PostgreSQL config syntax for memory sizes

   PostgreSQL accepts memory sizes with units like KB, MB, GB without quotes.

2. Step 2: Validate each option

   effective_cache_size = 4GB uses correct syntax: number + unit without quotes. effective_cache_size = '4GB' uses quotes (invalid). effective_cache_size = 4000MB uses MB but 4000MB is less than 4GB. effective_cache_size = 4g uses lowercase 'g' which is invalid; units must be uppercase.

3. Final Answer:

   effective_cache_size = 4GB -> Option D

4. Quick Check:

   Config memory size = number + uppercase unit [OK]

Hint: Use number + uppercase unit without quotes for memory sizes [OK]

Common Mistakes:

• Adding quotes around memory size values
• Using lowercase units like 'g' instead of 'GB'
• Confusing MB and GB values

3. Given work_mem = '2MB' and a query performing 3 sorts simultaneously, what is the total memory PostgreSQL may use for sorting?

medium

A. 6MB

B. 3MB

C. 2MB

D. 1MB

Solution

1. Step 1: Understand work_mem usage per operation

   Each sort operation can use up to work_mem memory independently.

2. Step 2: Calculate total memory for 3 sorts

   3 sorts x 2MB each = 6MB total memory used for sorting.

3. Final Answer:

   6MB -> Option A

4. Quick Check:

   work_mem x number of sorts = total memory [OK]

Hint: Multiply work_mem by number of simultaneous operations [OK]

Common Mistakes:

• Assuming work_mem is total for all operations
• Adding instead of multiplying memory sizes
• Ignoring simultaneous operation count

4. A PostgreSQL server has effective_cache_size set too low. What problem might this cause?

medium

A. PostgreSQL will allocate too much memory for sorting operations

B. The server will crash due to memory exhaustion

C. PostgreSQL may underestimate available cache and choose inefficient query plans

D. Connections will be refused due to low cache size

Solution

1. Step 1: Understand effective_cache_size role

   This setting helps PostgreSQL estimate how much OS cache is available for data pages.

2. Step 2: Consequence of low effective_cache_size

   If set too low, PostgreSQL thinks less cache is available, so it may avoid index scans or other efficient plans, choosing slower ones.

3. Final Answer:

   PostgreSQL may underestimate available cache and choose inefficient query plans -> Option C

4. Quick Check:

   Low effective_cache_size = conservative query plans [OK]

Hint: Low effective_cache_size causes conservative, slower plans [OK]

Common Mistakes:

• Confusing effective_cache_size with work_mem
• Assuming server crashes from low effective_cache_size
• Thinking it limits connection count

5. You have a PostgreSQL server with 32GB RAM. You want to optimize work_mem and effective_cache_size for a workload with many concurrent queries doing large sorts. Which is the best tuning approach?

hard

A. Set work_mem very high (e.g., 1GB) and effective_cache_size low (e.g., 4GB)

B. Set work_mem moderately (e.g., 16MB) and effective_cache_size high (e.g., 24GB)

C. Set both work_mem and effective_cache_size very low to save memory

D. Set work_mem low (e.g., 1MB) and effective_cache_size moderate (e.g., 8GB)

Solution

1. Step 1: Balance work_mem for concurrent large sorts

   Setting work_mem too high risks memory exhaustion with many queries; moderate value like 16MB balances performance and memory use.

2. Step 2: Set effective_cache_size to reflect OS cache

   With 32GB RAM, setting effective_cache_size high (e.g., 24GB) helps PostgreSQL plan queries assuming ample cache.

3. Step 3: Evaluate other options

   Set work_mem very high (e.g., 1GB) and effective_cache_size low (e.g., 4GB) risks memory overuse; Set both work_mem and effective_cache_size very low to save memory wastes performance; Set work_mem low (e.g., 1MB) and effective_cache_size moderate (e.g., 8GB) underestimates cache and limits sort memory.

4. Final Answer:

   Set work_mem moderately (e.g., 16MB) and effective_cache_size high (e.g., 24GB) -> Option B

5. Quick Check:

   Moderate work_mem + high effective_cache_size = balanced tuning [OK]

Hint: Balance work_mem and effective_cache_size for memory and cache [OK]

Common Mistakes:

• Setting work_mem too high causing memory exhaustion
• Setting effective_cache_size too low causing bad plans
• Ignoring concurrent query memory needs