Databases

Lecture 10: Indexes, Transactions, Authorization

• Lecture notes: sections 6.7, 7.1, 7.4, 7.6
• Book: 6.6, 8.3, (8.4), 10.1

Indexes

Example

• Consider a relation Employees(name,email,office,salary) with 5000 rows.
• How fast are these queries?

  • SELECT email FROM Employees WHERE name='Thomas'
    

  • SELECT name FROM Employees WHERE salary>50000
    

• Finding rows by using the primary key is expected to be fast.
• Finding rows based on other attribute values might require all rows to be retrieved and tested.
• This is because the DBMS automatically creates an index for the primary key.

Indexes

What is an index?

• An index is a data structure that allows values to be found quickly.
• PostgreSQL uses B-Trees for indexes by default.
• It is also possible to use hash tables.

Indexes

B-Tree

• A self-balancing tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time.
• A generalization of binary search trees, allowing nodes to have more than two children.
• Optimized for systems that read and write large blocks of data.

Indexes

What indexes are there?

• There is always an index for the primary key.
• An index is also added for attributes with a UNIQUE constraints.
• Additional indexes can be added with the CREATE INDEX statement.

Indexes

Live Demo

Using Internet Movie Database data (introduced last time)

• movies.sql (tables), import.psql, views.sql, indexes.sql.
• IMDB Database downloads: datasets.imdbws.com
• The table Names_basics contains almost 10 million rows.
• Comparing the speed of a few search examples with and without an index.
• Checking sizes of tables and indexes: \d+, \di+

Indexes

What operations benefits from the use of an index

• SELECT … WHERE …, DELETE … WHERE …, UPDATE … WHERE …
  • Quickly finding rows with matching attribute values.
• INSERT, UPDATE
  • Checking that primary keys and other UNIQUE attributes are still unique, without searching through the entire table.
• JOIN
  • Quickly find matching rows in the tables that are joined.
• ORDER BY, GROUP BY
  • Produce sorted/grouped output without sorting.

Indexes

What search conditions can be optimized using an index?

• SELECT … FROM … WHERE condition
  

• Equalities and other comparisons
  • a='something', a<='someting', a>'something', …
• Some boolean combinations of comparisons
  • price>100 AND price<200
  • name='Karl' OR name='Carl' (requires two scans of the index)
• Some pattern matching
  • Finding a prefix: name LIKE 'Tom%'
  • But not: name LIKE '%Cruise'

Indexes

What are the drawbacks of adding an index?

• Extra works in needed to update the index when data is inserted, updated or deleted.
• Storing the index takes extra space.
• (The lecture notes describe a cost-benefit analysis that can be used to help decide if using an indexed is beneficial.)

Indexes

SQL Syntax summary

• statement ::= CREATE INDEX indexname ON Tablename (attribute+)? DROP INDEX indexname

Transactions

Atomicity

• Some changes in a database require more than one update.
• Example: Alice transfers 2000kr to Bob:

  • UPDATE Accounts SET balance=balance-2000 WHERE name='Alice';
    UPDATE Accounts SET balance=balance+2000 WHERE name='Bob';
    

• What if there is a system crash or power outage betwen the two updates?
  • Could the 2000kr disappear!?

Transactions → Atomicity

• Solution: group the two updates into a transaction:

  • START TRANSACTION;
        UPDATE Accounts SET balance=balance-2000 WHERE name='Alice';
        UPDATE Accounts SET balance=balance+2000 WHERE name='Bob';
    COMMIT;
    

• The DBMS guarantees that transactions are atomic, i.e. it's all-or-nothing.
  • Even if there is a system crash or power failure at the wrong moment.
• By default each SQL statement is treated as a separate atomic transaction.
  • Triggers are executed as part of that atomic transaction.

Transactions

Update = Read + Write

• Consider again

  • UPDATE Accounts SET balance=balance-2000 WHERE name='Alice';
    UPDATE Accounts SET balance=balance+2000 WHERE name='Bob';
    

