Subqueries - Correlated vs Non-Correlated, EXISTS vs IN

▶

Steps

setup

Start SeqScan on Customers

Begin scanning the Customers table to read all customer rows.

💡 Scanning Customers is the first step to access customer data for joining.

Line:

for c in customers:

💡 The scan operator reads all customers to prepare for joining with orders.

setup

Start SeqScan on Orders

Begin scanning the Orders table to read all order rows.

💡 Scanning Orders is necessary to find which customers have placed orders.

Line:

order_customer_ids = set(order['customer_id'] for order in orders)

💡 The scan operator reads all orders to prepare for joining with customers.

expand

Build Hash Table on Orders

Build a hash table keyed by customer_id from the Orders rows to enable fast join lookups.

💡 Hash table creation speeds up join by allowing quick matching of customers to orders.

Line:

order_customer_ids = set(order['customer_id'] for order in orders)

💡 Hashing orders by customer_id prepares for efficient join with customers.

compare

Probe Hash Table with Customer 1 (Alice)

Check if Customer Alice (id=1) has matching orders by probing the hash table.

💡 Probing hash table finds if a customer has any orders quickly.

Line:

if c['id'] in order_customer_ids:

💡 Alice has at least one order, so she qualifies for the output.

compare

Probe Hash Table with Customer 2 (Bob)

Check if Customer Bob (id=2) has matching orders by probing the hash table.

💡 Each customer is checked individually to determine if they have orders.

Line:

if c['id'] in order_customer_ids:

💡 Bob has orders, so he is included in the final list.

compare

Probe Hash Table with Customer 3 (Charlie)

Check if Customer Charlie (id=3) has matching orders by probing the hash table.

💡 Customers without orders are filtered out by failing the hash table probe.

Line:

if c['id'] in order_customer_ids:

💡 Charlie has no orders, so he is excluded from the final list.

fill_cells

Project Distinct Customer Names

Select distinct customer names from the join result to avoid duplicates.

💡 Projection extracts only the needed customer names, removing duplicates.

Line:

return result

💡 Distinct projection ensures each customer appears once in the output.

reconstruct

Return Final Result

Return the list of customers who have orders: Alice and Bob.

💡 Returning the final result completes the query execution.

Line:

print([c['name'] for c in res])  # ['Alice', 'Bob']

💡 The final output matches the expected customers with orders.

prune

Summary of Join Efficiency

The join avoids scanning orders multiple times by hashing once and probing for each customer.

💡 This step highlights why the join is more efficient than correlated subqueries.

Line:

# HashJoin approach avoids repeated scans

💡 HashJoin reduces complexity by building a hash table once.

reconstruct

End of Query Execution

All operators have completed; the query plan has produced the final output.

💡 This final step confirms the query plan execution is complete.

Line:

# End of function

💡 The query plan states show all operators done and final rows returned.

def customers_with_orders_join(customers, orders):  # STEP 1-2
    order_customer_ids = set(order['customer_id'] for order in orders)  # STEP 3
    result = []  # STEP 3
    for c in customers:  # STEP 4-6
        if c['id'] in order_customer_ids:  # STEP 4-6
            result.append(c)  # STEP 4-6
    return result  # STEP 7-8

if __name__ == '__main__':  # STEP 8
    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']  # STEP 8

📊

Subqueries - Correlated vs Non-Correlated, EXISTS vs IN - Watch the Algorithm Execute, Step by Step

Watching each operator activate and process rows reveals how joins efficiently combine tables and filter results, clarifying the difference between correlated and non-correlated subqueries.

Scanning Customers table to read all customer rows.

SeqScanCustomersrows≈3

SeqScanOrdersrows≈3

HashJoinCustomers.id = Orders.customer_id

ProjectionDISTINCT Customers.name

Rows processed: 3

SeqScan reads all rows from Customers for join.

Scanning Orders table to read all order rows.

SeqScanCustomersrows≈3

SeqScanOrdersrows≈3

HashJoinCustomers.id = Orders.customer_id

ProjectionDISTINCT Customers.name

Rows processed: 3

SeqScan reads all rows from Orders for join.

Building hash table on Orders keyed by customer_id for join.

SeqScanCustomersrows≈3

SeqScanOrdersrows≈3

HashJoinCustomers.id = Orders.customer_idrows≈3

ProjectionDISTINCT Customers.name

Rows processed: 0

HashJoin uses hash table on Orders for efficient matching.

Probing hash table with Customer Alice (id=1) found matching orders.

SeqScanCustomersrows≈3

SeqScanOrdersrows≈3

HashJoinCustomers.id = Orders.customer_idrows≈3

