Query Optimization - Explain Plan, Cost Estimation, Cardinality

▶

Steps

setup

Initialize Explain Plan Tree

The optimizer initializes the explain plan as an empty B-tree with order 3, preparing to insert query operations as nodes.

💡 Setting up the tree structure is essential to organize query operations hierarchically for cost estimation.

Line:

plan_tree = BTree(order=3)
plan_tree.root = plan_tree.create_node(is_leaf=True)

💡 The explain plan starts empty and will grow as operations are added.

insert

Insert Scan Operation Node

Insert a leaf node representing a table scan operation with estimated cardinality 1000 and cost 10.

💡 Leaf nodes represent base operations like scans, which are the foundation for cost estimation.

Line:

plan_tree.insert(1, {'operation': 'scan', 'cardinality': 1000, 'cost': 10})

💡 Scan operations have fixed cost and cardinality, forming the leaves of the plan tree.

insert

Insert Filter Operation Node

Insert a filter operation node with estimated cardinality 500 and cost 5, refining the scan results.

💡 Filters reduce cardinality and add cost, affecting downstream operations.

Line:

plan_tree.insert(1, {'operation': 'filter', 'cardinality': 500, 'cost': 5})

💡 Filters prune data early, lowering cardinality and cost for subsequent operations.

insert

Insert Join Operation Node - Causes Split

Insert a join operation node with estimated cardinality 200 and cost 50, causing the root node to exceed max keys and trigger a split.

💡 Joins are costly and often cause tree restructuring due to their complexity.

Line:

plan_tree.insert(1, {'operation': 'join', 'cardinality': 200, 'cost': 50})

💡 Node splits maintain B-tree balance and keep operations organized hierarchically.

traverse

Traverse to Left Child for Cost Estimation

Traverse down to the left child node to estimate costs and cardinalities for the filter operation subtree.

💡 Cost estimation requires visiting child nodes to aggregate their metrics.

Line:

node = plan_tree.get_child(1, 0)  # left child

💡 Traversal allows bottom-up cost aggregation in the plan tree.

compare

Estimate Cost and Cardinality at Filter Node

Calculate the total cost and cardinality for the filter node, confirming the estimated values.

💡 Accurate cost and cardinality estimation at each node guides query plan selection.

Line:

filter_cost = 5
filter_cardinality = 500

💡 Filter reduces cardinality and adds cost, impacting parent join cost.

traverse

Traverse to Right Child for Cost Estimation

Traverse to the right child node to estimate costs and cardinalities for the scan operation subtree.

💡 Both children must be evaluated to estimate join cost accurately.

Line:

node = plan_tree.get_child(1, 1)  # right child

💡 Traversal ensures all subtrees contribute to the overall plan cost.

compare

Estimate Cost and Cardinality at Scan Node

Confirm the cost and cardinality for the scan node, which will be used in join cost calculation.

💡 Leaf node metrics are the base for higher-level operation cost calculations.

Line:

scan_cost = 10
scan_cardinality = 1000

💡 Scan node cost and cardinality are inputs to join cost estimation.

compare

Calculate Join Node Cost and Cardinality

Aggregate costs and cardinalities from child nodes to estimate join node metrics.

💡 Join cost depends on child costs and cardinalities; accurate aggregation is key.

Line:

join_cost = filter_cost + scan_cost + 35  # join overhead
join_cardinality = 200

💡 Join operation reduces cardinality but adds significant cost overhead.

traverse

Finalize Explain Plan and Output

The optimizer finalizes the explain plan tree with all cost and cardinality estimates, ready for query execution planning.

💡 Finalizing the plan confirms the best cost estimates for query execution.

Line:

return plan_tree

💡 The explain plan tree summarizes the query cost structure for optimization decisions.

class BTreeNode:
    def __init__(self, is_leaf):
        self.keys = []  # list of dicts with operation, cardinality, cost
        self.children = [None]*4  # max 4 children for order 3
        self.is_leaf = is_leaf
        self.parent = None

