Subqueries - Correlated vs Non-Correlated, EXISTS vs IN

🎯

Subqueries - Correlated vs Non-Correlated, EXISTS vs IN

mediumDBMSAmazonGoogleMicrosoft

Imagine you are analyzing customer orders and want to find customers who have placed orders with specific conditions. Understanding how subqueries work, especially correlated vs non-correlated, and the difference between EXISTS and IN, is crucial for writing efficient SQL queries.

💡 Subqueries are queries nested inside other queries. Beginners often struggle to understand when the inner query runs and how it relates to the outer query. This problem clarifies the difference between correlated and non-correlated subqueries and the practical implications of using EXISTS vs IN, which is essential for writing performant SQL.

📋

Problem Statement

Given two tables, Customers and Orders, write SQL queries to find customers who have placed at least one order. Implement this using both correlated and non-correlated subqueries, and using EXISTS and IN clauses. Explain the differences in execution and performance implications.

Customers table has up to 10^5 rowsOrders table has up to 10^6 rowsEach customer can have zero or more ordersSQL standard syntax assumed

💡

Example

Input"Customers: {1, 'Alice'}, {2, 'Bob'}, {3, 'Charlie'}; Orders: {101, 1}, {102, 2}, {103, 2}"

OutputCustomers with orders: Alice, Bob

Alice (id=1) has order 101, Bob (id=2) has orders 102 and 103, Charlie (id=3) has none.

• No customers in Customers table → output empty
• No orders in Orders table → output empty
• Customers with multiple orders → output each customer once
• Orders with customer_id not in Customers → ignored

⚠️

Common Mistakes

Using IN with a subquery that returns NULL values

Query may return unexpected results or exclude rows due to NULL comparison semantics

✅ Ensure subquery does not return NULLs or use EXISTS instead

Confusing correlated and non-correlated subqueries

Leads to inefficient queries or incorrect results due to misunderstanding execution order

✅ Understand that correlated subqueries depend on outer query rows and run repeatedly

Not using DISTINCT when JOIN causes duplicates

Output contains duplicate rows for customers with multiple orders

✅ Use DISTINCT or GROUP BY to eliminate duplicates

Ignoring performance implications of subqueries

Queries run slowly on large datasets, causing timeouts or resource exhaustion

✅ Prefer EXISTS or JOINs and ensure proper indexing

🧠

Brute Force (Non-Correlated Subquery with IN)

💡 This approach uses a simple non-correlated subquery with IN to check membership. It is intuitive and easy to write but can be inefficient for large datasets because the subquery executes once and the outer query scans all rows.

Intuition

Use a subquery to get all customer IDs from Orders, then select customers whose IDs are in that list.

Algorithm

1. Select all customer IDs from the Orders table.
2. Use the IN clause in the outer query to filter Customers whose IDs appear in the subquery result.
3. Return the matching customers.
4. This query runs the subquery once and then filters the outer query.

💡 The main challenge is understanding that the subquery runs independently and returns a set that the outer query uses.

</>

Code

def customers_with_orders(customers, orders):
    # customers: list of dicts with 'id' and 'name'
    # orders: list of dicts with 'order_id' and 'customer_id'
    order_customer_ids = set(order['customer_id'] for order in orders)
    result = [c for c in customers if c['id'] in order_customer_ids]
    return result

# Example usage
if __name__ == '__main__':
    customers = [{'id':1,'name':'Alice'},{'id':2,'name':'Bob'},{'id':3,'name':'Charlie'}]
    orders = [{'order_id':101,'customer_id':1},{'order_id':102,'customer_id':2},{'order_id':103,'customer_id':2}]
    res = customers_with_orders(customers, orders)
    print([c['name'] for c in res])  # ['Alice', 'Bob']

Line Notes

order_customer_ids = set(order['customer_id'] for order in orders)Extracts all customer IDs from orders to simulate the subquery result

result = [c for c in customers if c['id'] in order_customer_ids]Filters customers whose IDs appear in the subquery result

return resultReturns the filtered list of customers

