NoSQL Databases: Graph, Column, Wide-column, In-memory, Search & Vector

1. NoSQL 概覽（slides 2–3）

NoSQL stands for Not Only SQL，係 a broad class of non-relational DBMS。Slide 特別 note：有啲 NoSQL database 都係用 table structure，所以唔好將 NoSQL 等同「冇 table」。

ExamNoSQL 通常支援 flexible schema，過去十年喺新 applications / companies 好流行，原因係 agile development：requirements change rapidly，而 database schema 一改，就要 migrate 現有 data 去新結構。

2. Graph database（slides 4–5）

Graph 其實可以用 table 表示（slide 4 嘅 edge table，共 4 個 nodes）：

From	To	Weight
1	2	3
2	3	4
3	1	5
3	4	5

既然 table 都存到，點解仲要 graph database？

3. Graph analytics（slides 6–10）

Fraud detection 例子（slide 8）

ExamTarget scenario：有人操作幾百個 fake accounts。Observation：佢哋無可避免會共用 subtle resources，例如同一個 IP address、credit card、Wi-Fi network 或 delivery address。

Graph construction：Node = Account；兩個 accounts 有一個或以上 features 相同就連 edge。Fake accounts 就會形成一個大嘅 weakly connected component。

Handling false positives	做法
Filtering supernodes	排除例如 public computers，因為好多無關嘅人都會共用
Weights and thresholds	同 IP = low weight；同 credit card = high weight；common features 越多 weight 越高；再設 strict connectivity threshold，例如要有一條 high-weight path，或多條 medium-weight paths
Temporal relationship	只考慮 tight time window（例如 30 mins）內嘅 activities

4. Knowledge Graph 同 RDF（slides 11–12）

Knowledge Graph 曾經係 AI 嘅 leading techniques 之一：IBM Watson 喺 2011 年嘅問答節目 Jeopardy 贏咗兩位 human experts。Slide 11 嘅圖用 nodes 同 edges 表達知識，例如 Da Vinci painted Mona Lisa、Mona Lisa is in Louvre。

ExamRDF (Resource Description Framework) 技術上係一個 graph，每個 RDF record 有 3 個 components：Subject、Predicate、Object。命名用 URI-based vocabularies（同 linked data 一樣），query language 係 SPARQL（the query language of the Semantic Web）。

Subject	Predicate	Object
Da Vinci	painted	Mona Lisa

5. Column-oriented database（slides 13–19）

Exam核心分別：Standard RDBMS stores data by rows；column-oriented database stores data by columns（C-Store，Stonebraker et al., VLDB 2005）。例子 KDB 喺 financial industry 幾流行，支援 time-series data，query language 係 Q，不過 difficult to learn。Slide 13 附咗一張香港 Citibank KDB Engineer 招聘截圖，顯示業界需求。

Sample data（slide 14）：

x1	x2	x3	x4
x5	x6	x7	x8
x9	x10	x11	x12

Storage	Data on disk
RDBMS（by rows）	x1, x2, x3, x4, …, x11, x12
Column-oriented（by columns）	x1, x5, x9 | x2, x6, x10 | x3, x7, x11 | x4, x8, x12

Compression（slide 17）

ExamColumn-based compression 可以有較高 compression rate，因為 data within the same column are of very similar nature，帶來 lower storage cost 同 faster processing speed。

Sample use case（slide 19）

好適合 data analytics in finance：有好多 columns（MACD、RSI、Bollinger Bands 等 technical analysis），但 quantitative analysis 通常只用少數 columns，例如計一個 feature 嘅 mean、standard deviation、confidence intervals，或者兩個 features 嘅 correlation。

6. Wide-column database（slides 20–29）

ExamPurpose：make the database highly scalable by horizontal scaling。例子：Cassandra、HBase。源頭係 Google Bigtable（OSDI 2006）。

6.1 由 RDBMS 到 Bigtable（slides 21–22）

將多個 tables join 成一張 single big table，呢張 table 有咩特性？Big 同 Sparse，好多格都係空嘅。

Sample data（slide 23）：

ID	Name	Association	Hobby
1	Amy	Red Cross
2	Bob		Badminton

對應嘅 Bigtable data：

