Miscellaneous database administration notes

A Big Dataset

• legitimize the data by putting it to a non-hacking use
• establish the legitimate use of bittorrent

The size of the Ascii tables files is about 200 Mbyte. The actual MySQL file with index is about four times that, but only a little over twice that without the index (perhaps because I allowed varchar(80?)

-rw-rw---- 1 mysql mysql 801112064 Feb 17 12:22 password.ibd
-rw-rw---- 1 mysql mysql 478150656 Feb 17 12:11 password_noindex.ibd

For Postgres, the file size without index was 500,998,144 bytes. With index, the base file didn't change size.

See here for file locations.

Copying the table within MySQL takes about 1.5 minutes. Copying in Postgres took 164 seconds, or 2.75 minutes.

But we can configure the index so that it does use text prefixes, with the varchar_pattern_ops or text_pattern_ops options. I added an index "username_prefix" using the text_pattern_ops option to table password, speeding up this username like 'david%' query from 10 seconds to 164 ms. Here's the create table code:

create index password_index on ipassword (password);

create index username_prefix on ipassword (username, password varchar_pattern_ops);

Counting distinct entries

Counting items that occur only once

Bigger Company

The Company has had a hiring spree. I created data for 300 more employees, and a total of 20 departments and 40 projects. Each new employee works on four projects. This data is in my database bigcompany, available at pld.cs.luc.edu/database/bigcompany. (Only tables employee, department, project and works_on are provided; you can use the original versions of the other files, or leave them out.)

The new employee names all came courtesy of listofrandomnames.com (who would have thought?). The new hires don't have addresses yet, though I did give them random salaries.

Most of the employee data was created using C# programs that generated appropriate insert/update statements using random values. The new employees have ssns from 111220001 to 111220300.

Select count(*) from employee;

returns 308

select e.ssn, e.fname, e.lname, e.salary, e.dno from employee e order by e.lname limit 50;

The limit N SQL clause is useful at the end of any query to view only some of the data.

A few notes on transferring data from MySQL to Postgres:

(Generally, export and import must be run as "root" or "superuser")

To export: select * from employee into outfile '/home/pld/bigemployee.csv';

To import into postgres, run the following. To use the copy command, you have to be the postgres user.

    \connect bigcompany

    copy employee from   '/home/pld/305/bigcompany/bigemployee.csv'   delimiter E'\t' csv  null '\N';
    copy department from '/home/pld/305/bigcompany/bigdepartment.csv' delimiter E'\t' csv  null '\N';
    copy project from    '/home/pld/305/bigcompany/bigproject.csv'    delimiter E'\t' csv  null '\N';
    copy works_on from   '/home/pld/305/bigcompany/bigworks_on.csv'   delimiter E'\t' csv  null '\N';

A performance experiment

+-------+--------------+------+-----+---------+-------+
| Field | Type         | Null | Key | Default | Extra |
+-------+--------------+------+-----+---------+-------+
| id    | int(11)      | YES  |     | NULL    |       |
| name  | varchar(100) | YES  |     | NULL    |       |
+-------+--------------+------+-----+---------+-------+

+------------+-------+
| id         | name  |
+------------+-------+
|          1 | peter |
|          3 | ralph |
| 2147483647 | fred  |
+------------+-------+

Explain in MySQL

Here is an example. Suppose the query is the following triple join:

select e.lname, p.pname, w.hours
from employee e, project p, works_on w
where e.ssn = w.essn and w.pno = p.pnumber

If we run this on the bigcompany data using MySQL 5.7:

explain select e.lname, p.pname, w.hours from employee e, project p, works_on w where e.ssn = w.essn and w.pno = p.pnumber;

we get a table:

The rows here refer to the individual tables of the join, identified by their table aliases in the table column. Other columns are as follows:

• select_type: simple means a simple join, with no nested subquery.
• type:
• index means the index was scanned in full. This is slightly faster than scanning the table row-by-row.
• ref means that all matching rows (in a join) were retrieved. An index is used, but it is not a key index. Above, given a project record, all matching works_on rows with that project.pnumber are retrieved using the works_on.pno index.
• eq_ref means that MySQL knew there would be only one matching row (eg the lookup of w.essn in table employee). This is only used if there is a suitable key index available. MySQL looks up the matching row using the index. Above, given a works_on record w, MySQL looks up w.essn in employee using the index on employee.ssn.
• all: all records were examined
• const: MySQL knows there is a single match
• possible_keys: list of keys that might have been used
• key: the actual key that was used
• key_len: the length of the key, in bytes. The department.dname key is of type varchar(15); the extra two bytes are presumably a length field.
• ref: what value was looked up in this table (for example, p.pnumber was looked up in the works_on table using the pno index)
• rows:An estimate of the number of rows to be examined. When looking up w.essn in table employee, the 1 here is exact, as ssn is the primary key of employee. When looking up p.pnumber in works_on, the 1 is a gross underestimate. It is not exactly clear why this is happening; the fact that the type column is ref rather than eq_ref shows that MySQL knows one p.pnumber value may lead to multiple works_on matches.
• extra: Additional information as appropriate. The "using index" here means that each project name is looked up via the index, rather than simply by traversing the project table row-by-row.

What MySQL did here was to

• First retrieve every employee (the ALL in the type column), using the employee.ssn (primary-key) index. 
• For each e.ssn value (column ref), retrieve matching works_on records using the works_on.essn index (the PRIMARY index). The ref in the type column means that this is a one-to-many lookup (as only one of the two primary-key fields are used). The 1 in the rows column is misleading.
• For each record so far, look up the pno (column ref) in the project table. The eq_ref in the type column shows that MySQL knows these matches must be unique.

Here is the output of explain:

This is a similar join as the previous query, joining employee, works_on and project the same way, but is done in a different order.

MySQL first looks up "Computerization" in the project table, obtaining pnumber = 4. MySQL knows only 1 record will be retrieved. The "using index" in the extra column is supposed to indicate this.

In the second row all works_on records matching this pnumber are retrieved using the key on pno (key column). Here, however, MySQL gets a larger number for its estimate of the number of rows in works_on returned: 31 rather than 1 as in the previous example. 

Finally, for each w.essn (column ref), MySQL looks up the matching employee record using the primary key on employee.

Here is another example, including a join and an additional where-clause:

select e.lname, d.dname from employee e, department d where e.dno = d.dnumber and e.salary >=40000;

Here is the result of explain:

For each department, MySQL then looks up the employees in that department, using the index on employee.dno. This is the index created by the foreign-key constraint employee.dno references department.dnumber. Employees with salary less than $40,000 are removed at this point.

Note that there is no index above on e.salary. What happens if the query uses a field on which we do have an index?

select d.dname from employee e, department d where e.dno = d.dnumber and e.ssn='111220266';

The explain output is

This is identical with the version above. Now let us try to use straight_join to force a different query ordering:

We now get

Sure enough, the steps are now

1. MySQL looks up pnames from project
2. MySQL joins these to works_on records, matching p.pnumber to w.pno, using the works_on key on pno
3. MySQL joins this to employee by looking up w.essn as the employee.ssn value.

Explain in Postgres

• 0.00: estimated startup cost, in relatively arbitrary cost units that are supposed to relate to page accesses
• 7.85: estimated total cost
• 1: rows generated. We are looking up one employee, by ssn
• 7: average size, in bytes, of the records returned

 Index Only Scan using password_pkey on password  (cost=0.56..4.61 rows=3 width=8)
   Index Cond: (username = 'corydeut'::text)

explain select e.lname, d.dname from employee e join department d on e.dno = d.dnumber where e.salary >=40000;

explain select e.lname, d.dname from employee e join department d on e.dno = d.dnumber where e.salary >=30000;

explain select d.dname from employee e, department d where e.dno = d.dnumber and e.ssn='111220266';

                                   QUERY PLAN                                   
---------------------------------------------------------------------------------
  Nested Loop  (cost=0.00..16.13 rows=1 width=48)
   ->  Seq Scan on employee e  (cost=0.00..7.85 rows=1 width=4)
         Filter: (ssn = '111220266'::bpchar)
   ->  Index Scan using department_pkey on department d  (cost=0.00..8.27 rows=1 width=52)
 

This is another nested-loop join, but this time the added where condition -- a specific value for e.ssn -- is even more selective. We use the employee index on ssn to find the employee, and then look up the department in the department table. It is a very "small" join.

explain select e.lname from employee e where e.ssn between '111220100' and '111220150';

Hash Joins

explain select * from employee e join department d on e.dno = d.dnumber join project p on d.dnumber = p.dnum;

explain select * from employee e join works_on w on e.ssn = w.essn join project p on w.pno = p.pnumber where p.pname='Computerization';

(5a.json and 5b.json)

More fun with statistics

Let's create two tables:

create table rand (
    id int primary key,
    rval int
);

insert into rand select generate_series(1,100000) as id, 100000000*random();

create table tbl (
    id integer primary key,
    thou integer,
    hun  integer,
    ten1 integer,
    ten2 integer,
    ten3 integer,
    ten4 integer
);

insert into tbl select id from tbl2 order by id;
update tbl set thou = id%1000, hun=id%100,ten1=id%10;
update tbl set ten2=10-ten1,ten3=ten1+1,ten4=ten1+10;

Note that the ten1 through ten4 columns are not statistically independent. Knowing one value, you can easily figure out the others. In particular, if ten1 = 1, then ten2=9, ten3=2, and ten4=11.

We will now join these tables on r.id = t.id. If we do this without a where clause, we get a hash join.

Question 1: how selective does a where-clause have to be to get Postgres to switch from hash join to a nested-loop join?

explain select * from rand r join tbl6 t on r.id = t.id where t.ten1=2;

                               QUERY PLAN                               
--------------------------------------------------------------------------
 Hash Join  (cost=2677.46..5679.23 rows=10277 width=40)
   Hash Cond: (r.id = t.id)
   ->  Seq Scan on rand r  (cost=0.00..2524.00 rows=100000 width=12)
   ->  Hash  (cost=2549.00..2549.00 rows=10277 width=28)
         ->  Seq Scan on tbl t  (cost=0.00..2549.00 rows=10277 width=28)
               Filter: (ten1 = 2)

This is the least selective; a hash join is still used.

explain select * from rand r join tbl t on r.id = t.id where hun=1;

                               QUERY PLAN                               
--------------------------------------------------------------------------
 Hash Join  (cost=2561.66..5470.79 rows=1013 width=40)
   Hash Cond: (r.id = t.id)
   ->  Seq Scan on rand r  (cost=0.00..2524.00 rows=100000 width=12)
   ->  Hash  (cost=2549.00..2549.00 rows=1013 width=28)
         ->  Seq Scan on tbl t  (cost=0.00..2549.00 rows=1013 width=28)
               Filter: (hun = 1)

This is still a hash join! Note that the rows=1013 estimate on the first line is pretty accurate, but not perfect.

explain select * from rand r join tbl t on r.id=t.id where thou=1;

                                  QUERY PLAN                                  
-------------------------------------------------------------------------------
 Nested Loop  (cost=0.42..3360.61 rows=98 width=40)
   ->  Seq Scan on tbl t  (cost=0.00..2549.00 rows=98 width=28)
         Filter: (thou = 1)
   ->  Index Scan using tbl2_pkey on rand r  (cost=0.42..8.27 rows=1 width=12)
         Index Cond: (id = t.id)

Finally we've forced Postgres to use a nested loop join!

Question 2: how good is Postgres at estimating the selectivity of where clauses?

Let's try three in sequence:

explain select * from tbl where ten1 = 1;

                       QUERY PLAN                        
-----------------------------------------------------------
 Seq Scan on tbl  (cost=0.00..2549.00 rows=10093 width=28)
   Filter: (ten1 = 1)

Look at the rows=10093 estimate. The actual value is 10,000; Postgres' estimate is pretty good.

explain select * from tbl where ten1 = 1 and ten2 = 9;

Seq Scan on tbl  (cost=0.00..2799.00 rows=1019 width=28)

The actual answer is again 10,000 rows. But Postgres doesn't know that. It has assumed the two where-conditions are independent, and so only 1/100 of the rows will be included.

explain select * from tbl where ten1 = 1 and ten2 = 9 and ten3 = 2;

Seq Scan on tbl  (cost=0.00..3049.00 rows=103 width=28)

Now Postgres assumes that with three where-conditions each 10% selective, the end result is 0.1% selective. It is not; it's still 10%.

Question 3: can we use this trick to make Postgres use the wrong join?

We know from Question 1 that a where-condition with a selectivity of 1/1000 will force a nested-loop join. Let's try it:

explain select * from rand r join tbl t on r.id=t.id where ten1 = 1;

                               QUERY PLAN                               
-------------------------------------------------------------------------
 Hash Join  (cost=2675.16..4594.09 rows=10093 width=36)
   Hash Cond: (r.id = t.id)
   ->  Seq Scan on rand r  (cost=0.00..1443.00 rows=100000 width=8)
   ->  Hash  (cost=2549.00..2549.00 rows=10093 width=28)
         ->  Seq Scan on tbl t  (cost=0.00..2549.00 rows=10093 width=28)
               Filter: (ten1 = 1)

This is expected.

explain select * from rand r join tbl t on r.id=t.id where ten1 = 1 and ten2 = 9 and ten3 = 2;

This is not the choice Postgres should be making! It is the "wrong" plan; Postgres has been fooled by the fact that ten1, ten2 and ten3 are not independent.

Question 4: is there a fix?

create statistics s1 (dependencies) on col1, col2, col3 from table tbl2;

But this does not work in Postgres 9.5, which is what I'm using.

We will see where Postgres keeps its statistical knowledge in sql3.html#pg_stats.

Semi-joins and Anti-joins

Password DB Explain

explain select * from password where username = 'badmole';

explain select * from password where password = 'uxoodo';

Index Creation

MySQL Indexes

• The primary key
• If the primary key has two attributes, eg (essn, pno), then the index can also be used as an index on (essn) alone
• Any other keys (declared unique in Create Table)
• Any attributes subject to foreign-key constraints, eg employee.dno and employee.super_ssn (why?)

In the first few weeks I created an index on project.plocation so that I could introduce a Foreign Key constraint requring that each project.plocation appeared in the table dept_locations:

alter table project ADD foreign key (plocation) references dept_locations(dlocation);

The necessary index was created with

create index dloc_index on dept_locations(dlocation);

For example, the table employee has three indexes, on ssn, super_ssn and dno. The table works_on has indexes on (essn,pno) (doubling as an index on (essn) alone) and on (pno). And the table project has indexes on pnumber, pname, dnum and plocation.

To view MySQL indexes, use show index from tablename.

A Very Slow MySQL Query

I discovered a wonderful example of a very slow query at http://www.slideshare.net/manikandakumar/mysql-query-and-index-tuning, due to Keith Murphy, co-author of MySQL Administrator's Bible.

The goal is to force the database (MySQL here) to use a quadratic algorithm to form a join. This is the worst-case algorithm, where for each record of the first table the database has to do a sequential scan of the second table. For MySQL, the main thing is to force it not to use an index scan. The two primary "tricks" are

• To create a table with no index, just don't declare any primary key! Or, alternatively, declare a primary key that is an unrelated (perhaps synthetic) column.
• To force MySQL not to use an index on the other table involved in the join, use a left join (or, alternatively, an inner exists query).

When Postgres is faced with this situation, it uses a hash join, which performs reasonably well (very well, usually!) even when no useful index is available. But MySQL doesn't support that (at least not through v7.0; I haven't checked more recently). However, a similarly slow Postgres query appears below.