ProjectionDISTINCT Customers.name

Rows processed: 1

HashJoin probes hash table for each customer id.

Probing hash table with Customer Bob (id=2) found matching orders.

SeqScanCustomersrows≈3

SeqScanOrdersrows≈3

HashJoinCustomers.id = Orders.customer_idrows≈3

ProjectionDISTINCT Customers.name

Rows processed: 2

HashJoin probes hash table for each customer id.

Probing hash table with Customer Charlie (id=3) found no matching orders.

SeqScanCustomersrows≈3

SeqScanOrdersrows≈3

HashJoinCustomers.id = Orders.customer_idrows≈3

ProjectionDISTINCT Customers.namerows≈2

Rows processed: 2

HashJoin completed; customers without orders filtered out.

Projection completed, distinct customer names selected.

SeqScanCustomersrows≈3

SeqScanOrdersrows≈3

HashJoinCustomers.id = Orders.customer_idrows≈3

ProjectionDISTINCT Customers.namerows≈2

Rows processed: 2

Projection removes duplicates and outputs final customer list.

Final result returned: ['Alice', 'Bob']

SeqScanCustomersrows≈3

SeqScanOrdersrows≈3

HashJoinCustomers.id = Orders.customer_idrows≈3

ProjectionDISTINCT Customers.namerows≈2

Rows processed: 2

Query plan execution complete with correct output.

HashJoin efficiently matches customers to orders with one hash build.

SeqScanCustomersrows≈3

SeqScanOrdersrows≈3

HashJoinCustomers.id = Orders.customer_idrows≈3

ProjectionDISTINCT Customers.namerows≈2

Rows processed: 2

HashJoin chosen over nested loops for performance.

Query execution complete; final output ready.

SeqScanCustomersrows≈3cost=10

SeqScanOrdersrows≈3cost=15

HashJoinCustomers.id = Orders.customer_idrows≈3cost=25

ProjectionDISTINCT Customers.namerows≈2cost=5

Rows processed: 2

Final plan cost estimated at 55.0; output rows 2.

Key Takeaways

✓ Using a HashJoin efficiently matches customers to orders without repeated scans.

This insight is hard to see from code alone because the join optimization is implicit in the algorithm.

✓ Filtering customers by probing the hash table reveals how the join filters out customers without orders.

Visualizing each probe clarifies how the join condition works step-by-step.

✓ Projection removes duplicates and extracts only needed columns, finalizing the output cleanly.

Understanding projection's role is easier when seeing it as a separate operator in the plan.

Practice

1. Trace the sequence of steps the query optimizer takes when generating an explain plan for a query with a filter predicate on a large table. What happens to the cardinality estimate after applying the filter?

easy

A. The optimizer first estimates the total rows, then reduces cardinality based on filter selectivity before choosing access paths

B. The optimizer ignores filter predicates during cardinality estimation and applies them only at execution time

C. The optimizer assumes filter predicates reduce cardinality to zero if any predicate exists

D. The optimizer estimates cardinality after choosing the access path, not before

Solution

1. Step 1: Initial cardinality estimation

   The optimizer starts by estimating the total number of rows in the table.

2. Step 2: Apply filter selectivity

   It adjusts cardinality by applying the estimated selectivity of the filter predicate, reducing the row count.

3. Step 3: Use adjusted cardinality for access path selection

   The reduced cardinality informs the choice of index scans or full scans.

4. Step 4: Why other options are incorrect

   The optimizer ignores filter predicates during cardinality estimation and applies them only at execution time: Ignoring filters during estimation leads to poor plans.
   The optimizer assumes filter predicates reduce cardinality to zero if any predicate exists: Assuming zero cardinality is unrealistic and would discard valid plans.
   The optimizer estimates cardinality after choosing the access path, not before: Cardinality estimation precedes access path selection to guide it.

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   Filter predicates reduce estimated rows before access path decisions.

Hint: Filter predicates reduce cardinality estimates before access path selection.

Common Mistakes:

• Thinking filters are ignored until execution
• Assuming filters eliminate all rows
• Believing cardinality is estimated after access path choice

2. In which scenario is the Two-Phase Locking (2PL) protocol most appropriate to ensure serializability in a database system?

easy

A. When transactions require only read operations and no writes

B. When transactions involve both reads and writes and strict serializability is required

C. When transactions are short-lived and deadlocks are impossible

D. When optimistic concurrency control is preferred over locking

Solution

1. Step 1: Understand 2PL's purpose

   2PL ensures serializability by acquiring locks in a growing phase and releasing them in a shrinking phase, which is essential when transactions perform both reads and writes.

