Query processing in DBMS

[momentum]

Main Question or Discussion Point

This is written in my book.

Can you please reply to these queries in Q1 & Q2.

I'm stuck on those

 

[.Scott]

1) A and B are attributes of relations R and S respectively. If you are thinking in terms of a spread sheet, then you could call them columns. If you are thinking of the relation as files and records, then they would be fields.
2) A DBMS is implemented as file(s). The records in those files is in some order - sorted or not.

For example:
R may be a relation that lists your customer and S may be a relation that is a phone directory.
R is implemented as a file named RF with records ordered by the "customer number" field.
S is implemented as a file names SF with records ordered by the "last name" and "first name" fields.

And say we want to do a "EQUIJOIN" between relation R, attribute "business phone" and relation S, attribute "number".
So this is what we do:
1a) If we already have an index into file RF that is sorted by "business phone", then we skip to step 2.
1b) We build an index into the records in RF that includes field "business phone".
1c) We sort that index by "business phone".

2a) If we already have an index into file SF that is sorted by "number", then we skip to step 3.
2b) We build an index into the records in SF that includes field "number".
2c) We sort that index by "number".

3) We step through those two sorted indexes looking for matches.

Relational terms: relation, tuple, attribute
File terms: file, record, fields.
Spreadsheet terms: sheet, row, column

 

[PeterDonis]

This is written in my book.

What book?

 

[momentum]

1) A and B are attributes of relations R and S respectively. If you are thinking in terms of a spread sheet, then you could call them columns. If you are thinking of the relation as files and records, then they would be fields.
2) A DBMS is implemented as file(s). The records in those files is in some order - sorted or not.

For example:
R may be a relation that lists your customer and S may be a relation that is a phone directory.
R is implemented as a file named RF with records ordered by the "customer number" field.
S is implemented as a file names SF with records ordered by the "last name" and "first name" fields.

And say we want to do a "EQUIJOIN" between relation R, attribute "business phone" and relation S, attribute "number".
So this is what we do:
1a) If we already have an index into file RF that is sorted by "business phone", then we skip to step 2.
1b) We build an index into the records in RF that includes field "business phone".
1c) We sort that index by "business phone".

2a) If we already have an index into file SF that is sorted by "number", then we skip to step 3.
2b) We build an index into the records in SF that includes field "number".
2c) We sort that index by "number".

3) We step through those two sorted indexes looking for matches.

Relational terms: relation, tuple, attribute
File terms: file, record, fields.
Spreadsheet terms: sheet, row, column

okay. But it says "Pair of file blocks" (marked in red) . What is this ? Could you please elaborate this part a bit

 

[.Scott]

okay. But it says "Pair of file blocks" (marked in red) . What is this ? Could you please elaborate this part a bit

What I described was an index sort. In their description, they are creating two files, one from relation R the other from S. Both are sorted.
They are then reading from each of these files, a block at a time. Blocks are the smallest unit that can be read from the file system - typically 512, 1K, 2K, or 4K bytes. So it will read one block from R and one block from S - thus a pair.

 

[momentum]

What I described was an index sort. In their description, they are creating two files, one from relation R the other from S. Both are sorted.
They are then reading from each of these files, a block at a time. Blocks are the smallest unit that can be read from the file system - typically 512, 1K, 2K, or 4K bytes. So it will read one block from R and one block from S - thus a pair.

Okay. this is better.

Some more doubts on this.

They also said

"blocks are copied into memory in order " ---------> what does it mean by in order here ? Is not they are copied separately

"records are scanned ....... each for matching with the other file" -------> does it mean only the matching records (i.e output from join) are copied ? Not the entire R & S is copied ?

 

[willem2]

"blocks are copied into memory in order " ---------> what does it mean by in order here ? Is not they are copied separately

First the first block of R is read into memory. Once it's clear that there are no more mathches with S possible for this block, the next block is read from the file.

"records are scanned ....... each for matching with the other file" -------> does it mean only the matching records (i.e output from join) are copied ? Not the entire R & S is copied ?

Only the matching records are copied. Thats is the idea with an equi-join.

The whole description of a merge-join looks like something of 50 years ago, with tape drives and very small memories. The only thing that seems to be relevant for the runtime, is the time to read or write a block. Nowadays you try to read as much as possible of the files into memory while sorting them. A temporary index will likely be created instead of sorting the files themselves, because only the index column would have to be loaded into memory.

 

[jtbell]

"blocks are copied into memory in order " ---------> what does it mean by in order here ?

It probably means "in sequence". That is, blocks are read from each file in the same (linear) sequence in which they are stored: record #1, record #2, record #3, etc.

 

[momentum]

Thanks . That was very much helpful.

Please see this below.