The database (querydemo) consists of information about students and their scores on one of three tests. There are three tables:

• students
• grades
• tests

Here are the tables (on server sql1.cs.luc.edu)

create table students (
	student_id integer not null primary key,
	name char(40)
);

create table tests(
	test_id integer not null primary key,
	total integer,
	name char(40)
);

create table grades (
	test_id integer,
	student_id integer,
	score decimal(5,2)
);

There are only three tests; this is the smallest table:

insert into tests values (1,100,'test 1');
insert into tests values(2,100,'test 2');
insert into tests values (3,300, 'test 3');

The students2 table has 10,000 entries generated through a unix shell script:

for i in `seq 1 10000`
do
     echo "insert into students values ($i, 'student$i');" >> insert_students.sql
done

insert into grades select 1, s.student_id, rand()*100 from students s order by rand() limit 8000;
insert into grades select 2, s.student_id, rand()*100 from students s order by rand() limit 8000;
insert into grades select 3, s.student_id, rand()*300 from students s order by rand() limit 8000;

*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: s
         type: index
possible_keys: NULL
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 9976
        Extra: Using index
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: g
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 23521
        Extra: Using where

*************************** 1. row ***************************
           id: 1
  select_type: PRIMARY
        table: s
         type: index
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 9976
        Extra: Using where