class BTree:
    def __init__(self, order=3):
        self.order = order
        self.root = self.create_node(is_leaf=True)  # STEP 1

    def create_node(self, is_leaf):
        return BTreeNode(is_leaf)

    def insert(self, node_id, operation_info):
        # Simplified insert for demo
        node = self.root
        node.keys.append(operation_info)  # STEP 2,3,4
        node.keys.sort(key=lambda k: k['cost'])
        if len(node.keys) > self.order:
            self.split(node)  # STEP 4

    def split(self, node):
        mid = len(node.keys)//2
        promoted = node.keys[mid]
        left_keys = node.keys[:mid]
        right_keys = node.keys[mid+1:]

        left_node = self.create_node(node.is_leaf)  # STEP 4
        right_node = self.create_node(node.is_leaf)
        left_node.keys = left_keys
        right_node.keys = right_keys

        if node.parent is None:
            new_root = self.create_node(False)
            new_root.keys = [promoted]
            new_root.children[0] = left_node
            new_root.children[1] = right_node
            self.root = new_root
            left_node.parent = new_root
            right_node.parent = new_root
        else:
            # For simplicity, assume root split only
            pass

    def get_child(self, node_id, index):
        return self.root.children[index]  # STEP 5,7

# Usage
plan_tree = BTree(order=3)  # STEP 1
plan_tree.insert(1, {'operation': 'scan', 'cardinality': 1000, 'cost': 10})  # STEP 2
plan_tree.insert(1, {'operation': 'filter', 'cardinality': 500, 'cost': 5})  # STEP 3
plan_tree.insert(1, {'operation': 'join', 'cardinality': 200, 'cost': 50})  # STEP 4

# Traversals and cost estimations (conceptual)
filter_node = plan_tree.get_child(1, 0)  # STEP 5
scan_node = plan_tree.get_child(1, 1)    # STEP 7

filter_cost = 5  # STEP 6
filter_cardinality = 500
scan_cost = 10   # STEP 8
scan_cardinality = 1000
join_cost = filter_cost + scan_cost + 35  # STEP 9
join_cardinality = 200

# Final plan ready
final_plan = plan_tree  # STEP 10

📊

Query Optimization - Explain Plan, Cost Estimation, Cardinality - Watch the Algorithm Execute, Step by Step

Watching the algorithm execute visually helps you understand how query plans are constructed and optimized, revealing the interplay between cost estimation and cardinality at each node.

insert

leaf

Initialized empty explain plan tree with root node.

insertKey: {"operation":"scan","cardinality":1000,"cost":10}

{"operation":"scan","cardinality":1000,"cost":10}

leaf

Inserted scan operation node with cardinality 1000 and cost 10.

insertKey: {"operation":"filter","cardinality":500,"cost":5}

{"operation":"filter","cardinality":500,"cost":5}{"operation":"scan","cardinality":1000,"cost":10}

leaf

Inserted filter operation node with cardinality 500 and cost 5.

splitKey: {"operation":"join","cardinality":200,"cost":50}↑ promoted: {"operation":"join","cardinality":200,"cost":50}

{"operation":"join","cardinality":200,"cost":50}

{"operation":"filter","cardinality":500,"cost":5}

leaf

{"operation":"scan","cardinality":1000,"cost":10}

leaf

Root node split due to join insertion; join key promoted.

traverseKey: {"operation":"filter","cardinality":500,"cost":5}

{"operation":"join","cardinality":200,"cost":50}

{"operation":"filter","cardinality":500,"cost":5}

leaf

{"operation":"scan","cardinality":1000,"cost":10}

leaf

Traversing left child node to estimate filter subtree cost.

compareKey: {"operation":"filter","cardinality":500,"cost":5}

{"operation":"join","cardinality":200,"cost":50}

{"operation":"filter","cardinality":500,"cost":5}

leaf

{"operation":"scan","cardinality":1000,"cost":10}

leaf

Confirmed cost and cardinality at filter node.

traverseKey: {"operation":"scan","cardinality":1000,"cost":10}

{"operation":"join","cardinality":200,"cost":50}

{"operation":"filter","cardinality":500,"cost":5}

leaf

{"operation":"scan","cardinality":1000,"cost":10}

leaf