print([c['name'] for c in res])Demonstrates output for verification

import java.util.*;
public class SubqueryExample {
    public static List<String> customersWithOrders(List<Customer> customers, List<Order> orders) {
        Set<Integer> orderCustomerIds = new HashSet<>();
        for (Order o : orders) {
            orderCustomerIds.add(o.customerId);
        }
        List<String> result = new ArrayList<>();
        for (Customer c : customers) {
            if (orderCustomerIds.contains(c.id)) {
                result.add(c.name);
            }
        }
        return result;
    }
    static class Customer {
        int id; String name;
        Customer(int id, String name) { this.id = id; this.name = name; }
    }
    static class Order {
        int orderId, customerId;
        Order(int orderId, int customerId) { this.orderId = orderId; this.customerId = customerId; }
    }
    public static void main(String[] args) {
        List<Customer> customers = Arrays.asList(new Customer(1,"Alice"), new Customer(2,"Bob"), new Customer(3,"Charlie"));
        List<Order> orders = Arrays.asList(new Order(101,1), new Order(102,2), new Order(103,2));
        List<String> res = customersWithOrders(customers, orders);
        System.out.println(res); // [Alice, Bob]
    }
}

Line Notes

Set<Integer> orderCustomerIds = new HashSet<>();Creates a set to hold unique customer IDs from orders

for (Order o : orders)Iterates over orders to populate the set

if (orderCustomerIds.contains(c.id))Checks if customer ID is in the set simulating IN clause

System.out.println(res);Prints the result for verification

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
struct Customer {
    int id; string name;
};
struct Order {
    int order_id; int customer_id;
};
vector<string> customersWithOrders(const vector<Customer>& customers, const vector<Order>& orders) {
    unordered_set<int> orderCustomerIds;
    for (const auto& o : orders) {
        orderCustomerIds.insert(o.customer_id);
    }
    vector<string> result;
    for (const auto& c : customers) {
        if (orderCustomerIds.find(c.id) != orderCustomerIds.end()) {
            result.push_back(c.name);
        }
    }
    return result;
}
int main() {
    vector<Customer> customers = {{1,"Alice"},{2,"Bob"},{3,"Charlie"}};
    vector<Order> orders = {{101,1},{102,2},{103,2}};
    vector<string> res = customersWithOrders(customers, orders);
    for (auto& name : res) cout << name << " ";
    cout << endl; // Alice Bob
    return 0;
}

Line Notes

unordered_set<int> orderCustomerIds;Stores unique customer IDs from orders for quick lookup

for (const auto& o : orders)Populates the set with customer IDs from orders

if (orderCustomerIds.find(c.id) != orderCustomerIds.end())Checks membership simulating IN clause

for (auto& name : res) cout << name << " ";Outputs the result for verification

function customersWithOrders(customers, orders) {
    const orderCustomerIds = new Set(orders.map(o => o.customer_id));
    return customers.filter(c => orderCustomerIds.has(c.id));
}
// Example usage
const customers = [{id:1,name:'Alice'},{id:2,name:'Bob'},{id:3,name:'Charlie'}];
const orders = [{order_id:101,customer_id:1},{order_id:102,customer_id:2},{order_id:103,customer_id:2}];
const res = customersWithOrders(customers, orders);
console.log(res.map(c => c.name)); // ['Alice', 'Bob']

Line Notes

const orderCustomerIds = new Set(orders.map(o => o.customer_id));Extracts customer IDs from orders into a set for fast lookup

return customers.filter(c => orderCustomerIds.has(c.id));Filters customers whose IDs are in the set simulating IN clause

console.log(res.map(c => c.name));Prints the filtered customer names for verification

orders.map(o => o.customer_id)Maps orders to their customer IDs to build the set

⏱

Complexity

TimeO(n + m) where n = number of customers, m = number of orders

SpaceO(m) for storing customer IDs from orders

We scan orders once to build a set, then scan customers once to filter, so linear in input size

💡 For 100,000 customers and 1,000,000 orders, this means about 1.1 million operations, which is feasible but can be slow in SQL engines without indexes.