*************************** 2. row ***************************
           id: 2
  select_type: DEPENDENT SUBQUERY
        table: g
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 23521
        Extra: Using where

Adding an Index

*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: s
         type: index
possible_keys: NULL
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 9976
        Extra: Using index
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: g
         type: ref
possible_keys: grades2_student_id
          key: grades2_student_id
      key_len: 5
          ref: querydemo.s.student_id
         rows: 1
        Extra: Using where

*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: s
         type: index
possible_keys: NULL
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 9634
        Extra: Using index
*************************** 2. row ***************************
           id: 1, down to about 2
  select_type: SIMPLE
        table: g
         type: ref
possible_keys: grades2_test_id
          key: grades2_test_id
      key_len: 5
          ref: const
         rows: 7922
        Extra: Using where

Postgres

Note the Hash Anti Join. An "anti join" is the result of taking an outer join, and then considering those records where the "other" record is in fact null (here, g.student_id, meaning there is no match for s in table grades). MySQL does not handle this as a special case, but Postgres does. The not exists form of the query generates essentially exactly the same explain output; Postgres clearly recognizes the two forms as equivalent.

A slow Postgres Query

For our coverage of transactions, I created the following table (the goal was to allow later batching of updates to the parts table)

create table partupdate (
        invnum  integer,
        partnum integer,
        quan_sold integer,
        constraint partupdate_invnum  foreign key (invnum) references invoice(invnum),
        constraint partupdate_partnum foreign key (partnum) references part(partnum)
);

