推 Arim:所以沒有index的情況下,兩個的時間複雜度都是O(N)嗎? 10/10 15:52
→ FireLake:沒錯 10/11 09:14
※ 引述《Arim (Arim5566)》之銘言：
: 各位版友好
: 對於存取資料庫的時間複雜度有一點困惑
: 假如我有一個table,有n個tuple
: schema有m個屬性,A1,A2...Am,(總共有m個column)
: case 1(只比對一個column):
: select A1
: from emp
: where A1>40
: case 2(比對m個column):
: select A1,A2...Am
: from emp
: where A1>40,A2 == "xxxx"...,Am == "xxx"
: 在作query的時候,是不是會先抓每一個tuple出來,在逐一比對每一個屬性呢?
: 如果是這樣的話那case2就會比case1還要慢?(如果m很大的話)
: 看網路上面很多人寫時間複雜度只有O(n) @@
: 謝謝各位版友的指教
這種問題通常都要先比較 query plan，在沒有index的情況下，你這兩個case
都是要做 full table scan，所以基本上是一樣快。
如果有一個index是在 column A1上，你的case 1是做 index range scan，
case 2 是先做index range scan，再做 table access by row id，所以case 1
會比較快。但要注意的一點是，造成兩個 case 的 query plan 不一樣的原因
不一定是 where，有時是 select。例如，當把你的 case 1 改成
"select A1, A2...Am
from emp
where A1>40"
在這情況下，case 1的query plan就變成和case 2一樣，是先做index range scan，
再做 table access by row id。
總而言之，比較 query plan 就可以大略知道那個 query 比較快。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 69.181.252.242
※ 編輯: FireLake 來自: 69.181.252.242 (10/10 13:10)