also Indices

Primary mechanism to get improved performance on a database
Persistent data structure, stored in database

Functionality
Index on T.A or T.B or T.(A,B) allows you to ask a question based on that index instead of scanning the whole table.

Utility
Index = difference between full table scans and immediate location of tuples.
Orders of maginitude performance difference

Underlying data structures
– Balanced trees (B trees, B+ trees) A = V, A < V logarithmic in running time - Hash tables A = V constant running time Select sName From Student Where sID = 18942 Index on sID Many DBMS's build indexes automatically on PRIMARY KEY and sometimes UNIQUE attributes. Select sID From Student Where sName = 'Mary' and GPA > 3.9
Index on sName
Index on GPA
Index on (sName, GPA)

Downsides of Indexes
1) take up extra space
2) Index creation
3) Index maintenance

Picking which indexes to create:
size of table and possibly layout
data distributions
query vs update load

Physical design advisors
Input: database (statistics) and workload
Output: recommended indexes

Query Optimizer: looks at db stats. query or update, indexes and finds the best execution plan with estimated cost

SQL Syntax
Create Index IndexName on T(A)
Create Index IndexName on T(A1, A2, …, An)
Create Unique Index IndexName on T(A)
Drop Index IndexName