There are also definitions of the customer, invoice, invitem and part tables. The customer and part tables are populated with random data. The invoice/invitem tables are then populated by random purchases as made by the Python3 program conndemo.py.

The concern in conndemo.py is that every invoice has to update the appropriate rows of the part table, in order to update the inventory on hand. Multiple simultaneous invoices for the same part may lead to multiple updates of the same row of the part table at the same time, a potential bottleneck. The idea of the partupdate table is that each invoice can add one row to this table for each part ordered; there is never an issue with locked rows. The Python3 program conndemo3.py implements this. Setting the program's variables NUMTHREADS = 1 and PERTHREAD = 1000 simulates 1000 serialized (that is, not concurrent) transactions.

The primary key for partupdate probably should have been the first two items, (invnum,partnum), though that is not entirely clear as in some ways the partupdate table simply represents a log of all updates to do later, and in theory such logs can have duplicates. In any event, the table as written has no indexes at all.

For the examples below, I saved a snapshot of partupdate (which I have to delete records from regularly) as partupdate_copy:

insert into partupdate_copy select * from partupdate;

Anyway, let's find out the invoices having at least 12 parts:

    select pu.invnum from partupdate_copy pu group by pu.invnum having count(*) >= 12;

                               QUERY PLAN                                
-------------------------------------------------------------------------
 HashAggregate  (cost=533.62..558.62 rows=2000 width=4)
   Group Key: invnum
   Filter: (count(*) >= 12)
   ->  Seq Scan on partupdate pu  (cost=0.00..434.08 rows=19908 width=4)

This took, with about 10,000 records in partupdate, about 6 ms.

But now here it is with an inner query; the inner query (correlated) counts the number of parts corrsponding to that invnum:

    select distinct pu.invnum from partupdate_copy pu where (select count(*) from partupdate_copy p where p.invnum = pu.invnum) >= 12;

3.8 seconds!

A sequential scan within a sequential scan! That is, a nested loop, with no optimization tricks to speed it up!

But the problem does have something to do with the failure to have a proper index. If I add one:

create index partupdate_index on partupdate(invnum,partnum);

drop index partupdate_index;

The query now takes 104 ms to run, a 400x speedup! And creation of the index took less than 40 ms.

                                             QUERY PLAN                                            
----------------------------------------------------------------------------------------------------
   ->  Seq Scan on partupdate pu  (cost=0.00..763686.34 rows=6636 width=4)
         Filter: ((SubPlan 1) >= 12)
         SubPlan 1
           ->  Aggregate  (cost=38.33..38.34 rows=1 width=0)
                 ->  Bitmap Heap Scan on partupdate p  (cost=4.37..38.30 rows=10 width=0)
                       Recheck Cond: (invnum = pu.invnum)
                       ->  Bitmap Index Scan on partupdate_index  (cost=0.00..4.36 rows=10 width=0)
                             Index Cond: (invnum = pu.invnum)