Row ID	Column	Time	Value
1	Name	1 Jan 2020	Diana
1	Name	1 Jan 2023	Amy
1	Association	1 Jan 2020	Red Cross
2	Name	1 Jan 2020	Bob
2	Hobby	1 Jan 2020	Badminton

留意三件事：Row 1 嘅 Name 有兩個 versions，最新係 Amy；空格（Amy 冇 Hobby）根本唔使儲，就係 no null overhead；要還原返關係型嗰張 table，就要 self-join（slide 24）。

6.2 Query（slide 25）

Wide-column database 一般唔用 SQL。Cassandra 用類似 SQL 嘅 Cassandra Query Language (CQL)，但 CQL 冇 JOIN operator。

6.3 Append-only logs 同 LSM tree（slide 26）

有新 update 時，只係 insert 一個新 version，updates are processed sequentially。

6.4 優缺點（slides 27–28）

Example applications（slide 29）：IoT & sensor data logging（大量 devices 持續發 data）；Discord 用 ScyllaDB，因為 chat applications 有 heavy write volume，而且可以按 channels 自然 partition。

7. In-memory key-value database：Redis（slides 30–37）

7.1 點解 in-memory？（slides 30、33）

Storage	Benchmark read/write speed
Magnetic harddisk	80 MB/s – 160 MB/s
SSD harddisk	200 MB/s – 550 MB/s
RAM (Memory)	2 GB/s – 20 GB/s

ExamRAM 最快，但 volatile：一斷電 data 就冇晒。Redis 嘅做法係 data 主要放 RAM，permanent storage（例如 harddisk）作 backup。

另一個問題：RAM is expensive and limited，所以 compression is critical。Slide 33 嘅價錢截圖：8TB HDD 賣 $2699，16GB RAM 賣 $1499，以每 GB 計 RAM 貴接近 280 倍。Trade-off：compression / decompression 有 computational cost，最終 performance 視乎 data 嘅性質。

7.2 Redis 特性（slide 31）

• Key-value store，例如 key "session:auth:98342" 對應 {"user_id": "usr_01H7X", "status": "authenticated"}。
• Index on key only，唔支援其他 fields 嘅 secondary index，所以 querying power 有限。
• Simple sharding：hashed sharding，without strong consistency check。
• Optimized for speed but sacrifice consistency。

7.3 Persistence options（slide 32）

7.4 Indexing（slide 34）

Exam傳統 indexing（例如 B-tree）唔適合 in-memory database：佢哋係為 I/O optimal 而設計，放喺 memory 就 suboptimal。Preferred 方法係 Hash table：$O(1)$ time access，但 no range queries。

7.5 NVRAM（slide 35）

Non-volatile RAM：比 volatile RAM 慢，但 power off 都保留 data。現時 Redis 冇用 NVRAM 做 primary memory，不過可以作較快嘅 backup and recovery layer。

7.6 Use cases 同其他系統（slides 36–37）

Use case	原因
User session management	暫存 visit 期間嘅 user data（例如 shopping cart），冇 activity 一段時間就 expire
Leaderboards in gaming	大量 players 要 fast update
High-Frequency Trading	需要 low latency

Other in-memory databases	特點
VoltDB	For relational data；NewSQL
SAP HANA	Column-oriented storage
Memcached	Key-value store，even simpler than Redis

8. Search engine：Elasticsearch（slides 38–41）

Data 係 JSON 格式嘅 documents，Exam核心係 inverted index：mapping words to document IDs。

ID	Term	Document
1	butterfly	1
2	blue	1, 2
3	bright	1, 2

Elastic Stack (ELK)（slide 39）：

Component	角色
Logstash	Data pipeline tool，由多個 sources ingest data
Elasticsearch	The core engine
Kibana	Frontend interface

Analysis pipeline：由 text 到 terms（slides 40–41）

9. Relevance score 同 TF-IDF（slides 42–49）

點解要 rank？簡單 term matching 通常返回大量 documents，但唔知邊份較 relevant。Relevance score 就係代表 document 同 search query 相關程度嘅數值。流行演算法係 BM25（Best Matching），由 TF-IDF 改良而成。

9.1 Formula（slides 43–45）

$\text{TF}(t,d)$ 係 term $t$ 喺 document $d$ 嘅 term frequency；$\text{IDF}(t)$ 係 inverse document frequency，對所有 documents 都一樣。