Interview Verdict: Accepted

This approach is simple and works well for moderate data sizes but may be inefficient for very large datasets or complex queries.

🧠

Correlated Subquery with EXISTS

💡 This approach uses a correlated subquery with EXISTS, which checks for the existence of matching rows for each outer row. It is more efficient in many SQL engines because it can short-circuit and stop searching once a match is found.

Intuition

For each customer, check if there exists at least one order with that customer's ID.

Algorithm

1. For each customer in the outer query, run a subquery to check if any order exists with that customer's ID.
2. If the subquery returns any row, EXISTS evaluates to true.
3. Select customers where EXISTS is true.
4. This query runs the subquery once per outer row but can be optimized by the database engine.

💡 Understanding that the subquery depends on the outer query row is key to grasping correlated subqueries.

</>

Code

def customers_with_orders_exists(customers, orders):
    # Build a map from customer_id to orders for quick lookup
    order_map = {}
    for order in orders:
        order_map.setdefault(order['customer_id'], []).append(order)
    result = []
    for c in customers:
        if c['id'] in order_map:
            result.append(c)
    return result

# Example usage
if __name__ == '__main__':
    customers = [{'id':1,'name':'Alice'},{'id':2,'name':'Bob'},{'id':3,'name':'Charlie'}]
    orders = [{'order_id':101,'customer_id':1},{'order_id':102,'customer_id':2},{'order_id':103,'customer_id':2}]
    res = customers_with_orders_exists(customers, orders)
    print([c['name'] for c in res])  # ['Alice', 'Bob']

Line Notes

order_map = {}Prepares a dictionary to simulate quick lookup for correlated subquery

order_map.setdefault(order['customer_id'], []).append(order)Groups orders by customer_id to simulate EXISTS check

if c['id'] in order_mapChecks if any order exists for the current customer simulating EXISTS

result.append(c)Adds customer to result if condition is met

import java.util.*;
public class CorrelatedSubquery {
    public static List<String> customersWithOrdersExists(List<Customer> customers, List<Order> orders) {
        Map<Integer, List<Order>> orderMap = new HashMap<>();
        for (Order o : orders) {
            orderMap.computeIfAbsent(o.customerId, k -> new ArrayList<>()).add(o);
        }
        List<String> result = new ArrayList<>();
        for (Customer c : customers) {
            if (orderMap.containsKey(c.id)) {
                result.add(c.name);
            }
        }
        return result;
    }
    static class Customer {
        int id; String name;
        Customer(int id, String name) { this.id = id; this.name = name; }
    }
    static class Order {
        int orderId, customerId;
        Order(int orderId, int customerId) { this.orderId = orderId; this.customerId = customerId; }
    }
    public static void main(String[] args) {
        List<Customer> customers = Arrays.asList(new Customer(1,"Alice"), new Customer(2,"Bob"), new Customer(3,"Charlie"));
        List<Order> orders = Arrays.asList(new Order(101,1), new Order(102,2), new Order(103,2));
        List<String> res = customersWithOrdersExists(customers, orders);
        System.out.println(res); // [Alice, Bob]
    }
}

Line Notes

Map<Integer, List<Order>> orderMap = new HashMap<>();Creates a map to group orders by customer ID for quick lookup

orderMap.computeIfAbsent(o.customerId, k -> new ArrayList<>()).add(o);Groups orders by customer ID simulating correlated subquery

if (orderMap.containsKey(c.id))Checks existence of orders for the customer simulating EXISTS

System.out.println(res);Outputs the result for verification

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
struct Customer {
    int id; string name;
};
struct Order {
    int order_id; int customer_id;
};
vector<string> customersWithOrdersExists(const vector<Customer>& customers, const vector<Order>& orders) {
    unordered_map<int, vector<Order>> orderMap;
    for (const auto& o : orders) {
        orderMap[o.customer_id].push_back(o);
    }
    vector<string> result;
    for (const auto& c : customers) {
        if (orderMap.find(c.id) != orderMap.end()) {
            result.push_back(c.name);
        }
    }
    return result;
}
int main() {
    vector<Customer> customers = {{1,"Alice"},{2,"Bob"},{3,"Charlie"}};
    vector<Order> orders = {{101,1},{102,2},{103,2}};
    vector<string> res = customersWithOrdersExists(customers, orders);
    for (auto& name : res) cout << name << " ";
    cout << endl; // Alice Bob
    return 0;
}

Line Notes

unordered_map<int, vector<Order>> orderMap;Maps customer IDs to their orders for quick existence check

orderMap[o.customer_id].push_back(o);Groups orders by customer ID simulating correlated subquery

if (orderMap.find(c.id) != orderMap.end())Checks if any order exists for the customer simulating EXISTS

for (auto& name : res) cout << name << " ";Prints the result for verification

function customersWithOrdersExists(customers, orders) {
    const orderMap = new Map();
    for (const o of orders) {
        if (!orderMap.has(o.customer_id)) orderMap.set(o.customer_id, []);
        orderMap.get(o.customer_id).push(o);
    }
    return customers.filter(c => orderMap.has(c.id));
}
// Example usage
const customers = [{id:1,name:'Alice'},{id:2,name:'Bob'},{id:3,name:'Charlie'}];
const orders = [{order_id:101,customer_id:1},{order_id:102,customer_id:2},{order_id:103,customer_id:2}];
const res = customersWithOrdersExists(customers, orders);
console.log(res.map(c => c.name)); // ['Alice', 'Bob']

Line Notes

const orderMap = new Map();Creates a map to group orders by customer ID for quick lookup

orderMap.get(o.customer_id).push(o);Groups orders by customer ID simulating correlated subquery

return customers.filter(c => orderMap.has(c.id));Filters customers with at least one order simulating EXISTS

console.log(res.map(c => c.name));Prints the filtered customer names for verification

⏱

Complexity

TimeO(n + m) where n = number of customers, m = number of orders

SpaceO(m) for the map storing orders by customer ID

We build a map from orders and then check existence per customer, similar to approach 1 but conceptually simulates correlated subquery

💡 This approach is often more efficient in SQL engines because EXISTS can short-circuit, but in code it looks similar to approach 1.

Interview Verdict: Accepted

This approach is preferred in SQL for correlated subqueries with EXISTS due to potential optimizations.

🧠

Using JOIN for Optimal Performance

💡 Instead of subqueries, using JOINs is often the most efficient way to solve this problem in SQL. It avoids nested queries and leverages indexes and hash joins, which are optimized in database engines.

Intuition

Join Customers and Orders on customer ID, then select distinct customers who have matching orders.

Algorithm

1. Perform an INNER JOIN between Customers and Orders on customer ID.
2. Select distinct customers from the joined result to avoid duplicates.
3. Return the list of customers who have at least one order.
4. This approach leverages database join optimizations.

💡 JOINs are often faster because databases optimize them internally, unlike subqueries which may run multiple times.

</>

Code

def customers_with_orders_join(customers, orders):
    order_customer_ids = set(order['customer_id'] for order in orders)
    # Join simulation: filter customers with orders
    result = [c for c in customers if c['id'] in order_customer_ids]
    # Distinct is implicit since customers are unique
    return result

# Example usage
if __name__ == '__main__':
    customers = [{'id':1,'name':'Alice'},{'id':2,'name':'Bob'},{'id':3,'name':'Charlie'}]
    orders = [{'order_id':101,'customer_id':1},{'order_id':102,'customer_id':2},{'order_id':103,'customer_id':2}]
    res = customers_with_orders_join(customers, orders)
    print([c['name'] for c in res])  # ['Alice', 'Bob']

Line Notes

order_customer_ids = set(order['customer_id'] for order in orders)Extracts customer IDs from orders to simulate join keys

result = [c for c in customers if c['id'] in order_customer_ids]Filters customers who have matching orders simulating INNER JOIN

return resultReturns the filtered list of customers

print([c['name'] for c in res])Outputs the result for verification

