HW5

Q1. [30 pts]

In this problem, we will examine how B-tree indexes affect query performance in MySQL.

Two tables have been created in the cse30246 database using IMDb movie data:

  • hw5_titles_noidx — 461,318 movie records with no explicitly defined indexes.
  • hw5_titles_idx — The same 461,318 movie records, with B-tree indexes on tconst, primaryTitle, and startYear.

These tables are identical except that one has indexes and one does not.

SHOW INDEX FROM hw5_titles_noidx;
SHOW INDEX FROM hw5_titles_idx;

Here use EXPLAIN ANALYZE to observe how MySQL executes each query. Record the execution time and identify whether MySQL does a table scan, index lookup, or index range scan.

Execution times will vary depending on server load and caching. I am mostly interested in why a query takes longer than another.

(a) Consider the following query

EXPLAIN ANALYZE
SELECT *
FROM hw5_titles_noidx
WHERE tconst = 'tt0114709';

Run the same query against hw5_titles_idx.

  1. Report the execution time for each query.
  2. Approximately how many rows are examined in each case?
  3. Explain why one query is significantly faster than the other.

(b) Prefix Search. Suppose we want to count the movies whose titles begin with Star:

EXPLAIN ANALYZE
SELECT COUNT(*)
FROM hw5_titles_noidx
WHERE primaryTitle LIKE 'Star%';

Run the same query against hw5_titles_idx.

  1. Report the execution time for each query.
  2. Does MySQL use an index in the second query? If so, which one?
  3. Explain why a B-tree index can efficiently support a prefix search.

(c) Suffix Search. Now consider movies whose titles end with ‘Wars’.

EXPLAIN ANALYZE
SELECT COUNT(*)
FROM hw5_titles_noidx
WHERE primaryTitle LIKE '%Wars';

Run the same query against hw5_titles_idx.

  1. Report the execution time for each query.
  2. Does the indexed table perform significantly better? Why/why not?

(d) Range Searches. Suppose we want to count movies released between 1990 and 2000.

EXPLAIN ANALYZE
SELECT COUNT(*)
FROM hw5_titles_noidx
WHERE startYear BETWEEN 1990 AND 2000;

Run the same query against hw5_titles_idx.

  1. Report the execution time for each query.
  2. Identify the access method used in each execution plan.
  3. Is one faster than the other? Why/Why not?

Q2. [30 points]

Consider the following query:

EXPLAIN ANALYZE
SELECT /*+
    NO_MERGE(M)
    NO_DERIVED_CONDITION_PUSHDOWN(M)
*/
    COUNT(*)
FROM (
    SELECT tconst, primaryTitle, startYear, runtimeMinutes
    FROM hw5_titles_idx
) AS M
WHERE M.primaryTitle LIKE 'Star%';

Note: The NO_MERGE(M) and NO_DERIVED_CONDITION_PUSHDOWN(M) turn off parts of the MySQL Optimizer.

(a) Run the query and report the number of rows materialized, number of matching rows, and execution time.

(b) Rewrite and rerun the query by un-restricting the optimizer (removing the NO_MERGE and NO_DERIVED_CONDITION_PUSHDOWN hints). Report the number of rows materialized, number of matching rows, and execution time.

(c) Explain why the optimized query is faster. Note relational algebra transformations and index usage.

Next let’s extend this to joins.

To do this lets count the movies appearing in both hw5_titles_idx and hw5_titles_noidx whose titles begin with Star

EXPLAIN ANALYZE
SELECT /*+ NO_MERGE(J) NO_DERIVED_CONDITION_PUSHDOWN(J) */
    COUNT(*)
FROM (
    SELECT A.tconst, A.primaryTitle
    FROM hw5_titles_idx A
    JOIN hw5_titles_noidx B
        ON A.tconst = B.tconst
) AS J
WHERE J.primaryTitle LIKE 'Star%';

This query deliberately asks MySQL to:
Join all matching records from A and B, then Materialize the join result, then Apply the Star% filter, and finally Count the remaining Records

(d) How long did this query take? How many records did it materialize?

Now lets allow the optimizer to move the selection before the join:

EXPLAIN ANALYZE
SELECT 
    COUNT(*)
FROM (
    SELECT A.tconst, A.primaryTitle
    FROM (
        SELECT tconst, primaryTitle
        FROM hw5_titles_idx
        WHERE primaryTitle LIKE 'Star%'
    ) AS A
    JOIN hw5_titles_noidx B
        ON A.tconst = B.tconst
) AS J;

This explicitly filters A before joining it with B.

(e) How long did this query take? How many records did it materialize?

(f) Provide the unoptimized relational algebra and the optimized relational algebra for this query.

Q3 [20 points]

Suppose that three consistency constraints on a database are:

0≤A≤B, 0≤C≤D, and 0≤X≤Y.

Tell whether each of the following independent transactions traces preserves consistency if they were to be executed completely.

  • X = Y+1; Y = X+1;
  • A = A+B; B = A+B;
  • D = C+D; C = C+D;

Q4 [20 points]

For each of the transactions in Question 3, add the read and write actions to the computation and show the effect of the steps on the main memory, disk, and in an UNDO log.

Assume initially that {A,C,X}=4 and {B,D,Y}=14 on disk.