Traversing right child node to estimate scan subtree cost.

compareKey: {"operation":"scan","cardinality":1000,"cost":10}

{"operation":"join","cardinality":200,"cost":50}

{"operation":"filter","cardinality":500,"cost":5}

leaf

{"operation":"scan","cardinality":1000,"cost":10}

leaf

Confirmed cost and cardinality at scan node.

compareKey: {"operation":"join","cardinality":200,"cost":50}

{"operation":"join","cardinality":200,"cost":50}

{"operation":"filter","cardinality":500,"cost":5}

leaf

{"operation":"scan","cardinality":1000,"cost":10}

leaf

Calculated join node cost and cardinality from children.

traverse

{"operation":"join","cardinality":200,"cost":50}

{"operation":"filter","cardinality":500,"cost":5}

leaf

{"operation":"scan","cardinality":1000,"cost":10}

leaf

Explain plan finalized with all cost and cardinality estimates.

Key Takeaways

✓ Query optimization builds a hierarchical explain plan using a B-tree structure to organize operations.

This hierarchical structure is hard to grasp from code alone but becomes clear when visualized step-by-step.

✓ Cost and cardinality estimates propagate bottom-up, with leaf nodes providing base metrics and parent nodes aggregating them.

Understanding how these metrics accumulate is easier when you see each node's calculation in the tree.

✓ Node splits maintain balance in the explain plan tree, ensuring efficient organization of query operations.

The decision to split and promote keys is subtle in code but visually obvious in the tree structure.

Practice

1. In a database system that requires efficient range queries on large datasets stored on disk, which tree structure is most suitable and why?

easy

A. B+ Tree, because all data records are stored in leaf nodes linked sequentially, optimizing range scans.

B. B-Tree, because it stores keys and data in all nodes, allowing faster point queries.

C. B-Tree, because it reduces the height of the tree by storing data only in internal nodes.

D. B+ Tree, because it stores data only in internal nodes, minimizing disk I/O for all queries.

Solution

1. Step 1: Understand data storage in B-Tree vs B+ Tree

   B-Tree stores keys and data in all nodes, while B+ Tree stores data only in leaf nodes, which are linked sequentially.

2. Step 2: Consider range query efficiency

   Range queries benefit from sequential access to data, which B+ Tree's linked leaf nodes provide, reducing disk I/O.

3. Step 3: Analyze why other options are incorrect

   B-Tree, because it stores keys and data in all nodes, allowing faster point queries. is incorrect because storing data in all nodes does not optimize range queries. B-Tree, because it reduces the height of the tree by storing data only in internal nodes. is wrong as B-Trees store data in all nodes, not only internal nodes. B+ Tree, because it stores data only in internal nodes, minimizing disk I/O for all queries. incorrectly states B+ Tree stores data only in internal nodes.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   B+ Tree's leaf-level linked list is key for efficient range queries.

Hint: B+ Tree's linked leaves -> efficient range scans

Common Mistakes:

• Confusing where data is stored in B-Tree vs B+ Tree
• Assuming data in internal nodes always speeds up queries
• Ignoring the impact of leaf node linkage on range queries

2. In a high-concurrency OLTP system where multiple transactions frequently update different rows of the same table, which locking strategy is most appropriate to maximize throughput while maintaining consistency?

easy

A. Table-level locking to ensure simplicity and avoid deadlocks

B. Row-level locking to allow concurrent updates on different rows

C. No locking, relying solely on optimistic concurrency control

D. Page-level locking to balance granularity and overhead

Solution

1. Step 1: Understand the concurrency needs

   High concurrency with frequent updates on different rows requires fine-grained locking to avoid unnecessary blocking.

2. Step 2: Evaluate locking granularity

   Table-level locking (B) is too coarse and reduces concurrency. Page-level locking (D) is intermediate but still blocks unrelated rows. No locking (C) with optimistic control risks conflicts and rollbacks under high contention.

3. Step 3: Confirm best strategy

   Row-level locking (A) allows multiple transactions to update different rows simultaneously, maximizing throughput while preserving consistency.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Row-level locking allows multiple transactions to update different rows simultaneously, maximizing throughput while preserving consistency.

