## Theoretical evaluation of SQL query cost

Question

I need to evaluate a SQL query in theory by analyzing the results and the number of lines looked upon. Any link to information online is welcomed as I couldn't find help about this issue anywhere.

## What I learned in class

Suppose I have 2 tables,

• A contains 100 tuples
• B contains 500 tuples.

Notation : ```|A| is the number of tuples after the query {A} is the number of tuples examined to produce the query```

I've been shown that

``````R = |A JOIN B| = 500 (we take the biggest of the two)
{A JOIN B} = 100 * 500 = 50 000 (we need to check every tuple)

R' = |R WHERE NO=1| = 5 (we suppose each no has 5 occurences)
{R'} = 500 (we had to loop through the 500)

R'' = |R'[name]| ~5
{R''} = 5
``````

## My question

• A contains 50 tuples
• B contains 100 tuples.

`R = |A JOIN B|`

My teacher says that {A JOIN B} cost 150, 100 to go through B and 50 to go through A. But why isn't this 50*100 like in the previous example?

He further says that a restriction applied after the joint costs 5000, the total number of lines being of 1500 in the joint table. Wouldn't the number of lines be 50*100?

Show source