Index là thủ thuật rất phổ biến trong việc tăng hiệu suất tìm kiếm và sắp xếp các dữ liệu trong Database. Bài viết này sẽ tìm hiểu khái niệm cơ bản của Index đặc biệt là trong MongoDB
Index hay được gọi thuần việt là chỉ mục, một kĩ thuật rất phổ biến trong Database dùng để tăng cao hiệu suất query. Đặc biệt khi Database đó có rất nhiều dữ liệu giả sử là 10000 record, chúng ta không thể nào quét tuyến tính từ 1 đến 10000 để tìm được.
Chỉ mục trong đời sống cũng như khi chúng ta đi vào nhà sách tìm sách thì không thể nào tìm tuần tự từng quyển sách mà nhà sách đã đánh dấu cho ta từng khu theo từng loại sách khác nhau từ đó mà ta có thể tìm kiếm dễ dàng
TLDR: MongoDB sử dụng B-tree(ctdl dựa trên BST nhưng tối ưu hoá về việc truy cập và lưu bộ nhớ) với độ phức tạp tìm kiếm là O(log(n)) thay vì O(n)
Vậy làm sao để MongoDB có thể tìm kiếm nhanh bằng cách đánh Index?
Cứ tưởng tượng MongoDB lưu dữ liệu chúng ta là 1 mảng nối dài các ObjectID tuần tự tăng dần. Khi ta tìm field gì đó giả sử là score = 2 trong collection Student. MongoDB sẽ dùng "column scan" duyệt tiến tính từ đầu đến cuối để tìm ra score = 2 độ phức tạp sẽ là O(n).
Khi áp dụng Index, MongoDB sẽ sử dụng B-tree và lúc này tìm kiếm với độ phức tạp chỉ là O(log(n))
Tại sao lại là B-tree
Mình nghĩ do B-tree thích hợp với việc tối ưu hoá truy cập ổ đĩa, so với cây BST mỗi nút chỉ chứa 1 khoá, B-tree có thể chứa nhiều hơn 2 con điều này sẽ giảm được chiều cao của cây.
Giả sử ta lưu 10 số điểm của học sinh insert vào DB lần lượt là: 1, 3, 4, 5, 7, 8, 9, 2, 6, 0.
// cây BST
1
\
3
/ \
2 4
/ \
0 5
\
7
/ \
6 8
\
9
// cây B-tree (t=3) t: là độ lớn tối thiểu
4,7
/ | \
1,3 5,6 8,9
/ |
0 2
Bạn có thể thực hành qua B-tree visualization tại đây
Mình thiết kế schema Student phục vụ cho việc thực hành
const studentSchema = new mongoose.Schema({
name: { type: String, required: true },
age: { type: Number, required: true },
gpa: { type: Number, required: true },
gender: { type: String, enum: ["male", "female"], required: true },
location: {
city: { type: String },
street: { type: String },
},
});
const student = mongoose.model("student", studentSchema);
Generate 100 Student
async function main() {
await connectDB();
for (let index = 0; index < 100; index++) {
await student.create({
name: "student" + index,
age: Math.floor(Math.random() * 100),
gpa: (Math.random() * 4).toFixed(2),
gender: ["male", "female"][Math.floor(Math.random() * 2)],
});
}
}
Mở mongosh để query, ví dụ mình sẽ tìm những người có GPA lớn hơn 3.5. Nhưng lần này mình sẽ thêm explain() để phân tích query
db.students.find({gpa: {$gt: 3.5}}).explain("executionStats")
Kết quả
{
explainVersion: '2',
queryPlanner: {
namespace: 'student.students',
indexFilterSet: false,
parsedQuery: {
gpa: {
'$gt': 3.5
}
},
queryHash: 'D37FC761',
planCacheKey: 'A1F174F1',
maxIndexedOrSolutionsReached: false,
maxIndexedAndSolutionsReached: false,
maxScansToExplodeReached: false,
winningPlan: {
queryPlan: {
stage: 'COLLSCAN',
planNodeId: 1,
filter: {
gpa: {
'$gt': 3.5
}
},
direction: 'forward'
},
},
rejectedPlans: []
},
executionStats: {
executionSuccess: true,
nReturned: 13,
executionTimeMillis: 0,
totalKeysExamined: 0,
totalDocsExamined: 100,
executionStages: {
stage: 'filter',
planNodeId: 1,
nReturned: 13,
executionTimeMillisEstimate: 0,
opens: 1,
closes: 1,
saveState: 0,
restoreState: 0,
isEOF: 1,
numTested: 100,
filter: 'traverseF(s4, lambda(l1.0) { ((l1.0 > s7) ?: false) }, false) ',
inputStage: {
stage: 'scan',
planNodeId: 1,
nReturned: 100,
executionTimeMillisEstimate: 0,
opens: 1,
closes: 1,
saveState: 0,
restoreState: 0,
isEOF: 1,
numReads: 100,
recordSlot: 5,
recordIdSlot: 6,
fields: [
'gpa'
],
outputSlots: [
4
]
}
}
},
command: {
find: 'students',
filter: {
gpa: {
'$gt': 3.5
}
},
'$db': 'student'
},
}
Chúng ta để ý property queryPlan có stage là 'COLLSCAN', có nghĩa là MongoDB đã tìm tuyến tính. Làm rõ nhất giá trị của totalDocsExamined = 100 cho ta thấy được số docs mà MongoDB đã quét ra, bằng với length luôn 😳😳
Thật là painful nếu chúng ta không sử dụng Index đúng không? Hãy tạo Index để cùng so sánh xem hiệu quả thế nào
Cách tạo rất đơn giản đó là
db.<collection>.createIndex(
{ <field>: <value> },
{ name: "<indexName>" }
)
db.students.createIndex({gpa: 1})
// gpa_1
name là optional, kết quả trên chính là default name của Index
Nếu muốn đặt tên ta phải lưu ý:
Value ở đây là sortOrder giá trị 1 có nghĩa là tăng dần. Đây chính là Single Field Indexes
Một lưu ý nữa là _id mặc định được đánh Index, đó là tại sao ta có thể dùng cursor_based_pagination trong MongoDB
Do có rất nhiều kiểu đánh Index nên bài viết sau mình sẽ giải thích kĩ hơn
Ngoài ra có thể tạo Index bằng MongoDB Atlas
Bây giờ đã có Index cho field gpa, hãy cùng query đễ check xem liệu có hiệu quả không
db.students.find({gpa: {$gt: 3.5}}).explain("executionStats")
💡Tips
Chúng ta có thể gán biến như JS cho nhanh
const query = db.students.find({gpa: {$gt: 3.5}}).explain("executionStats")
query
Kết quả trả về
{
explainVersion: '2',
queryPlanner: {
namespace: 'student.students',
indexFilterSet: false,
parsedQuery: {
gpa: {
'$gt': 3.5
}
},
queryHash: 'D37FC761',
planCacheKey: 'E846F976',
maxIndexedOrSolutionsReached: false,
maxIndexedAndSolutionsReached: false,
maxScansToExplodeReached: false,
winningPlan: {
queryPlan: {
stage: 'FETCH',
planNodeId: 2,
inputStage: {
stage: 'IXSCAN',
planNodeId: 1,
keyPattern: {
gpa: 1
},
indexName: 'gpa_1',
isMultiKey: false,
multiKeyPaths: {
gpa: []
},
isUnique: false,
isSparse: false,
isPartial: false,
indexVersion: 2,
direction: 'forward',
indexBounds: {
gpa: [
'(3.5, inf.0]'
]
}
}
},
},
executionStats: {
executionSuccess: true,
nReturned: 13,
executionTimeMillis: 0,
totalKeysExamined: 13,
totalDocsExamined: 13,
...
}
command: {
find: 'students',
filter: {
gpa: {
'$gt': 3.5
}
},
'$db': 'student'
},
ok: 1
}
Ta có thể thấy queryPlan có kiểu stage là 'IXSCAN' có nghĩa là Index thay thì 'COLLSCAN' như lúc trước. Đặc biệt lúc này totalDocsExamined chỉ còn là 13 thay vì 100. Thật sự hiểu quả phải không các bạn
Tuy nhiên cùng đừng vì thế mà sử dụng Index vô tội vạ, nó sẽ phản tác dụng rất nhiều vì khi chúng ta thêm xoá dữ liệu, nó sẽ update lại toàn bộ Index để đảm bảo tính chính xác
Như vậy chúng ta đã tìm hiểu sơ qua khái niệm Index là gì rồi, nhưng như vậy là chưa đủ, Index có nhiều kiểu khác nhau và còn nhiều trường hợp sử dụng nữa có thể kể đến như Compound Index, full text search,... Bài viết sau sẽ là nối tiếp của bài viết này để có thể tìm hiểu rõ hơn về Index
Hi vọng bài chia sẻ này hữu ích với mọi người!
Cheers 🍺
-
10 months ago
hay
-
a year ago
a