2. Step 2: Analyze each option

   A is incorrect because 2PL is not necessary if only reads occur; shared locks suffice without strict 2PL. B is unrelated as optimistic concurrency control avoids locking. C is wrong since deadlocks can occur regardless of transaction length. D correctly identifies the scenario where 2PL is most appropriate.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   2PL is designed for mixed read-write transactions requiring strict serializability.

Hint: 2PL is for mixed read-write transactions needing serializability [OK]

Common Mistakes:

• Assuming 2PL is needed for read-only transactions
• Believing short transactions cannot deadlock
• Confusing locking with optimistic concurrency

3. Which of the following is a common misconception about optimistic concurrency control in high-contention environments?

medium

A. Optimistic concurrency control always improves throughput by avoiding locks

B. It can lead to increased transaction aborts and retries under contention

C. It assumes conflicts are rare and validates data before commit

D. It reduces blocking but may increase latency due to retries

Solution

1. Step 1: Understand optimistic concurrency assumptions

   Optimistic control assumes conflicts are rare and avoids locking during transaction execution.

2. Step 2: Analyze behavior under high contention

   When conflicts are frequent, many transactions abort and retry, reducing throughput.

3. Step 3: Evaluate misconception

   Believing optimistic control always improves throughput ignores the cost of retries and aborts in high-contention scenarios.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Optimistic concurrency is beneficial mainly when conflicts are infrequent.

Hint: Optimistic concurrency shines only when conflicts are rare, not always.

Common Mistakes:

• Assuming no locks means always better performance
• Ignoring the cost of transaction retries
• Confusing optimistic validation with locking

4. Which of the following statements best describes the trade-off between lossless join and dependency preservation in database schema decomposition?

medium

A. Dependency preservation can be sacrificed to ensure lossless join, but not vice versa

B. Lossless join can be sacrificed to preserve all dependencies, especially in 3NF decompositions

C. Achieving both lossless join and dependency preservation is always possible by decomposing into BCNF

D. Neither lossless join nor dependency preservation is necessary if the schema is in 1NF

Solution

1. Step 1: Understand BCNF and 3NF

   BCNF guarantees lossless join but may lose dependency preservation; 3NF can preserve dependencies but may sacrifice lossless join.

2. Step 2: Analyze trade-offs

   Lossless join is critical to avoid spurious tuples; dependency preservation is important for enforcing constraints without joins.

3. Step 3: Evaluate options

   Dependency preservation can be sacrificed to ensure lossless join, but not vice versa correctly states the trade-off direction.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Achieving both lossless join and dependency preservation is always possible by decomposing into BCNF is false; Lossless join can be sacrificed to preserve all dependencies, especially in 3NF decompositions reverses the trade-off; Neither lossless join nor dependency preservation is necessary if the schema is in 1NF ignores normalization importance.

Hint: BCNF ensures lossless join but may lose dependencies; 3NF preserves dependencies but may sacrifice lossless join.

Common Mistakes:

• Assuming BCNF always preserves dependencies
• Believing lossless join is less important than dependency preservation
• Ignoring normalization levels and their guarantees

5. Given a relation R(A, B, C, D) with dependencies A -> B, B -> C, and C -> A, how would you approach normalization to BCNF, and what challenge arises?

hard

A. Stop at 3NF because BCNF does not handle cyclic dependencies

B. Decompose into BCNF relations easily since all dependencies have candidate keys as determinants

C. Normalization to BCNF is impossible without losing dependency preservation due to cyclic dependencies

D. Add redundant attributes to break cycles and achieve BCNF

Solution

1. Step 1: Identify cyclic dependencies

   The dependencies A -> B, B -> C, and C -> A form a cycle, meaning no single attribute is a candidate key for all dependencies.

2. Step 2: Understand BCNF decomposition challenges

   Decomposing into BCNF relations breaks the cycle but may lose dependency preservation, a known limitation when cyclic dependencies exist.

3. Step 3: Evaluate options

   Normalization to BCNF is impossible without losing dependency preservation due to cyclic dependencies correctly identifies the challenge. Decompose into BCNF relations easily since all dependencies have candidate keys as determinants ignores the cycle. Stop at 3NF because BCNF does not handle cyclic dependencies incorrectly states BCNF cannot handle cycles. Add redundant attributes to break cycles and achieve BCNF suggests an invalid approach.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Cyclic dependencies complicate BCNF normalization and dependency preservation.

Hint: Cyclic dependencies -> BCNF decomposition loses dependency preservation

Common Mistakes:

• Assuming BCNF always achievable without trade-offs
• Believing 3NF cannot handle cycles
• Trying to add attributes to fix cycles