9.2 例題（slides 43、46–49）

Corpus：

• $d_1$：The cat sat on the mat.
• $d_2$：The cat chased the cat.
• $d_3$：The mouse ran from the cat.

移除 stop words（the、on、from）後，Vocabulary = [cat, chased, mat, mouse, ran, sat]。

Step 1：TF（scikit-learn 版本，即 count）

	cat	chased	mat	mouse	ran	sat
$d_1$	1	0	1	0	0	1
$d_2$	2	1	0	0	0	0
$d_3$	1	0	0	1	1	0

Step 2：IDF（$N=3$）

mat、mouse、ran、sat 都只喺一份 document 出現，所以 IDF 同 chased 一樣，都係 $\ln2+1$。

Step 3：TF × IDF（normalization 之前），例如 $\text{TF-IDF}(\text{cat},d_1)=1\times1=1$：

	cat	chased	mat	mouse	ran	sat
$d_1$	1	0	$\ln2+1$	0	0	$\ln2+1$
$d_2$	2	$\ln2+1$	0	0	0	0
$d_3$	1	0	0	$\ln2+1$	$\ln2+1$	0

Step 4：L2 norms

Step 5：每行除以該行嘅 norm（final result，slide 49）

from sklearn.feature_extraction.text import TfidfVectorizer

corpus = ["The cat sat on the mat.",
          "The cat chased the cat.",
          "The mouse ran from the cat."]

vectorizer = TfidfVectorizer(stop_words=['the', 'on', 'from'])
X = vectorizer.fit_transform(corpus).toarray()
print(vectorizer.get_feature_names_out())  # ['cat' 'chased' 'mat' 'mouse' 'ran' 'sat']
print(vectorizer.idf_)                     # [1. 1.6931 1.6931 1.6931 1.6931 1.6931]
print(X.round(4))                          # 同 slide 49 一樣

Textbook version 比較（自編，唔係 slide 內容）：$\text{IDF}(\text{cat})=\log_{10}(3/3)=0$，所以 cat 嘅 TF-IDF 喺每份 document 都係 0。假設 total terms 以移除 stop words 後計（$d_2$ 有 3 個），$\text{TF-IDF}(\text{chased},d_2)=\frac13\times\log_{10}3\approx0.159$。

10. TF-IDF 嘅問題同 BM25（slides 50–51）

11. Elasticsearch 嘅其他功能同應用（slides 52–53）

Fuzzy search：連相似嘅字都會返回，similarity 用 edit distance 量度。Use case：user 打錯字，想搵 “fox” 但打咗 “box”；兩個字只差一個字母，edit distance 係 1。

Application	做咩
Website search	搵個 phrase 喺網站邊度出現
Enterprise search	搵企業入面邊份 document 有呢個 phrase
Data analytics	統計唔同 search phrases 嘅出現次數再分析，例如喺 treemap 顯示 incident documents 最常見嘅原因

12. Vector database（slides 54–58）

Vector data 例子：User-Product ratings（YouTube、Netflix）、item features（例如 TF-IDF 產生嘅 feature vector）、text / image / 任何 data type 嘅 embedding（Generative AI / LLM，呢度嘅重點）。

Pure vector databases：Pinecone、Qdrant、Chroma、FAISS。隨住 vector database 流行，PostgreSQL、MongoDB、Oracle 等都開始實作 vector functions。

ExamEmbedding model（slide 55）：neural network model，將 data 映射成 dense vector。兩個 inputs semantically similar，佢哋嘅 vectors 就會 close to each other。例子：nomic-embed-text-v2-moe（text，multilingual）、CLIP（image）、Gemini Embedding 2（multimodal）。

自編例子：$x=(1,2,2)$，$y=(2,0,1)$。$x\cdot y=2+0+2=4$，$|x|=3$，$|y|=\sqrt5$，similarity $=\frac{4}{3\sqrt5}\approx0.596$，distance $\approx0.404$。

Slide 58 列出 MongoDB 嘅 options：$similarityCosine、$similarityDotProduct、$similarityEuclidean。

13. kNN 計算：Brute force、IVF、HNSW（slides 59–62）

HNSW 結構（slide 60）：

