So I'm just starting to learn about query processing and such in databases and I'm having some trouble. I don't really understand how to compute the minimum number of block reads given a relation and a query I guess you could say. If anyone could help me out, it'd be much appreciated. Here is an example that I'm working on:

  • R1(A,B,C) A is a primary key and C is a foreign key to R2.C
  • R2(C,D,E) C is a primary key
  • R1 has 20,000 records, with 200 records per block. There is a primary B+-tree index on A with height h = 3
  • R2 has 45,000 records, with 4,500 records per block. There is a primary B+-tree index on C with height hC = 3 and a secondary B+-tree index on D with height hD = 2.

Find the minimum number of block reads for each statement. I can only hold one block of memory for each relation at a time.

  • Where B=1(R1)
  • Where C=1(R2)

I'm not looking for answers. I'm looking for explanation of how to actually do it and guide me along the way. Aka equations, etc. It's kind of difficult to find anything beneficial online at all.

  • $\begingroup$ One of the things any RDBMS worth its salt will do extensive query optimization, reorganizing the query to use less reads. $\endgroup$ – vonbrand Apr 22 '13 at 16:33
  • 1
    $\begingroup$ I'm having trouble with interpreting the syntax you are using. I followed the question up until you wrote where B=1(R1). What does that mean? (I understand relational calculus, relational algebra and basic SQL.) $\endgroup$ – Wandering Logic Apr 22 '13 at 17:34

select * from R1 Where B=1

You don't have any index on a search field (B), hence you have to do a full table scan. It means that you fetch all relation's blocks one by one and take the records which satisfy the condition B=1. (Cost - 200000/200 = 200 blocks)

select * from R2 Where C=1

There is not enough information - you have to know(at least approximately) how many records in R2 satisfy the condition C=1. For example in case that all the records in R2 have C=1 you'll do the full table scan like above (cost - 45000/4500 = 10 blocks) On the other hand if you have only one record with C=1 you'll read 3 blocks of index and another one from disk(cost 3 + 1 = 4 blocks)

  • $\begingroup$ Alright, this is all understandable. Thank you so far. What would you do when something gets changed up though for a where, say where D=5 in R2? Also, how would you indexed nested loop join? When I did the indexed nested loop join, I got 20,000 records x (45,000 records / 4,5000 records per block) + 100 blocks = 2,000,100 block reads $\endgroup$ – user7233 Apr 24 '13 at 18:35
  • $\begingroup$ Something seems terrible off about that however, unless I'm just overthinking it. $\endgroup$ – user7233 Apr 24 '13 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy