GATE CSE 2011 | Question: 39

Question

Consider a relational table $r$ with sufficient number of records, having attributes $A_1, A_2, \dots ,A_n$ and let $1 \leq p \leq n$. Two queries $Q1$ and $Q2$ are given below.

• $Q1: \pi_{A_1, \dots ,A_p} \left(\sigma_{A_p=c}\left(r\right)\right)$ where $c$ is a constant
• $Q2: \pi_{A_1, \dots ,A_p} \left(\sigma_{c_1 \leq A_p \leq c_2}\left(r\right)\right)$ where $c_1$ and $c_2$ are constants.

The database can be configured to do ordered indexing on $A_p$ or hashing on $A_p$. Which of the following statements is TRUE?

• A. Ordered indexing will always outperform hashing for both queries
• B. Hashing will always outperform ordered indexing for both queries
• C. Hashing will outperform ordered indexing on $Q1$, but not on $Q2$
• D. Hashing will outperform ordered indexing on $Q2$, but not on $Q1$

Comments

Useful link: http://www.cs.sfu.ca/CourseCentral/354/zaiane/material/notes/Chapter11/node21.html

Answer 1

(C) Hashing works well on the 'equal' queries, while ordered indexing works well better on range queries too. For ex consider B+ Tree, once you have searched a key in B+ tree , you can find range of values via the block pointers pointing to another block of values on the leaf node level.

Comments

outperform == perform better.

---

Can someone please share any good reference for this concept,

Hashing Vs Ordered Indexing

---

Hope it helps a bit.

If record are accessed for a particular value from table, hashing will do better.

If records are accessed in a range of values, ordered indexing will perform better.

https://www.geeksforgeeks.org/gate-gate-cs-2011-question-39/

Answer 2

http://www.cs.sfu.ca/CourseCentral/354/zaiane/material/notes/Chapter11/node21.html

it explains with the same example

Comments

@vijju532 Thanx !

Answer 3

Typically, ordered indexing is used unless it is known in advance that range queries will be infrequent, in which case hashing is used like Q2:πA1,…,Ap(σc1≤Ap≤c2(r)) . Hash organizations are particularly useful for temporary files created during query processing, if lookups on a key value are required and no ranges queries will be performed like Q1:πA1,…,Ap(σAp=c(r)).

c is correct

Answer 4

Hashing is generally better at retrieving records having a specified value of the key.

If range queries are common, ordered indices are to be preferred.

https://www.cse.iitb.ac.in/~sudarsha/db-book/slide-dir/ch12.pdf

Comments

Indexing perform better in range queries like in B+-trees.