Hint: Use row-level locks when many transactions update different rows concurrently.

Common Mistakes:

• Assuming table-level locking is always simpler and better
• Believing optimistic concurrency always outperforms locking
• Confusing page-level locking benefits

3. Suppose a database uses snapshot isolation to handle concurrent transactions. Which scenario can still violate Consistency despite snapshot isolation, and why?

hard

A. A transaction commits without flushing changes to disk, violating durability.

B. Two concurrent transactions update different rows, causing no conflicts and preserving consistency.

C. A transaction reads uncommitted data from another transaction, causing dirty reads.

D. Two concurrent transactions read the same snapshot and update overlapping data, leading to write skew anomalies.

Solution

1. Step 1: Understand snapshot isolation

   Snapshot isolation prevents many anomalies but can allow write skew, where concurrent transactions read the same snapshot and update overlapping data inconsistently.

2. Step 2: Analyze options

   A describes the write skew anomaly possible under snapshot isolation. B is safe and consistent. C describes read uncommitted, not snapshot isolation. D relates to durability, not consistency.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Write skew under snapshot isolation can violate consistency.

Hint: Snapshot isolation can allow write skew anomalies

Common Mistakes:

• Assuming snapshot isolation prevents all anomalies
• Confusing dirty reads with snapshot isolation behavior

4. Suppose you want to extend the SQL query execution simulation to handle queries where LIMIT is applied without an ORDER BY clause. Which of the following statements about the behavior of LIMIT in this case is correct, and what adjustment should be made to the simulation to reflect real SQL behavior?

hard

A. LIMIT cannot be used without ORDER BY; simulation should raise an error if ORDER BY is missing.

B. LIMIT returns an arbitrary subset of rows without ORDER BY; simulation should note LIMIT applies after FROM and WHERE but before ORDER BY.

C. LIMIT always returns the first N rows sorted by default; no change needed in simulation.

D. LIMIT returns arbitrary rows without ORDER BY; simulation should reflect that LIMIT applies last but does not guarantee order.

Solution

1. Step 1: Understand LIMIT behavior without ORDER BY

   Without ORDER BY, LIMIT returns an arbitrary subset of rows, not sorted, so results may be inconsistent.

2. Step 2: Adjust simulation to reflect logical execution

   Simulation should keep LIMIT as the last clause executed but clarify it does not guarantee sorted output without ORDER BY.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   LIMIT applies last but unordered without ORDER BY [OK]

Hint: LIMIT without ORDER BY returns arbitrary rows [OK]

Common Mistakes:

• Assuming LIMIT sorts rows by default

5. In a geo-distributed NoSQL system designed for high availability and partition tolerance, an application requires strict consistency for a subset of critical transactions. Which approach best addresses this requirement without sacrificing overall system availability?

hard

A. Switch the entire system to a strongly consistent SQL database cluster

B. Accept eventual consistency for all transactions to maintain availability

C. Implement a hybrid approach using multi-model databases or selective consistency zones for critical data

D. Use synchronous replication across all nodes for all data to guarantee consistency

Solution

1. Step 1: Understand system constraints

   The system is geo-distributed, prioritizing availability and partition tolerance, but needs strict consistency for some transactions.

2. Step 2: Evaluate options

   Switch the entire system to a strongly consistent SQL database cluster sacrifices availability globally, which is undesirable. Accept eventual consistency for all transactions to maintain availability ignores strict consistency needs. Use synchronous replication across all nodes for all data to guarantee consistency sacrifices availability due to synchronous replication delays.

3. Step 3: Hybrid solution

   Implement a hybrid approach using multi-model databases or selective consistency zones for critical data proposes selective consistency zones or multi-model databases, allowing critical transactions to be strongly consistent while maintaining availability elsewhere.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Hybrid approaches balance consistency and availability per data criticality [OK]

Hint: Hybrid selective consistency zones enable strict consistency without losing availability globally

Common Mistakes:

• Thinking entire system must switch to SQL for consistency
• Assuming eventual consistency suffices for critical transactions
• Believing synchronous replication is always feasible in geo-distributed setups