Question

Develop an optimal execution plan (including the exact execution ordering) for the following SQL query. This should include the most appropriate algorithms for both selection and join operations. Justify your choices based on the provided table and index information below that are partly identical to that provided in the previous question. You should also calculate the total cost of your proposed execution plan in terms of total disk block accesses. [15 points] Query: SELECT * FROM PLAYERS AS P, PLAYER_PERFORMANCE AS PP WHERE P.PlayerID = PP.PlayerID AND PP.Score > 8.0; The relation PLAYERS has 1000 records stored in 100 disk blocks with blocking factor = 10 records/block and PLAYER_PERFORMANCE has 6110 records stored in 306 disk blocks with blocking factor = 20 records/block. Assume there are 13 main memory buffers available and that the blocking factor for writing the join result back to disk is 12 records per block. The following access paths are also available: •A primary index on P.PlayerID, with levels xPlayerID = 2. •A primary index on the composite key (PP.PlayerID, PP.GameID) with levels x(PlayerID, GameID) = 3. •In addition, the relation PP is sorted on PlayerID in ascending order. The PLAYERS table remains unsorted. •A secondary index on PP.Score, with levels xScore = 4 and average selectivity sScore = 0.25.

Answer 1

The optimal execution plan utilizes the secondary index on PP.Score for selection, followed by a merge join using the sorted order of PP.PlayerID and the primary index on P.PlayerID.

To develop an optimal execution plan, we need to consider the available access paths, indexes, and the characteristics of the tables involved in the query. Let's break down the query and build an execution plan step by step:

Query:

```sql

SELECT * FROM PLAYERS AS P, PLAYER_PERFORMANCE AS PP

WHERE P.PlayerID = PP.PlayerID AND PP.Score > 8.0;

Given information:

- PLAYERS: 1000 records, 100 disk blocks, blocking factor = 10 records/block

- PLAYER_PERFORMANCE: 6110 records, 306 disk blocks, blocking factor = 20 records/block

- 13 main memory buffers available

- Blocking factor for writing the join result back to disk is 12 records per block

- Primary index on P.PlayerID with levels xPlayerID = 2

- Primary index on (PP.PlayerID, PP.GameID) with levels x(PlayerID, GameID) = 3

- Relation PP is sorted on PlayerID in ascending order

- Secondary index on PP.Score with levels xScore = 4 and average selectivity sScore = 0.25

Execution Plan:

1. Selection on PP.Score > 8.0:

- Use the secondary index on PP.Score because it provides efficient access to selective data.

- Apply the selection first to reduce the number of rows early in the process.

- Estimated cost: \(sScore \times \text{Total records in PP} = 0.25 \times 6110 = 1527.5\) block accesses.

2. Join Operation:

- Use the sorted order of PP.PlayerID to perform a merge join with the primary index on P.PlayerID.

- Merge join is efficient when both relations are sorted on the join attribute.

- Estimated cost: \(2 \times \text{Number of records in PP} = 2 \times 6110 = 12220\) block accesses.

3. Write the Join Result Back to Disk:

- Since the blocking factor for writing is 12 records per block, each output block will contain 12 joined records.

- The total number of output blocks:
`\(\frac{\text{Total joined records}}{\text{Blocking factor for writing}} = (6110)/(12) \approx 509.17\).`

- Estimated cost: \(509.17\) block accesses.

Total Estimated Cost:

`\[ 1527.5 (\text{Selection on PP.Score}) + 12220 (\text{Merge Join}) + 509.17 (\text{Write Join Result}) = 14356.67 \text{ block accesses}\]`

This execution plan minimizes the number of block accesses by utilizing available indexes, sorting, and efficient join operations.