import java.util.*;
public class JoinApproach {
    public static List<String> customersWithOrdersJoin(List<Customer> customers, List<Order> orders) {
        Set<Integer> orderCustomerIds = new HashSet<>();
        for (Order o : orders) {
            orderCustomerIds.add(o.customerId);
        }
        List<String> result = new ArrayList<>();
        for (Customer c : customers) {
            if (orderCustomerIds.contains(c.id)) {
                result.add(c.name);
            }
        }
        return result;
    }
    static class Customer {
        int id; String name;
        Customer(int id, String name) { this.id = id; this.name = name; }
    }
    static class Order {
        int orderId, customerId;
        Order(int orderId, int customerId) { this.orderId = orderId; this.customerId = customerId; }
    }
    public static void main(String[] args) {
        List<Customer> customers = Arrays.asList(new Customer(1,"Alice"), new Customer(2,"Bob"), new Customer(3,"Charlie"));
        List<Order> orders = Arrays.asList(new Order(101,1), new Order(102,2), new Order(103,2));
        List<String> res = customersWithOrdersJoin(customers, orders);
        System.out.println(res); // [Alice, Bob]
    }
}

Line Notes

Set<Integer> orderCustomerIds = new HashSet<>();Collects customer IDs from orders to simulate join keys

if (orderCustomerIds.contains(c.id))Filters customers who have matching orders simulating INNER JOIN

result.add(c.name);Adds matching customer names to result

System.out.println(res);Prints the result for verification

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
struct Customer {
    int id; string name;
};
struct Order {
    int order_id; int customer_id;
};
vector<string> customersWithOrdersJoin(const vector<Customer>& customers, const vector<Order>& orders) {
    unordered_set<int> orderCustomerIds;
    for (const auto& o : orders) {
        orderCustomerIds.insert(o.customer_id);
    }
    vector<string> result;
    for (const auto& c : customers) {
        if (orderCustomerIds.find(c.id) != orderCustomerIds.end()) {
            result.push_back(c.name);
        }
    }
    return result;
}
int main() {
    vector<Customer> customers = {{1,"Alice"},{2,"Bob"},{3,"Charlie"}};
    vector<Order> orders = {{101,1},{102,2},{103,2}};
    vector<string> res = customersWithOrdersJoin(customers, orders);
    for (auto& name : res) cout << name << " ";
    cout << endl; // Alice Bob
    return 0;
}

Line Notes

unordered_set<int> orderCustomerIds;Stores customer IDs from orders to simulate join keys

if (orderCustomerIds.find(c.id) != orderCustomerIds.end())Filters customers with matching orders simulating INNER JOIN

result.push_back(c.name);Adds matching customer names to result

for (auto& name : res) cout << name << " ";Prints the result for verification

function customersWithOrdersJoin(customers, orders) {
    const orderCustomerIds = new Set(orders.map(o => o.customer_id));
    return customers.filter(c => orderCustomerIds.has(c.id));
}
// Example usage
const customers = [{id:1,name:'Alice'},{id:2,name:'Bob'},{id:3,name:'Charlie'}];
const orders = [{order_id:101,customer_id:1},{order_id:102,customer_id:2},{order_id:103,customer_id:2}];
const res = customersWithOrdersJoin(customers, orders);
console.log(res.map(c => c.name)); // ['Alice', 'Bob']

Line Notes

const orderCustomerIds = new Set(orders.map(o => o.customer_id));Extracts customer IDs from orders to simulate join keys

return customers.filter(c => orderCustomerIds.has(c.id));Filters customers with matching orders simulating INNER JOIN

console.log(res.map(c => c.name));Prints the filtered customer names for verification

orders.map(o => o.customer_id)Maps orders to customer IDs for building the set

⏱

Complexity

TimeO(n + m) where n = number of customers, m = number of orders

SpaceO(m) for storing customer IDs from orders

This approach simulates an INNER JOIN by filtering customers with matching orders, which is efficient and preferred in SQL.

💡 JOINs are usually the fastest way to combine tables in SQL, especially with proper indexes.

