5: Query Processing/ Optimisation

Question 1

What is query processing?

Answer 1

It’s the steps required to execute a query.

Question 2

What costs does processing incur?

Answer 2

• I/O costs for accessing the data
• Communications costs for transmitting data over any distance
• CPU costs for processing the data

Summary: accessing, transmitting and processing costs

Question 3

What is query optimisation?

Answer 3

It’s one of the steps in query processing which is used to identify the ‘best’ execution strategy ie the one with the minimum resources and therefore costs required to execute the query.

Question 4

What are the 3 different levels in a tree structure?

Answer 4

• Leaf node level -> relations
• Non-leaf node level -> RA operations
• Root-node level -> result

Question 5

What is the heuristic approach?

Answer 5

Its then transformation rules convert algebraic expressions into alternative forms (several trees).

Each tree has its own unique execution sequence, with unique costs for that sequence.

Heuristic approach provides alternative forms that are more efficient, eg perform a select before performing a join.

Question 6

The initial tree is based on the Cartesian Product of the relations. Would you use this tree?

Answer 6

No.

The Cartesian Product produces all possible combinations of any join – resulting in very large relations.

Question 7

The query optimiser produces several execution sequences. Does it then look for the ‘absolute best’ one?

Answer 7

No, this would add to the cost.

Optimisation is about selecting from the alternatives an execution sequence that is considered efficient enough to run the query, even though there may be other more efficient ones available.

Question 8

How do you read the relational algebra tree?

Answer 8

Bottom-up ^

Start at leaf-nodes and traverse up the root.