Physical design

Physical design – is the process of deciding how to store relations and access data.

GOAL choose the best performing storage structure

Part 1: Steps of processing a high-level query

1. The scanner identifies the language components in the text of the query

2. The Parser checks the query syntax and determine whether it is formatted according to the syntax rules of the language

3. The validation process determines if all attribute and relation names are valid and semantically meaningful

Query tree - the internal form of a query

Query optimisation – the DBMS compares a number of query plans (strategies) for retrieving the result of the query from the internal database files. (baso trial and error the best method for doing the query)

Query code generator – generates the code to execute the query

Runtime database processor – runs the query code, generates runtime error messages

Part 2: Query Speeds Based On Access Methods

Query is speed - depends on num of reads and writes (lesser extent)

File Organisation: best search type

• Heap (unordered) file: linear search

• Sequential (ordered) file: binary search

• Hash (direct) file: hash function calculates memory address

Reading by blocks (pages)

Block (page) - is the smallest unit of data to be read or written to a data file on the disk, this block may contain many rows of data

Blocks are not stored sequentially on disk: best access methods are linear and hash

Costing Operations (using rows)

Join (where)

Compares each row of the first table to all of the rows on the second table

Note: table1 should always be the smallest one... even if picking max

Cost = rows table 1 + (rows table1 * rows table2)

Select (when == value)

Reads all rows in the table

Cost = rows table 1

Project Columns (select)

Reads all rows in the table

Cost = rows table 1

Example

Part 3: Query Optimisation Strategies

Algorithms are used to implement slept in joint statements (relational operators), but each has a cost in terms of its read and write operations.

• Cost estimation i.e. choosing the strategy with the best execution time

• Heuristics – uses transformation rules to lower cost ordering of algorithms

Cost Estimation

The optimiser estimates the cost for each plan, and chooses the strategy with the lowest lowest cost.

The optimiser only has to approximate since it only needs to have removed the bad plans and get a near enough optimal plan.

Heuristic rules

What the lecture slide said

Condition Selection: Chooses the order of conditions within the algorithm, pretty much it picks the condition that reduces the selection to the smallest amount first (condition = a > b)

Operator ordering: Applies a select and project operations before applying the join operation since join operations generate larger tables, while select and project operation to reduce the size of a table

Part 4: Indexes to Extend Binary Search, and Searches

Searching Algorithms

• Linear search (brute force): Retrieves every single record in the file starting from the beginning

• Binary search (uses the index, or ID): looks the middle of the record is it's greater or less than and then goes from there, works on a ID of some kind

• Hash search: is direct access to the record

Indexes

Uses secondary indexes on non-primary key columns

Indexing Structures

• Indexes: A table of index values and associated address pointers to the records containing the relevant rows

Types of Index

• Primary key indexes: Built on a unique, unordered field

• Secondary key indexes: Built on a non-unique, unordered field

• Multilevel indexes: when an index is large, the index can be split into a number of shorter indexes. It provides an index to the indexes (e.g. B – trees)

Example of an Index

Adv:

• its hella quick almost as fast as Pedro

Dis:

• you have to maintain multiple levels

• takes up space

Example of a Multilevel Index

• The top level points to 2 tables one where the greatest index is equal to 23 and the other by the greatest index is equal to 30

• The lower level indexes well then points towards the primary key of the student records table

Adv:

• Is quicker but only when you've got a big table

Dis:

• takes up space