Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

While reading Graph Databases book, I came across this excerpt:

enter image description here

I can't figure out why the second query is more expensive than the first. Indeed, both filter on the Bob person.

May anyone explain it?

share|improve this question
up vote 5 down vote accepted

The book is assuming that PersonFriend is indexed on PersonID, but not on FriendID. It also seems to assume that Person indexes PersonID and Person independently.

If this is the case, the first query comes back as

  1. {INDEX UNIQUE SCAN Person on Person => 'Bob' get back PersonID}
  2. {INDEX RANGE SCAN PersonFriend on PersonID => PersonIDs for Alice and Zack get back FriendID}
  3. {LOOP {INDEX UNIQUE SCAN Person on PersonID} for Alice and Zack}

Then the second comes back as

  1. {INDEX UNIQUE SCAN Person on Person => 'Bob' get back PersonID}
  2. {TABLE ACCESS FULL PersonFriend FOR FriendID of Bob get back PersonID}
  3. {LOOP {INDEX UNIQUE SCAN Person on PersonID} for friend(s)}

This would be an elementary relational database design error. With a relationship table like this you would always index all keys, and the performance profile for both queries would be indistinguishable (ignoring variations in value distributions, etc).

At this point it sounds like the author is trying to show that relational databases are intrinsically deficient.

share|improve this answer
Thanks for this answer :) I was thinking the same => "The book is assuming that PersonFriend is indexed on PersonID, but not on FriendID". So if I well figure it out, if FriendID was also indexed, both queries would be similar regarding performance. Howerver the book explains that adding another index for this column (FriendId) would be expensive (in memory, etc..). Am I right? – Mik378 Jul 13 '14 at 15:52
One problem with database "expertise" is that it decays. Indexes typically cost most in add/update/delete performance, but even then, it is practically unnoticeable. The additional storage on an index I also consider unnoticeable. The cost of storage is crazy low now! Concerns like these are fifteen years out-of-date if not more. – Andrew Wolfe Jul 13 '14 at 18:13
So you mean that the argument provided by the book isn't relevant due to the low cost of a potential index on the FriendId column? – Mik378 Jul 13 '14 at 18:30
Yes, I wouldn't hesitate for a minute to add the other index. Moreover, if the column has an FK constraint on it you're crazy not to because it increases the cost of deletes to the MASTER (Person) table. – Andrew Wolfe Jul 15 '14 at 0:47
Understood! Thanks a lot Andrew for this great answer :) – Mik378 Jul 15 '14 at 6:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.