Still a sequential scan on partupdate, at the top level. But the inner query now uses a bitmap heap scan, based on a bitmap index scan. Yay indexes!

A simpler version

Now let's try to extract out the essential feature of this example. The only attribute of partupdate that we refer to is invnum, so let's just use that:

create table nums (invnum integer);

Note that we don't make invnum a primary key. Now let's add 30,000 values:

insert into nums select generate_series(1, 30000);

There are no duplicate values! But let's repeat the count of for how many records does the same invnum appear at least 12 times. This count, of course, must be zero:

select invnum from nums group by invnum having count(*)>=12;

And here is the very slow version:

select p.invnum from nums p where (select count(*) from nums q where p.invnum = q.invnum) >= 12;

Time: 35036 ms

Postgres has no way to optimize away that inner query, and to run the inner query takes quadratic time.

Selecting Indexes

Much of this information comes from www.slideshare.net/myxplain/mysql-indexing-best-practices-for-mysql and www.slideshare.net/billkarwin/how-to-design-indexes-really.

The first step is identifying which queries are underperforming. If a query is slow, but you don't run it often, it doesn't matter. The MySQL slow-query log (/var/log/mysql/mysql-slow.log) can be useful here.

If a query is not running fast enough, options available include

• adding options to force the query to be run a certain way
• restructuring the query, eg from a nested query to a join
• adding suitable indexes

The straight_join option (above) is often useful for the first category, as can be the addition of a WITH INDEX index_name option. Most query-optimizing efforts, however, are in the last category: adding indexes.

Be aware that indexes add write costs for all updates; don't create more than you need.

A B-Tree index can also be used to look up any prefix of the key. The prefix might be a single attribute A in an index on trow attributes (A,B), or else a string prefix: e.ssn LIKE '55566%'.

B-tree indexes can also be used for range queries: key < 100, key BETWEEN 50 AND 80, for example.

Join comparisons do best when the fields being compared are both strings and are both the same length. Joining on ssn where one table declares ssn to be an Integer and the other a CHAR(9) is not likely to work well.

A non-key index has high selectivity if each index value corresponds to only a few records. An index on lname might qualify. The standard example of a low-selectivity index is one on sex.