• A higher layer is a sparser subset of the lower layer。
• 最底嘅 ground layer 包含所有 vectors。
• 每一層，每個 node 都記住 neighbours 嘅 edges。

自我測驗 Self-test

Q1. NoSQL 代表咩？點解 agile development 會令 NoSQL 流行？

Not Only SQL。Requirements 轉得快，而 RDBMS schema 一改就要 migrate 現有 data；NoSQL 通常支援 flexible schema，唔使咁麻煩。

Q2. 點解 graph database 比 RDBMS 更適合搵關係？

RDBMS 要大量 expensive joins。Graph database 用 Index-Free Adjacency，直接儲存相連 nodes 嘅 pointers，traversal time 係 constant。

Q3. 12 rows × 4 columns 嘅 table，每次 disk I/O 讀 3 個 values。Sum 一個 column，row storage 同 column storage 各要幾多次 I/O？

Column storage：12 個 values 連續擺放，12/3 = 4 次。Row storage（以第一個 column 為例）：佢哋喺第 1、5、9、…、45 個位置，每個都落喺唔同 block，所以 12 次。

Q4. 將 A, A, B, B, B, A 用 Run-Length Encoding 壓縮；將 Red, Blue, Red, Green 用 Dictionary Encoding 壓縮。

A2B3A1。1, 2, 1, 3，Dictionary：Red → 1，Blue → 2，Green → 3。

Q5. Bigtable 嘅 data model 係咩？Timestamp 有咩用？

(row:string, column:string, time:int64) → string。Timestamp 令系統可以保存同取得同一格喺唔同時間嘅 versions。

Q6. 解釋 LSM tree；點解 wide-column database write 快但 read 慢？

Writes 先 buffer 喺 memory，間中 flush 成 immutable sorted records，背景 merge and compact。Update 只係 append 新 version，所以 write 快（例如 no locking）；read 就要喺 LSM trees 花功夫搵最新 data，所以 latency 較高。

Q7. 點解 B-tree 唔適合 in-memory database？Hash table 嘅代價係咩？

B-tree 為 I/O optimal 而設計，喺 memory 入面 suboptimal。Hash table 有 $O(1)$ access，但做唔到 range queries。

Q8. 寫出 Redis 嘅 persistence options。AOF 點樣還原 data？

Snapshot、AOF、No persistence、Snapshot + AOF。AOF 記錄每個 write operation，server 啟動時 replay 去重建 dataset。

Q9. 排列 analysis pipeline，並處理 “<b>The Apples ran</b>”。

Character filter → Tokenizer → Normalization → Stopword filter → Stemming filter。結果：The Apples ran → [The, Apples, ran] → [the, apples, ran] → [apples, ran] → [apple, run]。

Q10. 用 scikit-learn 版本：$N=4$，term $t$ 喺 1 份 document 出現，喺 $d$ 出現 3 次。求 TF-IDF（未 normalize）。

$\text{IDF}=\ln\frac{4+1}{1+1}+1=\ln2.5+1\approx1.9163$，TF = 3，所以 TF-IDF $\approx5.749$。

Q11. 同上，改用 textbook 版本，假設 $d$ 共有 10 個 terms。

TF = 3/10 = 0.3；$\text{IDF}=\log_{10}(4/1)\approx0.6021$；TF-IDF $\approx0.1806$。

Q12. BM25 解決咗 TF-IDF 嘅咩問題？

Term frequency saturation（TF 唔再線性上升）、improved length normalization（減少偏向長 documents），而且有 tuneable parameters。

Q13. 比較 IVF 同 HNSW。如果 RAM 好緊張，揀邊個？

IVF：$O(\sqrt{n})$、用較少 RAM、需要 K-means。HNSW：$O(\lg n)$、較快、唔使 re-training、較流行。兩者都只係 approximate。RAM 緊張就揀 IVF。

Q14. 以下情況用邊種 database？(a) 記錄大量 IoT sensor readings；(b) 搵 fake account 集團；(c) 遊戲 leaderboard；(d) 計幾百個 columns 入面某一個 column 嘅 mean；(e) 用意思而唔係關鍵字搜尋文件。

(a) Wide-column；(b) Graph；(c) In-memory（Redis）；(d) Column-oriented；(e) Vector database。

一頁總結 Cheat sheet