Interview Verdict: Accepted

This is the recommended approach in interviews to demonstrate SQL knowledge and performance awareness.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, coding the JOIN approach or explaining EXISTS is best. Brute force is useful to show understanding but not for production.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Non-Correlated Subquery with IN)	O(n + m)	O(m)	No	N/A	Mention only - never code
2. Correlated Subquery with EXISTS	O(n + m)	O(m)	No	N/A	Explain and optionally code
3. Using JOIN for Optimal Performance	O(n + m)	O(m)	No	N/A	Code this approach in 95% of interviews

💼

Interview Strategy

💡 Use this guide to understand the fundamental differences between subquery types and how EXISTS and IN behave. Practice explaining these concepts clearly and writing queries in multiple ways to impress interviewers.

How to Present

Step 1: Clarify the problem and confirm table schemas.Step 2: Present the brute force approach using a non-correlated subquery with IN.Step 3: Explain correlated subqueries with EXISTS and their benefits.Step 4: Show the optimal JOIN approach and discuss performance.Step 5: Discuss edge cases and tradeoffs.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 8min → Test: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of subquery execution, SQL semantics, and query optimization strategies.

Common Follow-ups

• What is the difference in execution between EXISTS and IN? → EXISTS short-circuits, IN may scan entire subquery result.
• When would you prefer JOIN over subqueries? → When performance and readability are priorities, especially with indexes.

💡 These follow-ups check your deeper understanding of SQL optimization and practical query writing.

🔍

Pattern Recognition

When to Use

1. Need to filter rows based on existence in another table 2. Problem mentions subqueries or nested queries 3. Query involves membership testing (IN/EXISTS) 4. Performance considerations for large datasets

Signature Phrases

WHERE EXISTSWHERE IN (SELECT ...)correlated subquerynon-correlated subquery

NOT This Pattern When

Problems focusing solely on aggregation or window functions without subqueries

Similar Problems

SQL Join vs Subquery - understanding when to use eachUsing ANY vs ALL in SQL - related membership and comparison patterns

Practice

1. In which scenario is the Isolation property of ACID most critical to ensure correct database behavior?

easy

A. When a transaction must be completed entirely or not at all to avoid partial updates

B. When multiple transactions run concurrently and must not see each other's intermediate states

C. When the database must maintain integrity constraints after each transaction

D. When committed transactions must survive system crashes and power failures

Solution

1. Step 1: Understand Isolation's role

   Isolation ensures that concurrent transactions do not interfere by hiding intermediate states from each other.

2. Step 2: Analyze each option

   A describes Atomicity, C describes Consistency, D describes Durability.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Isolation is about concurrency control, so B is correct.

Hint: Isolation = hiding intermediate states during concurrency

Common Mistakes:

• Confusing Isolation with Atomicity
• Mixing Consistency with Durability

2. In which scenario is Armstrong's Axioms primarily used when working with functional dependencies in database schema design?

easy

A. To determine if a set of functional dependencies logically implies another dependency

B. To optimize SQL query execution plans based on join conditions

C. To enforce referential integrity constraints between tables

D. To normalize data by identifying candidate keys directly from data instances

Solution

1. Step 1: Understand Armstrong's Axioms purpose

   Armstrong's Axioms (Reflexivity, Augmentation, Transitivity) provide a sound and complete inference system to derive all functional dependencies implied by a given set.

2. Step 2: Analyze each option

   A is correct because Armstrong's Axioms are used to infer whether a dependency logically follows from others.
   B is incorrect because query optimization uses cost-based heuristics, not Armstrong's Axioms.
   C is incorrect as referential integrity is enforced by foreign keys, not functional dependency inference.
   D is incorrect because candidate keys are identified through closure computations, not directly from data instances or Armstrong's Axioms alone.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Armstrong's Axioms are inference rules, not enforcement or optimization tools.

Hint: Armstrong's Axioms = FD inference, not enforcement or optimization

Common Mistakes:

• Confusing FD inference with query optimization
• Thinking Armstrong's Axioms enforce constraints
• Assuming candidate keys come directly from data, not FD closure