• Under the hood, each update might be implemented as two database accesses:

  • b1 := READ balance  FROM Accounts WHERE name='Alice';
    WRITE balance=b1-2000 TO Accounts WHERE name='Alice';
    b2 := READ balance  FROM Accounts WHERE name='Bob';
    WRITE balance=b2+2000 TO Accounts WHERE name='Bob';
    

Transactions

Concurrent transactions

What if at the same time Bob wants to transfer 1000kr to Carl?

• Accounts before

  name	balance
  Alice	30000
  Bob	20000
  Carl	1000

• UPDATE Accounts SET balance=balance-2000 WHERE name='Alice';
  UPDATE Accounts SET balance=balance+2000 WHERE name='Bob';
  

• UPDATE Accounts SET balance=balance-1000 WHERE name='Bob';
  UPDATE Accounts SET balance=balance+1000 WHERE name='Carl';
  

• Accounts after

  name	balance
  Alice	28000
  Bob	21000
  Carl	2000

• What would happen if transactions weren't atomic?

Transactions

Arbitrarily interleaved access

• b1 := READ balance  FROM Accounts WHERE name='Alice';
  

• WRITE balance=b1-2000 TO Accounts WHERE name='Alice';
  

• b2 := READ balance  FROM Accounts WHERE name='Bob';
  

• WRITE balance=b2+2000 TO Accounts WHERE name='Bob';
  

• b3 := READ balance  FROM Accounts WHERE name='Bob';
  

• WRITE balance=b3-1000 TO Accounts WHERE name='Bob';
  

• b4 := READ balance  FROM Accounts WHERE name='Carl';
  

• WRITE balance=b4+1000 TO Accounts WHERE name='Carl';
  

Transactions

Interference problems

• Dirty Read
• Non-repeatable Read
• Phantom

Transactions → Interference problems

Dirty Read

• 	T1	T2
  1.		insert v
  2.	read v
  3.		rollback

• Happens when one transaction is allowed to read a value before it has been committed.

Transactions → Interference problems

Non-repeatable Read

• 	T1	T2
  1.	read a
  2.		update a=a' commit
  3.	read a

• Happens when one transaction reads the same data twice and gets different results because of another concurrent transaction.

Transactions → Interference problems

Phantom

• 	T1	T2
  1.	SELECT * FROM A
  2.		INSERT INTO A … COMMIT
  3.	SELECT * FROM A

• The same query gives different results beacuse of data commited in another concurrent transaction

Transactions → Interference problems

Isolation levels

• START TRANSACTION isolation_level;
  

• Isolation levels from lowest to highest

  	Dirty reads	Non-repeatable reads	Phantoms
  READ UNCOMMITTED	yes	yes	yes
  READ COMMITTED	no	yes	yes
  REPEATABLE READ	no	no	yes
  SERIALIZABLE	no	no	no

• SQL standard: the default is SERIALIZABLE.
• PostgreSQL:
  • The default is READ COMMITTED.
  • READ UNCOMMITTED is not supported, you get READ COMMITTED instead.

Transactions → Interference problems

Another summary of isolation levels

• SERIALIZABLE
  • I accept no interference from other transactions.
• REPEATABLE READ
  • I accept that others make changes as long as they don't modify or delete data I have already looked at.
• READ COMMITED
  • I accept that others make any changes to the database.
• READ UNCOMMITED
  • I accept that some data I get might actually never be in the database (!)

Transactions

The ACID properties

Database transactions are expected to have the following properties

• Atomicity
  • Transactions are atomic (all-or-nothing).
• Consistency
  • Database constraints are preserved.
• Isolation
  • Concurrent transactions do not interfere.
• Durability
  • Once a transaction has been committed, the changes are permanent.

Transactions

Implementation techniques

• Locks (for isolation)
  • Mutual exclusion
  • Shared locks for read access
  • Exclusive locks for write access
• Write-Ahead Log (atomicity and crash recovery)
  • Changes made by a transaction are entered into a separate log before they are integrated in the "real" database tables.

Transactions

SQL Syntax summary

