BigQuery for analytics in GCP - Time & Space Complexity

Time Complexity: BigQuery for analytics

O(n)

Understanding Time Complexity

When using BigQuery for analytics, it is important to understand how query execution time changes as the amount of data grows.

We want to know how the time to get results changes when we analyze bigger datasets.

Scenario Under Consideration

Analyze the time complexity of the following BigQuery SQL query.

SELECT user_id, COUNT(*) AS session_count
FROM `project.dataset.sessions`
WHERE event_date BETWEEN '2024-01-01' AND '2024-01-31'
GROUP BY user_id
ORDER BY session_count DESC
LIMIT 100
    

This query counts user sessions in January 2024, groups by user, and returns the top 100 users with the most sessions.

Identify Repeating Operations

Look at what happens repeatedly during query execution.

• Primary operation: Scanning rows in the sessions table that match the date filter.
• How many times: Once over all matching rows, which depends on how many sessions happened in January.
• Secondary operation: Grouping rows by user_id and counting sessions per user.
• How many times: Once per unique user in the filtered data.

How Execution Grows With Input

As the number of sessions in January grows, the query scans more rows and groups more data.

Input Size (n)	Approx. Api Calls/Operations
10,000 sessions	Scan 10,000 rows, group by users in those rows
100,000 sessions	Scan 100,000 rows, group by users in those rows
1,000,000 sessions	Scan 1,000,000 rows, group by users in those rows

Pattern observation: The work grows roughly in direct proportion to the number of sessions scanned.

Final Time Complexity

Time Complexity: O(n)

This means the query time grows linearly with the number of rows scanned in the filtered data.

Common Mistake

[X] Wrong: "Adding a LIMIT 100 means the query only looks at 100 rows, so it runs fast regardless of data size."

[OK] Correct: The LIMIT applies after scanning and grouping all matching rows, so the query still processes all relevant data before limiting results.

Interview Connect

Understanding how BigQuery processes data helps you explain performance trade-offs clearly and shows you can think about cost and speed in cloud analytics.

Self-Check

"What if we added a filter on user_id to only include a small subset? How would the time complexity change?"

Practice

1. What is the main purpose of Google BigQuery in data analytics?

easy

A. To run fast SQL queries on large datasets without managing servers

B. To store files like images and videos

C. To create virtual machines for computing

D. To send emails automatically

Solution

1. Step 1: Understand BigQuery's role

   BigQuery is designed to analyze large amounts of data quickly using SQL without needing to manage servers.

2. Step 2: Compare options

   Options A, C, and D describe other services unrelated to BigQuery's main function.

3. Final Answer:

   To run fast SQL queries on large datasets without managing servers -> Option A

4. Quick Check:

   BigQuery = fast SQL analytics [OK]

Hint: BigQuery = fast SQL on big data, no servers needed [OK]

Common Mistakes:

• Confusing BigQuery with storage or compute services
• Thinking BigQuery manages virtual machines
• Assuming BigQuery sends emails

2. Which of the following is the correct syntax to select all columns from a table named sales_data in BigQuery?

easy

A. FETCH * sales_data;

B. GET ALL FROM sales_data;

C. SELECT * FROM sales_data;

D. SELECT ALL COLUMNS sales_data;

Solution

1. Step 1: Recall SQL SELECT syntax

   The correct SQL syntax to select all columns is SELECT * FROM table_name;.

2. Step 2: Check each option

   Only SELECT * FROM sales_data; matches the correct SQL syntax. Options A, B, and D use incorrect keywords or structure.

3. Final Answer:

   SELECT * FROM sales_data; -> Option C

4. Quick Check:

   SELECT * FROM table = correct syntax [OK]

Hint: Use SELECT * FROM table to get all columns [OK]

Common Mistakes:

• Using wrong keywords like GET or FETCH
• Omitting FROM keyword
• Writing SELECT ALL COLUMNS instead of SELECT *

3. Given the table orders with columns order_id, customer_id, and amount, what will this query return?

SELECT customer_id, SUM(amount) AS total_spent FROM orders GROUP BY customer_id ORDER BY total_spent DESC LIMIT 2;

medium

A. All orders sorted by amount

B. Top 2 customers who spent the most money

C. Total amount spent by all customers combined

D. First 2 orders by order_id

Solution

1. Step 1: Understand the query components

   The query groups orders by customer_id, sums the amount per customer, orders results by total spent descending, and limits output to 2 rows.

2. Step 2: Interpret the output

   This returns the top 2 customers who spent the most money.

3. Final Answer:

   Top 2 customers who spent the most money -> Option B

4. Quick Check:

   GROUP BY customer_id + SUM + ORDER BY DESC + LIMIT 2 = top 2 spenders [OK]

Hint: GROUP BY + SUM + ORDER BY DESC + LIMIT = top results [OK]

Common Mistakes:

• Thinking it returns all orders instead of grouped data
• Confusing LIMIT with total sum
• Ignoring ORDER BY direction

4. You wrote this query but get an error:

SELECT customer_id, amount FROM orders WHERE SUM(amount) > 100;

What is the problem?

medium

A. SELECT must include all columns in WHERE

B. Missing GROUP BY clause for customer_id

C. amount column does not exist

D. SUM() cannot be used in WHERE clause; use HAVING instead

Solution

1. Step 1: Identify misuse of SUM() in WHERE

   Aggregate functions like SUM() cannot be used in WHERE; they belong in HAVING clause.

2. Step 2: Correct usage

   Replace WHERE SUM(amount) > 100 with HAVING SUM(amount) > 100 and add GROUP BY customer_id.

3. Final Answer:

   SUM() cannot be used in WHERE clause; use HAVING instead -> Option D

4. Quick Check:

   Aggregates in HAVING, not WHERE [OK]

Hint: Use HAVING for conditions on aggregates, not WHERE [OK]

Common Mistakes:

• Using SUM() in WHERE clause
• Forgetting GROUP BY with aggregates
• Assuming WHERE filters aggregates

5. You want to find the average order amount per customer but only for customers who placed more than 5 orders. Which query correctly achieves this in BigQuery?

hard

A. SELECT customer_id, AVG(amount) AS avg_amount FROM orders GROUP BY customer_id HAVING COUNT(order_id) > 5;

B. SELECT customer_id, AVG(amount) AS avg_amount FROM orders WHERE COUNT(order_id) > 5 GROUP BY customer_id;

C. SELECT customer_id, AVG(amount) AS avg_amount FROM orders WHERE order_count > 5;

D. SELECT customer_id, AVG(amount) AS avg_amount FROM orders GROUP BY customer_id WHERE COUNT(order_id) > 5;

Solution

1. Step 1: Understand filtering on aggregate

   To filter groups by count, use HAVING clause after GROUP BY.

2. Step 2: Check each option's correctness

   SELECT customer_id, AVG(amount) AS avg_amount FROM orders GROUP BY customer_id HAVING COUNT(order_id) > 5; uses GROUP BY customer_id and HAVING COUNT(order_id) > 5 correctly. Options A, B, and C misuse WHERE or clause order.

3. Final Answer:

   SELECT customer_id, AVG(amount) AS avg_amount FROM orders GROUP BY customer_id HAVING COUNT(order_id) > 5; -> Option A

4. Quick Check:

   HAVING filters groups, WHERE filters rows [OK]

Hint: Use HAVING to filter groups after GROUP BY [OK]

Common Mistakes:

• Using WHERE to filter aggregates
• Placing WHERE after GROUP BY
• Referencing undefined columns like order_count