TABLESAMPLE for random sampling in PostgreSQL - Time & Space Complexity

Time Complexity: TABLESAMPLE for random sampling

O(n)

Understanding Time Complexity

When we use TABLESAMPLE in PostgreSQL, we want to quickly get a random part of a big table.

We ask: How does the time to get this sample grow as the table gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT * FROM large_table TABLESAMPLE SYSTEM (10);
    

This query returns about 10% of rows from large_table using a fast random sampling method.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning data pages to decide which to include in the sample.
• How many times: Once over the table's data pages, not every row individually.

How Execution Grows With Input

As the table grows, the number of data pages grows, so the scan takes longer.

Input Size (rows)	Approx. Operations (pages scanned)
10,000	Small number of pages scanned
100,000	About 10 times more pages scanned
1,000,000	About 100 times more pages scanned

Pattern observation: The work grows roughly in proportion to the table size because it scans pages, not individual rows.

Final Time Complexity

Time Complexity: O(n)

This means the time to get a sample grows roughly in direct proportion to the size of the table.

Common Mistake

[X] Wrong: "TABLESAMPLE reads only the sampled rows, so time stays the same no matter table size."

[OK] Correct: The method scans data pages to decide which rows to include, so it still reads a part of the whole table, making time grow with table size.

Interview Connect

Understanding how sampling queries scale helps you explain performance trade-offs clearly and shows you know how databases handle big data efficiently.

Self-Check

"What if we used BERNOULLI sampling instead of SYSTEM? How would the time complexity change?"

Practice

1.

What is the main purpose of using TABLESAMPLE in a PostgreSQL query?

easy

A. To retrieve a random subset of rows from a table

B. To sort the table rows in random order

C. To permanently delete random rows from a table

D. To create a backup of the table

Solution

1. Step 1: Understand the purpose of TABLESAMPLE

   TABLESAMPLE is used to get a random sample of rows from a table without scanning the entire table.

2. Step 2: Compare options with TABLESAMPLE usage

   Only To retrieve a random subset of rows from a table describes retrieving a random subset of rows, which matches TABLESAMPLE's purpose.

3. Final Answer:

   To retrieve a random subset of rows from a table -> Option A

4. Quick Check:

   TABLESAMPLE = random subset retrieval [OK]

Hint: TABLESAMPLE returns random rows, not sorting or deleting [OK]

Common Mistakes:

• Confusing TABLESAMPLE with ORDER BY RANDOM()
• Thinking TABLESAMPLE deletes rows
• Assuming TABLESAMPLE creates backups

2.

Which of the following is the correct syntax to sample approximately 10% of rows from a table named employees using the BERNOULLI method?

easy

A. SELECT * FROM employees TABLESAMPLE BERNOULLI(10);

B. SELECT * FROM employees TABLESAMPLE SYSTEM(10);

C. SELECT * FROM employees SAMPLE BERNOULLI(10);

D. SELECT * FROM employees TABLESAMPLE BERNOULLI 10;

Solution

1. Step 1: Recall correct TABLESAMPLE syntax

   The correct syntax uses TABLESAMPLE followed by the method name and percentage in parentheses.

2. Step 2: Check each option

   SELECT * FROM employees TABLESAMPLE BERNOULLI(10); matches the correct syntax exactly. SELECT * FROM employees TABLESAMPLE SYSTEM(10); uses SYSTEM instead of BERNOULLI. SELECT * FROM employees SAMPLE BERNOULLI(10); misses TABLESAMPLE keyword. SELECT * FROM employees TABLESAMPLE BERNOULLI 10; misses parentheses around 10.

3. Final Answer:

   SELECT * FROM employees TABLESAMPLE BERNOULLI(10); -> Option A

4. Quick Check:

   Correct TABLESAMPLE syntax = SELECT * FROM employees TABLESAMPLE BERNOULLI(10); [OK]

Hint: Use TABLESAMPLE METHOD(percentage) with parentheses [OK]

Common Mistakes:

• Omitting TABLESAMPLE keyword
• Using wrong method name
• Missing parentheses around percentage

3.

Given a table products with 1000 rows, what is the expected approximate number of rows returned by this query?

SELECT * FROM products TABLESAMPLE SYSTEM(5);

medium

A. Exactly 5 rows

B. About 50 rows

C. About 500 rows

D. All 1000 rows

Solution

1. Step 1: Understand SYSTEM sampling percentage

   SYSTEM(5) means approximately 5% of rows are sampled.

2. Step 2: Calculate expected rows from 1000 total

   5% of 1000 is 0.05 * 1000 = 50 rows approximately.

3. Final Answer:

   About 50 rows -> Option B

4. Quick Check:

   5% of 1000 = 50 [OK]

Hint: Percentage in TABLESAMPLE is approximate row count percent [OK]

Common Mistakes:

• Confusing percentage with exact row count
• Assuming SYSTEM returns fewer rows than BERNOULLI always
• Thinking TABLESAMPLE returns all rows

4.

Identify the error in this query that tries to sample 20% of rows using BERNOULLI:

SELECT * FROM orders TABLESAMPLE BERNOULLI 20;

medium

A. TABLESAMPLE keyword is misspelled

B. BERNOULLI method cannot be used with TABLESAMPLE

C. Percentage value must be between 0 and 1

D. Missing parentheses around the percentage value

Solution

1. Step 1: Check TABLESAMPLE BERNOULLI syntax

   The percentage must be inside parentheses, like BERNOULLI(20).

2. Step 2: Identify the error in the query

   The query misses parentheses around 20, causing syntax error.

3. Final Answer:

   Missing parentheses around the percentage value -> Option D

4. Quick Check:

   Percentage needs parentheses in TABLESAMPLE [OK]

Hint: Always put percentage in parentheses after method name [OK]

Common Mistakes:

• Omitting parentheses around percentage
• Using invalid percentage range
• Misspelling TABLESAMPLE keyword

5.

You want to quickly test a query on a large table sales but need a random sample that is more uniformly random than SYSTEM sampling. Which query is best?

Options:
A) SELECT * FROM sales TABLESAMPLE SYSTEM(10);
B) SELECT * FROM sales TABLESAMPLE BERNOULLI(10);
C) SELECT * FROM sales ORDER BY RANDOM() LIMIT 100;
D) SELECT * FROM sales TABLESAMPLE SYSTEM(100);

hard

A. Use SYSTEM sampling for speed but less randomness

B. Use ORDER BY RANDOM() for perfect randomness but slower

C. Use BERNOULLI sampling for better randomness

D. Use SYSTEM sampling with 100% to get all rows

Solution

1. Step 1: Compare randomness and speed of methods

   SYSTEM is faster but less random; BERNOULLI is slower but more uniformly random.

2. Step 2: Choose best method for uniform randomness and speed

   BERNOULLI(10) gives a good balance of randomness and reasonable speed for sampling.

3. Final Answer:

   Use BERNOULLI sampling for better randomness -> Option C

4. Quick Check:

   BERNOULLI = better randomness than SYSTEM [OK]

Hint: BERNOULLI is more random; SYSTEM is faster [OK]

Common Mistakes:

• Choosing SYSTEM when better randomness is needed
• Using ORDER BY RANDOM() on large tables (slow)
• Misunderstanding 100% SYSTEM returns all rows