Many MySQL indexes on a non-key field A are really dual-attribute indexes on (A,PK) where PK is the primary key.

In a multi-attribute index, MySQL can use attributes up until the first one not involved in an equality comparison (that is, not used or involved in an inequality). If the index is on attributes (A,B,C), then the index can be used to answer:

    A>10
    A=10 and B between 30 and 50
    A=12 and B=40 and C<> 200

The telephone book is an index on (lname, fname). It can find people with lname='dordal' quickly, but is not very useful in finding people with fname='peter'.

Sometimes a query can be answered by using ONLY the index. In that case, the index is said to be a covering index for that query. For example, if we have an index for EMPLOYEE on (dno,ssn), then we can answer the following query using the index alone:

    select e.ssn from employee e where e.dno = 5

The (dno,ssn) index is a covering index for this query.

For the phone book, an index on (lname, fname, phone) would be a covering index for phone-number lookups, but not, say, for address lookups.

For the works_on table, an index on (essn,pno,hours) ((essn,pno) is the primary key) is a covering index for the whole table.

If the query is 

select e.lname from employee e where e.salary = 30000 and e.dno = 5;

then while the ideal index is a common index on either (salary,dno) or (dno,salary), two separate indexes on (salary) alone and on (dno) alone are almost as useful, as we can look up the employees with salary = 30000 and the employees in dno 5 and then intersect the two sets. The strategy here is sometimes called "index merge".

Sometimes, if the key is a long string (eg varchar(30)), we build the index on just a prefix of the string (maybe the first 10 characters). The prefix length should be big enough that it is "selective": there should be few records corresponding to each prefix. It should also be short enough to be fast. If a publisher database has an index for book_title, of max length 100 characters, what is a good prefix length? 10 chars may be too short: "An Introdu" matches a lot of books. How about 20 characters? "An Introduction to C" is only marginally more specific.

Query Analysis on Oracle

• row packing
• caching
• optimizer settings
• disk/ram tuning

Mostly we will ignore these. The first step, in any case, is with the queries.

Oracle provides the SQL Performance Analyzer (SPA) tool, which takes a set of queries known as the SQL Tuning Set, or STS, and figure out what the DBA should consider optimizing. In many cases the SPA tool will recommend the addition of specific indexes.

The Oracle version of MySQL's explain is the explain plan command. I have not worked with this, but there is an article describing it at http://www.oracle.com/technetwork/database/bi-datawarehousing/twp-explain-the-explain-plan-052011-393674.pdf.

Aside from creation of indexes, Oracle also supports collection of a wide-ranging set of table statistics, beyond MySQL's basic row counts. Analysis of these statistics is sort of what the SPA tool does.

Adaptive Query Optimization

Here is a brief example from the tuning guide above, at http://docs.oracle.com/cd/E16655_01/server.121/e15858/tgsql_optcncpt.htm#TGSQL221. The sample query is (slightly edited):

SELECT product_name  
FROM   order_items o join product_information p on p.product_id = o.product_id
WHERE  o.unit_price = 15 
AND    o.quantity > 1  

Optimizer Hints

• single-table
• specification of what INDEX to use
• USE_NL to request a Nested Loop join
• multiple-table
• LEADING allows a suggestion of what tables to start with (eg to join first)
• query block
• UNNEST: applies to nested queries
• STAR_TRANSFORMATION: One table is the center of the "star" and multiple other tables are accessed relative to the center, but not relative to one another
• ALL_ROWS

Here are a couple of Oracle's examples. The first is an index suggestion:

SELECT /*+ INDEX (employees emp_department_ix)*/ employee_id, department_id
FROM   employees 
WHERE  department_id > 50;
 

Here is an example of LEADING, which suggests that the join begin with tables e and j:

SELECT /*+ LEADING(e j) */ *
FROM   employees e, departments d, job_history j
WHERE  e.department_id = d.department_id
AND    e.hire_date = j.start_date;