3. In which scenario is MVCC most beneficial compared to traditional locking mechanisms in a database system?

easy

A. When strict serializability is required and no stale reads are allowed

B. When transactions are short-lived and mostly write-heavy with minimal reads

C. When many concurrent transactions perform mostly read operations with occasional writes

D. When the database workload consists primarily of batch updates with no concurrent reads

Solution

1. Step 1: Understand MVCC's strength in concurrency

   MVCC allows readers to access snapshot versions without blocking writers, making it ideal for workloads with many reads and fewer writes.

2. Step 2: Analyze write-heavy workloads

   Write-heavy workloads with minimal reads benefit less from MVCC since version maintenance overhead can be costly.

3. Step 3: Analyze batch updates without concurrent reads

   Batch updates without concurrent reads do not leverage MVCC's snapshot isolation benefits.

4. Step 4: Analyze strict serializability requirements

   MVCC provides snapshot isolation, which may allow some anomalies; strict serializability requires stronger mechanisms.

5. Final Answer:

   Option C -> Option C

6. Quick Check:

   MVCC shines in read-heavy concurrent environments [OK]

Hint: MVCC excels when many reads coexist with some writes

Common Mistakes:

• Assuming MVCC is best for write-heavy workloads
• Confusing snapshot isolation with strict serializability
• Believing MVCC is unnecessary without concurrent reads

4. Why might a B-Tree be less efficient than a B+ Tree for disk-based database indexing despite having fewer levels in some cases?

medium

A. Because B-Tree stores data in all nodes, increasing node size and causing more disk I/O per node access.

B. Because B-Tree requires more frequent rebalancing during insertions, increasing CPU overhead.

C. Because B-Tree's height is always greater than B+ Tree, leading to more disk reads.

D. Because B-Tree's internal nodes contain data, making range queries slower due to lack of leaf node linkage.

Solution

1. Step 1: Compare data storage impact on range queries

   B-Tree stores data in all nodes but lacks linked leaf nodes, making sequential range scans inefficient.

2. Step 2: Understand disk I/O implications

   Range queries in B-Tree require traversing multiple nodes without sequential access, increasing disk I/O.

3. Step 3: Analyze other options

   Because B-Tree stores data in all nodes, increasing node size and causing more disk I/O per node access. is incorrect because storing data in all nodes does not necessarily increase node size beyond B+ Tree's leaf nodes. Because B-Tree requires more frequent rebalancing during insertions, increasing CPU overhead. is misleading; both trees require rebalancing but it's not the main inefficiency. Because B-Tree's height is always greater than B+ Tree, leading to more disk reads. is false; B+ Tree height is often equal or less.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Lack of linked leaves in B-Tree slows range queries despite fewer levels.

Hint: Linked leaves -> efficient range queries; B-Tree lacks this -> slower range scans

Common Mistakes:

• Assuming fewer levels always means fewer disk I/Os
• Confusing node size impact on disk reads
• Overestimating rebalancing cost differences

5. Which of the following statements about B+ tree indexes is INCORRECT?

medium

A. B+ trees maintain keys in sorted order, enabling efficient range queries.

B. B+ trees store all data only in leaf nodes, with internal nodes storing keys for navigation.

C. B+ trees provide O(1) time complexity for equality lookups due to balanced structure.

D. B+ trees link leaf nodes to allow sequential access without traversing internal nodes.

Solution

1. Step 1: Review B+ tree properties

   B+ trees keep keys sorted, store data in leaves, and link leaves for sequential access.

2. Step 2: Analyze time complexity

   Equality lookups require O(log n) time due to tree traversal, not O(1).

3. Step 3: Evaluate distractors

   Options B, C, and D correctly describe B+ tree features.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   B+ tree equality lookup is O(log n), not O(1) [OK]

Hint: B+ tree lookup = O(log n), not O(1)

Common Mistakes:

• Confusing B+ tree lookup with hash index lookup time
• Assuming internal nodes store data
• Ignoring leaf node linkage