• statement ::= START TRANSACTION mode*  COMMIT  ROLLBACK  mode ::= ISOLATION LEVEL level  READ WRITE  READ ONLY  level ::= SERIALIZABLE  REPEATABLE READ  READ COMMITED  READ UNCOMMITED
• PostgreSQL also lets you write BEGIN instead of START TRANSACTION.

Transactions

Transactions with JDBC in Java

• To use transactions, run conn.setAutoCommit(false);.
  • where conn is your Connection object.
  • Run it once.
• End each transaction with conn.commit(); or conn.rollback();
  • This also starts a new transaction.
• To set the isolation level, use conn.setTransactionIsolation(…)
• See the JDBC manual: setAutoCommit, commit, rollback, setTransactionIsolation.

Authorization and privileges

Intro

• Every connection to a database (including from applications) is made by a user.
• Users should not be allowed to do everything.
• They should only be allowed to do the things they need for their purpose.
• If an attacker gets hold of a username/password, the damage they can do will be limited by the privileges granted to that user.

Authorization and privileges

Databases vs file systems privileges/permissions

• A Unix file systems
  • Three different permissions on files: read, write, execute.
  • Permissions on three levels: for the owner, for users in the same group, for everyone else.
• An SQL database
  • Privileges on tables, views, triggers, etc.
  • Nine different privileges (SELECT, INSERT, UPDATE, DELETE, …)
  • Privileges controlled separately for each user.

Authorization and privileges

• Initial privileges
  • All objects (tables, views, etc) are owned by the user who created them.
  • The owner has all privileges on his/her objects, other user have no access at all.
• Granting and revoking privileges
  • The owner can grant certain privileges to other users.
  • Granted privileges can be revoked.
  • Only the owner of a table can drop the table (and similarly for other objects). This is a privilege that can not be granted to other users.

Authorization and privileges

Roles

• Users can be given roles (which are like groups in Unix).
• Privileges can be granted to roles.
• This can simplify the administration of privileges.
• Example: the roles a student portal could be:
  • student, teacher, study_administrator

Authorization and privileges

Examples

• GRANT SELECT ON Products TO webshop_users, marketing;
  

• GRANT SELECT(name,email,office) ON Employees TO PUBLIC;
  

• REVOKE UPDATE, DELETE ON Transfers FROM staff;
  

• For SELECT, INSERT and UPDATE, the privilege can be restricted to certain columns.

Authorization and privileges

Granting the privilege to grant

• When granting a privilege to someone, you can choose to pass on the right to grant that privilege to others.

• GRANT UPDATE(salary) ON Employees TO Bob WITH GRANT OPTION;
  

Authorization and privileges

Grant diagrams

Example

• Starting state: the user Alice has the a privilege R on an object he/she owns:

  

• Alice: GRANT R TO Bob WITH GRANT OPTION;
  

• 

• Bob: GRANT R TO Carl;
  

• 

• Alice: REVOKE GRANT OPTION FOR R FROM U
  

• 

• Alice: REVOKE R FROM U
  

• 

Authorization and privileges

SQL Syntax summary

• statement ::= GRANT privilege+ ON object TO user grantoption? REVOKE privilege+ ON object FROM user CASCADE? REVOKE GRANT OPTION FOR privilege+ ON object FROM user CASCADE? GRANT rolename TO username adminoption? grantoption ::= WITH GRANT OPTION  adminoption ::= WITH ADMIN OPTION 

Authorization and privileges → SQL Syntax summary

• privilege ::= SELECT (attr+)? | INSERT (attr+)? | UPDATE (attr+)? DELETE | REFERENCES | … ALL PRIVILEGES  object ::= tablename | viewname | trigger | … user ::= username | rolename | PUBLIC 

Further reading

• Jonas Duregård's slides about authorization and transactions with some more details and examples.
• PostgreSQL documentation:
  • Indexes, CREATE INDEX
  • START TRANSACTION
  • GRANT, CREATE ROLE, createuser.
• Java JDBC: setAutoCommit, commit, rollback, setTransactionIsolation.
• Extra reading for the curious:
  • SQLite: Locking and rollback journal, Write-Ahead Logging.
  • PostgreSQL: Reliability and the Write-Ahead Log.