IAE Academy

GATE 2024 DA Q.55: solution and answer

GATE 2024 · DAQ.55 · 2 marks · MSQ

An OTT company is maintaining a large disk-based relational database of different movies with the following schema:

Movie(ID, CustomerRating)
Genre(ID, Name)
Movie_Genre(MovieID, GenreID)

(Primary keys underlined in print: Movie.ID; Genre.ID; Movie_Genre.MovieID and GenreID together.)

Consider the following SQL query on the relation database above:

SELECT *
FROM Movie, Genre, Movie_Genre
WHERE
    Movie.CustomerRating > 3.4 AND
    Genre.Name = "Comedy" AND
    Movie_Genre.MovieID = Movie.ID AND
    Movie_Genre.GenreID = Genre.ID;

This SQL query can be sped up using which of the following indexing options?

  1. (A)

    B tree on all the attributes.

  2. (B)

    Hash index on Genre.Name and B tree on the remaining attributes.

  3. (C)

    Hash index on Movie.CustomerRating and B tree on the remaining attributes.

  4. (D)

    Hash index on all the attributes.

See the question in the paper
GATE 2024 DA question 55Tap to open full size

Answer and solution

ANSWER

The query can be sped up by options A and B.

Official answer: A, BSource: Official answer key, GATE 2024 DA (IISc Bengaluru)

  1. Classify each predicate by the access it needs. Movie.CustomerRating > 3.4 is a range condition. Genre.Name = "Comedy" is an equality condition. The two join conditions, Movie_Genre.MovieID = Movie.ID and Movie_Genre.GenreID = Genre.ID, are equalities on key attributes.

  2. A hash index answers only equality lookups, because hashing scatters keys and destroys their order. A B tree keeps its leaves sorted and linked, so it answers both equality and range lookups.

  3. Take an option to speed the query up when every predicate has an index type that can serve it. The range predicate on CustomerRating is the deciding one: it can use an index only if Movie.CustomerRating carries a B tree. A hash index on it cannot answer "rating ", so Movie would still be scanned in full.

  4. Option A: a B tree on every attribute serves the range on CustomerRating, the equality on Name, and the join lookups on ID, MovieID and GenreID. Every predicate is served, so the query is sped up. Correct.

  5. Option B: a hash index on Genre.Name is ideal for the single equality Name = "Comedy". The remaining attributes carry B trees, including CustomerRating (range) and the join keys. Every predicate again has a suitable index, so the query is sped up. Correct.

  6. Option C: the hash index sits on CustomerRating, the one attribute that needs range access. The range filter on Movie therefore gets no usable index, which is exactly the mismatch that defeats the design for this query. The other attributes are indexed, but the option does not match the access pattern, so it is not accepted as a way to speed the query up. Not correct.

  7. Option D: hash indexes on all attributes leave the range predicate on CustomerRating unsupported, for the same reason as C. Not correct.

  8. Only A and B give every predicate a matching index type. The answer is A and B.

KEY IDEA

Match index type to predicate type. Hash indexes serve only equality, whereas B trees serve equality and range. A range predicate such as CustomerRating > 3.4 needs a B tree on that attribute.

WATCH OUT FOR

Assuming a hash index is always faster than a B tree and choosing a hash index on the attribute with the range condition (option C), or hashing everything (option D). Hashing cannot help with a comparison.

From the GATE 2024 DA paper. Every question of this paper · Download the full paper · All 3 Indexing questions, with notes

More Indexing questions