Multi-Key Indexing

• Motivation: queries of the form

  • SELECT … FROM R WHERE cond1 and cond2
  • cond1 and cond2 are equality or range conditions

• Solution 1: use index for only one of the conditions

  • suggested if there is a very selective condition

• Solution 2: pointer intersection

  • fairly selective conditions

SELECT Name FROM Employee

WHERE Dept=“Toys” AND Year > 3

p

s

Dept=“Toys” AND Yearɯ

Name

Rewriting

& Optimization

p

s

Dept=“Toys”

Name

s

Yearɯ

Employee

IND

SCAN

Employee

Previous slide

Next slide

Back to first slide

View graphic version