Nghiên cứu kỹ thuật tiền xử lý dữ liệu trong tối ưu truy vấn cơ sở dữ liệu có kích thước lớn

Công nghệ thông tin 
C. Đ. Huy, N. N. An, “Nghiên cứu kỹ thuật tiền xử lý  dữ liệu có kích thước lớn.” 208 
NGHIÊN CỨU KỸ THUẬT TIỀN XỬ LÝ DỮ LIỆU TRONG 
TỐI ƯU TRUY VẤN CƠ SỞ DỮ LIỆU CÓ KÍCH THƯỚC LỚN 
 Cao Đăng Huy*, Nguyễn Nhật An 
Tóm tắt: Tối ưu hóa cơ sở dữ liệu là một vấn đề rất quan trọng trong việc xây 
dựng các ứng dụng cơ sở dữ liệu. Có nhiều công nghệ và kỹ thuật được áp dụng cho 
việc tối ưu cơ sở dữ liệu như đặt chỉ mục, phân mảnh dữ liệuvv; tuy nhiên với ứng 
dụng có dữ liệu quá lớn hoặc có tần suất truy cập đồng thời rất cao và những truy vấn 
dữ liệu khá phức tạp thì những kỹ thuật này chỉ có thể đạt đến một giới hạn nhất định 
nào đó. Trong bài viết này chúng tôi đề xuất kỹ thuật tiền xử lý dữ liệu nhằm tạo ra 
các dữ liệu có những định dạng phù hợp mà có thể kết hợp với những kỹ thuật truyền 
thống nhằm tối ưu các truy vấn cơ sở dữ liệu có kích thước lớn. Bài viết đồng thời 
cũng phân lớp và đề xuất mô hình triển khai cho việc tiền xử lý dữ liệu một cách hiệu 
quả. Kết quả thử nghiệm cho bài toán reverse geocode trên dữ liệu không gian trên 
tập dữ liệu mẫu mà chúng tôi đề xuất có thể cải thiện tốc độ hơn 54 lần và việc triển 
khai nó trong thực tế cho phép chúng tôi có thể tạo ra được những báo cáo về dữ liệu 
của hàng trăm triệu đến hàng chục tỷ bản ghi trong thời gian chấp nhận được. Điều 
này cho thấy cách tiếp cận này là rất khả quan. 
Từ khóa: Tối ưu cơ sở dữ liệu; Tiền xử lý; Phân mảnh dữ liệu. 
1. ĐẶT VẤN ĐỀ 
Tối ưu hóa về cơ sở dữ liệu là một chủ đề rất được quan tâm và nghiên cứu. 
Khi xây dựng một hệ thống phần mềm với một cơ sở dữ liệu lớn, có nhiều truy vấn 
và cập nhật đồng thời thì vấn đề này là cực kỳ quan trọng vì nó ảnh hưởng rất lớn 
đến sự đáp ứng của hệ thống, trải nghiệm người dùng, thậm chí là sự ổn định, tồn 
vong của cả một hệ thống phần mềm. 
Có nhiều giải pháp để tối ưu hóa cơ sở dữ liệu như chuẩn hóa thiết kế, đặt 
chỉ mục index hợp lý, thiết lập cấu hình hệ thống, tối ưu các câu hỏi truy vấn và 
phân mảnh dữ liệu [4]. Tuy nhiên với dữ liệu có kích thước quá lớn hoặc có tần 
suất truy cập rất cao mà câu hỏi truy vấn dữ liệu lại phức tạp thì những giải pháp 
này chỉ đạt đến một giới hạn nhất định. Đòi hỏi phải có một giải pháp mới để xử lý 
vấn đề này và chúng tôi đề xuất là sử dụng kỹ thuật tiền xử lý dữ liệu. 
Tiền xử lý dữ liệu là quá trình biến đổi dữ liệu sang một định dạng mới 
phục vụ cho một quá trình phân tích, xử lý dữ liệu nào đó. Thuật ngữ này là khá 
phổ biến trong khai phá dữ liệu, trí tuệ nhân tạo, xử lý ngôn ngữ và học máyvv. 
Tuy nhiên trong bài viết này đề cập đến một phạm vi hẹp là sử dụng kỹ thuật tiền 
xử lý dữ liệu để tối ưu các truy vấn dữ liệu. 
Như chúng ta đã biết hiện nay đa số các cơ sở dữ liệu dựa trên mô hình dữ 
liệu quan hệ bởi tính tiện lợi, toàn vẹn và nhất quán của dữ liệu. trong đó tất cả các 
thông tin của nó được lưu trữ trong các bảng có các cột và hàng và có mối quan hệ 
với nhau. Các truy vấn đến dữ liệu được thông qua ngôn ngữ truy vấn có cấu trúc 
SQL để trích xuất một phần hoặc toàn bộ dữ liệu trong các bảng này. Ngôn ngữ 
truy vấn có cấu trúc SQL chủ yếu dựa trên các phép toán của đại số quan hệ. Gồm 
Thông tin khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 209
các phép toán 1 ngôi như chọn, phép chiếu, phép gán, phép đổi tên và các phép 
toán 2 ngôi như tích decac, giao (Intersection), hợp (union), hiệu (minus), nối 
(join), chia (Division). Ngoài ra các hệ quản trị cơ sở dữ liệu hiện đại còn tích hợp 
thêm một số phép toán như các hàm tập hợp (Aggregate function), Gom nhóm các 
bộ dữ liệu (Grouping) và Phép kết mở rộng (Outer Join). Các thực thể trong cơ sở 
dữ liệu quan hệ được phân biệt với nhau thông qua giá trị của nó do vậy cơ sở dữ 
liệu quan hệ là cơ sở dữ liệu hướng giá trị (value oriented). Các bộ hay bản ghi của 
dữ liệu được phân biệt với nhau bởi các giá trị của nó do vậy việc lựa chọn trích 
xuất dữ liệu trong cơ sở dữ liệu hoàn toàn dựa vào giá trị của dữ liệu 
Việc truy vấn dựa trên giá trị của dữ liệu sẽ có những hạn chế nhất định về 
mặt tốc độ nhất là khi dữ liệu có kích thước lớn do phải thực hiện việc quét (scan) 
dữ liệu trong các bảng. Hiệu năng của một truy vấn được dựa trên chi phí (cost) mà 
truy vấn đó chiếm dụng tài nguyên hệ thống: 
cA(all)=cD(lưu trữ)+cM(Memory)+cN(Networking)+cL(lock)+cC(CPU) [7] 
Trong đó: 
cD: là chi phí đọc ghi đĩa lưu trữ (bộ nhớ ngoài) liên quan đến truy vấn 
cM: chi phí thao tác đến bộ nhớ trong liên quan đến truy vấn 
cN: chi phí về truyền thông mạng là số băng thông mạng mà truy vấn chiếm 
dụng 
cL: là chi phí liên quan đến tranh chấp khóa của truy vấn. Các cơ sở dữ liệu 
hiện đại đưa các khóa (lock) vào để quản lý việc truy cập đồng thời và các chỉ mục 
(index) để tối ưu truy vấn và việc thay đổi cũng như đọc dữ liệu vì vậy sẽ tiêu tốn 
tài nguyên của hệ thống liên quan đến khóa 
cC: phí phí liên quan đến tài nguyên chiếm dụng CPU của truy vấn. 
Hiệu năng của một hệ thống cơ sở dữ liệu là tổng chi phí của tất cả các yêu 
cầu truy vấn phát sinh trong một đơn vị thời gian : 
Trong đó N là số truy vấn trong một đơn vị thời gian, cj là chi phí của truy 
vấn j 
Như vậy mấu chốt của vấn đề là muốn nâng cao hiệu năng của hệ thống thì 
phải giảm chi phí tài nguyên của các truy vấn đến cơ sở dữ liệu. 
Ngoài việc chuẩn hóa thiết kế để tránh dư thừa dữ liệu và đảm bảo tính toàn 
vẹn, chuẩn hóa và tối ưu các câu lệnh sql để cải thiện hiệu năng truy vấn, các hệ 
quản trị cơ sở dữ liệu đưa việc đặt chỉ mục (index) để đảm bảo rằng thay vì việc tìm 
dữ liệu trong một danh sách không được sắp xếp thì chuyển việc tìm kiếm trong 
một danh sách đã được sắp xếp. Ngoài ra các hệ quản trị cơ sở dữ liệu hiện đại đưa 
Công nghệ thông tin 
C. Đ. Huy, N. N. An, “Nghiên cứu kỹ thuật tiền xử lý  dữ liệu có kích thước lớn.” 210 
ra các công nghệ về phân mảnh dữ liệu đó là quá trình phân chia dữ liệu thành 
nhiều đoạn và việc phân chia này cũng dựa trên các chỉ mục index [4]. 
Trên thực tế có nhiều dạng dữ liệu mà việc đặt chỉ mục là không hề dễ dàng 
ví dụ như những dữ liệu không có cấu trúc hoặc có cấu trúc phức tạp như dữ liệu 
không gian. Các chỉ mục chỉ hiệu quả khi chúng được tìm kiếm và so sánh dựa trên 
các toán tử (operator) và sẽ mất hoàn toàn hiệu quả khi sử dụng các hàm (function) 
dù nó là hàm của hệ quản trị cơ sở dữ liệu (system function), hàm do người dùng tự 
định nghĩa (user define function) hay hàm của các tool bổ sung thêm (add in 
function). Trong trường hợp này việc đặt chỉ mục và phân mảnh dựa trên các dữ 
liệu hiện có nhằm tối ưu tối ưu truy vấn là rất khó để thực hiện đòi hỏi chúng ta 
phải tạo ra các dữ liệu mới thì mới có thể đặt chỉ mục được [5],[6] 
Với cơ sở dữ liệu có kích thước lớn (hàng trăm triệu đến hàng trăm tỷ bản 
ghi và dung lượng có thể đạt đến nhiều TB dữ liệu) các truy vấn có thể lấy dữ liệu 
từ nhiều bảng thì việc truy vấn dữ liệu rất chậm và trong rất nhiều trường hợp là 
không khả thi, khả năng đáp ứng đồng thời nhiều truy vấn cùng lúc là rất khó và có 
thể gây nên hiện tượng dead lock (khóa chết) gián đoạn hệ thống và tệ hơn có thể 
gây nên việc hỏng và mất dữ liệu. Ngoài ra với những hệ thống có số lượng truy 
cập truy vấn dữ liệu đồng thời rất lớn như truy vấn thông tin địa chỉ trên bản đồ 
reverse geocode thì mặc dù khối lượng dữ liệu có thể không quá lớn nhưng tần suất 
quá lớn (hàng vạn thậm chí hàng chục triệu truy vấn đồng thời) cũng có thể gây nên 
quá tải hệ thống đòi hỏi chúng ta phải có giải pháp để nâng cao hiệu năng của các 
truy vấn đến cơ sở dữ liệu. 
Chúng tôi đề xuất giải pháp là dùng kỹ thuật tiền xử lý dữ liệu để nâng cao 
tính hiệu quả của các truy vấn cơ sở dữ liệu. Đó là những kỹ thuật tính toán, xử lý 
trước để tạo ra các định dạng dữ liệu mới nhằm cải thiện hiệu năng một cách rõ rệt 
cho việc truy vấn dữ liệu. Các kỹ thuật này đã được chúng tôi áp dụng và mang lại 
một hiệu quả rõ rệt cho những hệ thống có kích thước dữ liệu tương đối lớn hoặc có 
nhiều truy cập khai thác đồng thời. Chúng tôi phân loại tiền xử lý dữ liệu thành 2 
dạng là tạo ra các dữ liệu trên cũng một bảng truy vấn và tạo ra một số bảng dữ liệu 
tóm tắt hoàn toàn mới dựa trên việc rút gọn và tóm tắt các dữ liệu hiện có và đề 
xuất mô hình xử lý đối với hai dạng dữ liệu đó. 
2. MÔ HÌNH TIỀN XỬ LÝ DỮ LIỆU TRONG TỐI ƯU TRUY VẤN 
Tiền xử lý dữ liệu chính là bước tạo ra các dữ liệu trung gian với một định 
dạng và nội dung phù hợp mà dựa trên nó chúng ta có thể cải thiện một cách hiệu 
quả hiệu năng truy vấn đến cơ sở dữ liệu và thậm chí là hiệu năng trong quản lý bảo 
trì và lưu trữ dữ liệu. 
Dựa trên đặc tính và định dạng của dữ liệu và nội dung truy vấn chúng tôi 
đề xuất hai mô hình tiền xử lý dữ liệu. 
Thông tin khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 211
2.1. Tiền xử lý tạo ra các các dữ liệu trên cùng một bảng truy vấn. 
Kỹ thuật này được áp dụng đối với những truy vấn liên quan đến bảng có kích 
thước dữ liệu khá lớn hoặc tần suất khai thác nhiều lần mà các truy vấn đến nó là 
rất khó khăn trong việc thiết kế và sử dụng chỉ mục index, các điều kiện tìm kiếm 
sau lệnh where hoặc join là rất phức tạp đòi hỏi chi phí tính toán lớn cũng như chi 
phí về quét dữ liệu khi scan bảng đòi hỏi phải đọc dữ liệu rất nhiều từ toàn bộ bảng. 
Để giải quyết vấn đề này chúng ta sẽ tạo thêm một hoặc một số cột dữ liệu ở 
trên bảng mà giá trị của nó được tính toán dựa trên các cột hiện có và có định dạng 
phù hợp cho việc tạo chỉ mục cũng như hỗ trợ tốt việc phân mảnh dữ liệu nếu có 
(trong trường hợp số lượng bản ghi của bảng quá lớn). Thực chất của quá trình này 
là chúng ta đã phi chuẩn hóa về dữ liệu (de-normal) tạo ra các phụ thuộc hàm dựa 
trên các thuộc tính hiện có của bảng. Với những cột mới này chúng ta sẽ tạo chỉ 
mục tìm kiếm phù hợp và chỉnh sửa lại nội dung cú pháp các câu lệnh truy vấn để 
hướng đến việc sử dụng chỉ mục và phân đoạn bảng (với các bảng có dữ liệu lớn) 
Để thực hiện việc tiền xử lý trên cùng một bảng chúng ta sẽ thực hiện các bước 
như sau: 
Hình 1. sơ đồ các bước tiền xử lý dữ liệu trên cùng một bảng. 
Bước 1: Phân tích kích bản thực thi của truy vấn SQL hiện có, phân tích các 
tham số đầu vào Input của truy vấn và thứ tự các thao tác vật lý và logic mà bộ thực 
thi truy vấn của hệ quản trị cơ sở dữ liệu thực hiện để xử lý và trả kết quả truy vấn. 
Đặc biệt chú ý đến việc quét bảng và chỉ mục để tìm các tiến trình và thao tác có 
chi phí lớn nhất và có khả năng cải thiện được nhiều nhất. Chúng ta có thể sử dụng 
các công cụ hiện có của hệ quản trị cơ sở dữ liệu để thực hiện điều này. Ví dụ trong 
sql server chúng ta có thể sử dụng công cụ Estimated Execution Plan. 
Bước 2: Thêm các cột nhằm phục vụ cho việc tính toán tiền xử lý vào bảng liên 
quan đến truy vấn. Cột thêm vào nhằm tạo chỉ mục tìm kiếm và tối ưu hóa phép 
chọn. Tạo chỉ mục index từ các cột vừa tạo. Nếu dữ liệu của bảng quá lớn (>1GB) 
thì có thể phân mảnh bảng dữ liệu dựa trên chỉ mục vừa tạo để cải thiện hiệu suất 
quét bảng và truy vấn. 
Công nghệ thông tin 
C. Đ. Huy, N. N. An, “Nghiên cứu kỹ thuật tiền xử lý  dữ liệu có kích thước lớn.” 212 
Bước 3: Cập nhật các số liệu tiền xử lý vào các cột đã tạo mới một cách chính 
xác trong các tiến trình nền. 
Bước 4: Bổ sung các điều kiện lọc hướng tới chỉ mục tìm kiếm vào câu lệnh 
truy vấn SQL. điều kiện lọc liên quan đến chỉ mục phải được ưu tiên đầu tiên trong 
các điều kiện lọc sau lệnh where và lệnh join. Với bảng phân đoạn thì điều kiện lọc 
liên quan đến chỉ mục của phân đoạn bảng phải được nằm ở vị trí ưu tiên cao nhất 
trong thứ tự các điều kiện lọc này. Tránh tuyệt đối sử dụng hàm trong các điều kiện 
lọc mới bổ sung thêm. 
2.2. Tiền xử lý tóm tắt dữ liệu từ nhiều bảng 
Kỹ thuật này được áp dụng trên những truy vấn mà cần lấy dữ liệu từ nhiều 
bảng với khối lượng dữ liệu rất lớn có thể lên đến nhiều tỷ bản ghi vì vậy truy vấn 
cần phải có nhiều phép hợp union và phép nối join trên nhiều bảng, và do nó quét 
dữ liệu từ nhiều bảng rất lớn nên chiếm dụng I/O đĩa cứng, tài nguyên khóa và CPU 
nên nó sẽ không thể chạy được trong thời gian chấp nhận được cũng như có thể gây 
treo hệ thống, deadlock (khóa chết) thậm chí là hỏng hóc dữ liệu. Với những truy 
vấn kiểu này chúng tôi đề xuất là xây dựng những bảng dữ liệu trung gian lưu trữ 
các dữ liệu tổng hợp và tóm tắt để phục vụ cho việc tối ưu tốc độ của các truy vấn 
liên quan đến tổng hợp dữ liệu 
Các dữ liệu tóm tắt sẽ được thiết kế theo nguyên tắc sau:Dựa trên định dạng 
thông tin đầu ra của các truy vấn 
- Các dữ liệu tóm tắt có số lượng bản ghi ít hơn nhiều lần so với số lượng bản 
ghi của dữ liệu gốc và chứa đựng các nguyên tố của truy vấn đầu ra. 
- Dữ liệu tóm tắt được đánh chỉ mục index dựa trên các tham số đầu vào của 
truy vấn. 
- Bảng dữ liệu quá lớn (>2GB) có thể phân mảnh dựa trên thông tin trong chỉ 
mục index để tối ưu hóa tốc độ truy vấn và quản lý cũng như bảo trì hiệu 
quả dữ liệu. 
Để thực hiện việc tiền xử lý tóm tắt dữ liệu chúng ta sẽ thực hiện các bước 
như sau: 
Hình 2. sơ đồ các bước tiền xử lý tóm tắt dữ liệu từ nhiều bảng. 
Thông tin khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 213
Bước 1: Phân tích về tần suất các truy vấn và nội dung dữ liệu tổng hợp của 
các truy vấn, nghiên cứu về các định dạng dữ liệu đầu ra và xác định nguyên tố của 
các truy vấn đầu ra ví dụ chúng ta cần truy vấn tổng hợp của các cá nhân, phòng 
ban của một công ty trong một ngày, tháng, năm thì bản ghi nguyên tố chính là tổng 
hợp trong ngày của một cá nhân. Như vậy các thông tin tổng hợp của cá 
nhân,phòng ban trong một khoảng thời gian ngày, tháng có thể được lấy từ các 
thông tin tổng hợp của các cá nhân trong một số ngày nào đó. 
Bước 2: thiết kế các bảng dữ liệu tóm tắt chứa các bản ghi là các thông tin 
tóm tắt về dữ liệu phục vụ cho mục đích truy vấn mỗi hàng là một nguyên tố 
(atomic) của các dữ liệu báo cáo đầu ra, Xây dựng các chỉ mục tìm kiếm liên quan 
đến các điều kiện lọc của dữ liệu, phân mảnh dữ liệu nếu cần. Kích thước bảng này 
bé hơn rất nhiều lần so với dữ liệu gốc 
Bước 3: xây dựng các tiến trình nền Background process để tiền xử lý dữ 
liệu nhằm ghi nhận dữ liệu vào các bảng tóm tắt mà chúng ta xây dựng ở bước 3. 
Bước 4: Sửa đổi các câu lệnh truy vấn để truy cập dữ liệu trực tiếp vào các 
bảng tóm tắt thay vì tổng hợp từ nhiều bảng. lưu ý về sử dụng chỉ mục trong các 
câu lệnh tóm tắt này để nâng cao hiệu năng truy vấn. 
3. THỬ NGHIỆM VÀ ĐÁNH GIÁ 
Chúng ta sẽ thử nghiệm trên bài toán truy vấn thông tin địa lý mà cụ thể là 
địa chỉ trên nền bản đồ reverse geocoding trên dữ liệu không gian địa lý trong SQL 
Server 2014. Đây là một bài toán rất quan trọng và có ý nghĩa ứng dụng rất lớn và 
là một tính năng cơ bản của các công cụ bản đồ nổi tiếng Google map, Bing map 
hay việt bản đồvv. Bài toán này được ứng dụng nhiều trên các sản phẩm thương 
mại như Uber, Grabvv. Một số đặc điểm đáng chú ý trong bài toán này là chúng 
có số lượng truy vấn đồng thời rất lớn có thể đạt đến hàng triệu, hàng chục triệu từ 
những nguồn dữ liệu có cấu trúc phức tạp như dữ liệu không gian vốn là khá khó 
khăn trong việc đánh chỉ mục để tìm kiếm. 
3.1. Bài toán gốc 
Cơ sở dữ liệu mẫu chúng tôi dùng để thử nghiệm là cơ sở dữ liệu không 
gian có 2 lớp địa lý là lớp Địa danh hành chính (Tỉnh, huyện, xã) và lớp đường giao 
thông của Việt Nam và được tổ chức vào 2 bảng như sau: 
Bảng 1. Cấu trúc bảng dữ liệu gốc tblVillage. 
Tên cột Loại dữ liệu Loại cột Mô tả 
VillageID smallint Khóa chính Mã địa danh 
VillageName Nvarchar(30) Tên xã phường 
DistrictName Nvarchar(30) Tên quận, huyện 
ProvinceName Nvarchar(30) Tên tỉnh, thành phố 
Công nghệ thông tin 
C. Đ. Huy, N. N. An, “Nghiên cứu kỹ thuật tiền xử lý  dữ liệu có kích thước lớn.” 214 
Geom Geometry Dữ liệu không 
gian 
Dữ liệu này bao gồm lớp hành chính của gần 12.000 xã phường ở Việt Nam 
bao gồm cả dữ liệu không gian chứa đựng trong trường Geom 
Bảng 2. Cấu trúc bảng dữ liệu gốc tblRoad. 
Tên cột Loại dữ liệu Loại cột 
RoadID int Khóa chính Mã đường 
RoadName Nvarchar(80) Tên đường 
RoadType tinyint Loại đường:cao tốc, quốc lô, 
tỉnh lộ 
Geom geometry Dữ liệu không gian 
Dữ liệu đường giao thông mà chung tôi thử nghiệm gồm khoảng hơn 200.000 
đoạn đường giao thông ở Việt Nam. Nó bao gồm Gần như tất cả các đường giao 
thông có tên trên bản đồ google map đến quý 2 năm 2017 
Truy vấn mà chúng tôi minh họa ở đây là truy vấn truy vấn địa chỉ dựa trên tọa 
độ đầu vào reverse geocoding, tham số đầu vào là tọa độ GPS tại một điểm trên bản 
đồ số và đầu ra là địa chỉ của điểm đó (tên đường, xã phường, quận huyện, tỉnh 
thành phố). Đây là một truy vấn có tần suất rất lớn trên các dịch vụ bản đồ của 
goole map, bing map và việt bản đồ. 
Để lấy kết quả chúng ta cần thực hiện 2 truy vấn trên 2 bảng khác nhau là 
tblVilage và tblRoad 
Để lấy thông tin địa chỉ xã phường, quận huyện, tỉnh thành phố chúng ta sẽ 
thực hiện query sau: 
declare @Point geometry,@str nvarchar(60), @str nvarchar(60)@Lng 
decimal(9,6)=105.7993966,@Lat decimal(8,6)=21.0435112 
set @Point=geometry::Point(@Lng,@Lat,4326) 
select @str=VilageName+', '+DistrictName+', '+ProvinceName from tblVilage 
where Geom.STIntersects(@Point)=1 
select @str=RoadName+’, ’+@str from tblRoad where 
Geom.STDistance(@Point)<0.0009 order by Geom.STDistance(@Point) desc 
print @str 
Kết quả trả ra là: Phố Hoàng Sâm, Phường Nghĩa Đô, Quận Cầu Giấy, Hà Nội. 
3.2. Áp dụng kỹ thuật tiền xử lý cho bài toán 
Dữ liệu gốc trên bài toán này chúng ta sẽ rất khó khăn trong việc đánh chỉ mục 
và phân mảnh dữ liệu do nó là dữ liệu không gian với cấu trúc phức tạp. Khi phân 
tích kịch bản thực thi của truy vấn thì truy vấn trong bài toán gốc phải quét dữ liệu 
cuả toàn bộ bảng do đó nếu tần suất truy vấn lớn thì thời gian, tài nguyên hệ thống 
như I/O, CPU, Ram là khá lớn 
Thông tin khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 215
Bảng 3. các phép xấp xỉ các đối tượng không gian. 
Bây giờ chúng ta sẽ cải tiến hiệu năng truy vấn bằng cách xấp xỉ các đối 
tượng không gian ở đây là các đối tượng đa giác tượng trưng cho các đối tượng 
hành chính tỉnh, huyện xã và đối tượng đường gấp khúc tượng trưng cho các đoạn 
đường giao thông [9]. 
Đối với bài toán này chúng ta chọn xấp xỉ các đối tượng không gian theo đường 
bao hình chữ nhật của đối tượng không gian. Như vậy mỗi đối tượng hành chính 
hay đường giao thông được xấp xỉ với một hình chữ nhật (x1,y1/x2,y2) là hình bao 
của đối tượng 
Bước 1, Chúng ta chia bản đồ ra làm nhiều mảnh theo lưới ô vuông theo 
chiều vĩ độ thành m hàng và theo chiều kinh độ thành n cột và xác định các đối 
tượng này thuộc vị tri ô (x,y) nào trong lưới ô vuông này. Có thể có một số đối 
tượng sẽ nằm trong một số ô và vì vậy ta dùng các phép toán giao (intersec) để 
phân chia các đối tượng không gian nằm ở nhiều ô thành nhiều đối tượng riêng biệt 
nhau mà mỗi đối tượng chỉ nằm trọn ở một ô duy nhất. Như vậy mỗi đối tượng bây 
giờ được định vị ở một ô có ví trị (x,y) trong lưới ô vuông. Trong thử nghiệm này 
chúng ta sẽ chia bản đồ việt nam thành 75 hàng và 25 cột 
 Bước 2, chúng ta sẽ thêm vào bảng tblVilage 6 cột x1,y1,x2,y2 là xấp xỉ 
của đối tượng không gian và X và Y để xác định phường thuộc ô nào của lưới ô 
Công nghệ thông tin 
C. Đ. Huy, N. N. An, “Nghiên cứu kỹ thuật tiền xử lý  dữ liệu có kích thước lớn.” 216 
vuông, cột HaveStreet để chỉ thị đối tượng hành chính có đường giao thông hay 
không. 
Bảng 4. cấu trúc bảng dữ liệu tblVillage mới. 
Tên cột Loại dữ liệu Loại cột Mô tả 
VillageID smallint Khóa chính Mã địa danh 
VillageName Nvarchar(30) Tên xã phường 
DistrictName Nvarchar(30) Tên quận, huyện 
ProvinceName Nvarchar(30) Tên tỉnh, thành phố 
Geom Geometry Dữ liệu không 
gian 
X1 Decimal(9,6) Chỉ mục tìm kiếm 
Y1 Decimal(8,6) Chỉ mục tìm kiếm 
X2 Decimal(9,6) Chỉ mục tìm kiếm 
Y2 Decimal(8,6) Chỉ mục tìm kiếm 
X tinyint Chỉ mục phân 
đoạn 
Xác định phường thuộc 
dòng nào 
Y tinyint Chỉ mục Xác định phường thuộc cột 
nào 
HaveStreet bit Điều kiện lọc Xã phường có đường giao 
thông hay không 
Đối với bảng tblRoad cũng thêm tương tự 
Bảng 5. cấu trúc bảng dữ liệu tblRoad mới. 
Tên cột Loại dữ liệu Loại cột 
RoadID int Khóa chính Mã đường 
RoadName Nvarchar(80) Tên đường 
RoadType tinyint Loại đường:cao tốc, quốc lô, 
tỉnh lộ 
X1 Decimal(9,6) Chỉ mục tìm 
kiếm 
Y1 Decimal(8,6) Chỉ mục tìm 
kiếm 
X2 Decimal(9,6) Chỉ mục tìm 
kiếm 
Y2 Decimal(8,6) Chỉ mục tìm 
kiếm 
X tinyint Chỉ mục phân 
đoạn 
Xác định đường thuộc dòng 
nào 
Y tinyint Chỉ mục Xác định đường thuộc cột nào 
Thông tin khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 217
Tạo các chỉ mục trên các cột X1,Y1,X2,Y2 và đặc biệt là X,Y trên 2 bảng trên. 
Thực hiện việc phân đoạn bảng trên cột X ở cả 2 bảng trên. 
Bước 3, chúng ta sẽ cập nhật các giá trị vào các cột X1,Y1,X2,Y2,X ,Y và 
HaveStreet vào hai bảng trên 
Bước 4, Chúng ta tiến hành sửa đổi các truy vấn cho phù hợp với các chỉ 
mục tương tứng đã thêm vào, cột X ở đây dùng để phân đoạn dữ liệu nên điều kiên 
kiện lọc liên quan đến X sẽ được thêm vào và đứng đầu tiên sau lệnh where sau đó 
đến các điều kiện lọc liên quan đến Y và X1,Y1,X2,Y2. Nội dung truy vấn sẽ được 
sửa đổi như sau: 
decimal(9,6)=105.79939663410187,@Lat decimal(8,6)=21.043511243422103 
declare @Point geometry,@X tinyint,@Y tinyint,@str nvarchar(60) 
if @Lat<8.6 
 set @X=0 
else 
 set @X=5*@Lat-42 
if @Lng<102.4 
set @Y=0 
else 
 set @Y=5*@Lng-511 
set @Point=geometry::Point(@Lng,@Lat,4326) 
select @str= VilageName+', '+DistrictName+', 
'+ProvinceName,@HaveStreet=HaveStreet from tblVilageGis where X=@X and 
Y=@Y and @X between X1 and X2 and @Y between Y1 and Y2 and 
Geom.STIntersects(@Point)=1 
if @HaveStreet=1 
select @str=RoadName+’, ’+@str from tblRoad where X=@X and Y=@Y and 
@X between X1 and X2 and @Y between Y1 and Y2 and 
Geom.STDistance(@Point)<0.0009 order by Geom.STDistance(@Point) desc 
print @str 
Kết quả trả ra là: Phố Hoàng Sâm, Phường Nghĩa Đô, Quận Cầu Giấy, Hà Nội. 
Bảng 6. so sánh chi phí (cost) của query cũ và query mới và thời gian chạy truy 
vấn sau khi sử dụng kỹ thuật tiền xử lý. 
Chi phí Bài toán gốc Sử dụng kỹ thuật tiền xử 
lý 
So sánh 
Operator cost 15.79 0.0059 Giảm 2676 lần 
I/O cost 7.11 0.0047 Giảm 1512 lần 
CPU Cost 8.673 0.56 Giảm 53 lần 
Thời gian chạy 247.95 4.59 ms Giảm 54 lần 
Công nghệ thông tin 
C. Đ. Huy, N. N. An, “Nghiên cứu kỹ thuật tiền xử lý  dữ liệu có kích thước lớn.” 218 
Như vậy việc sử dụng kỹ thuật tiền xử lý đã mang lại kết quả cải thiện rất 
lớn về hiệu năng trong , và trong trường hợp số lượng truy vấn càng nhiều thì chỉ số 
chênh lệch về hiệu năng lại càng lớn bởi thao tác I/O có độ chênh lệch lớn về chi 
phí, các chi phí CPU, bộ nhớ và sự tranh chấp dữ liệu giảm xuống do các điều kiện 
lọc chỉ tìm kiếm trong một miền rất nhỏ của dữ liệu thay vì toàn bộ bảng. Và trong 
trường hợp độ lớn của dữ liệu tăng lên chúng ta có thể phân đoạn dữ liệu chi tiết 
hơn nhằm tối ưu việc quét cũng như lọc dữ liệu 
4. KẾT LUẬN 
Như vậy với dữ liệu kích thước lớn, tần suất truy vấn đồng thời cao và điều 
kiện tìm kiếm trong truy vấn phức tạp thì việc sử dụng kỹ thuật tiền xử lý sẽ mang 
lại hiệu quả rất lớn về hiệu năng. Bài báo đã nêu và phân tích về sự cần thiết phải 
sử dụng kỹ thuật tiền xử lý. Đề xuất mô hình các bước để thực hiện kỹ thuật tiền xử 
lý trên những dữ liệu có tần suất truy vấn lớn, cấu trúc phức tạp và có điều kiện lọc 
không sử dụng được chỉ mục dựa trên những dữ liệu sẵn có. Đồng thời cũng đề 
xuất mô hình tiền xử lý dữ liệu đối với những dữ liệu có kích thước từ lớn đến đặc 
biệt lớn, dữ liệu cần tổng hợp từ nhiều bảng. Kết quả thử nghiệm cho bài toán 
reverse geocode cho thấy tính khả thi của mô hình. 
TÀI LIỆU THAM KHẢO 
[1]. The Effect of Data Pre-Processing on Optimized Training of Artificial Neural 
Networks Nazri Mohd Nawi, Walid Hasen Atomi, M. Z. Rehman 
[2]. Query Optimization in Database Systems , MATTHIAS JARKE New York 
University, New York, New York 10006 
[3]. Preprocessing and Postprocessing in Linear Optimization, Xin Huang, 
McMaster University 2004 
[4]. Database Optimization: Increase query performance with indexes and statistics. 
Microsoft 
[5]. Search Space Preprocessing in Solving Complex Optimization Problems, 
Ruoqian Liu, Ankit Agrawal, Wei-keng Liao, Alok Choudhary EECS 
Department Northwestern University Evanston, IL USA 
[6]. Preprocessing Techniques, Nael El Shawwa Olesya Peshko Alberto Olvera 
Jonathan Li 
[7]. Estimating Query Costs, Brian Moran 2003. 
[8]. Performance Tip: Find Your Most Expensive Queries, overachiever 2012 
[9]. Spatial Partitioning and Index, Claudia Dolci, Dan Salvini, Micheal Schrattner, 
Robert Weibel 
Thông tin khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 11 - 2018 219
ABSTRACT 
DATA PRE PROCESSING TECHNIQUE 
FOR OPTIMIZATION QUERY ON BIG SIZE DATABASE 
Data optimization plays an important role to deploy every database 
aplication. Techniques For Improving Query Performance are Indexing, 
Partitioning but limited with big size data or concurency access with complex 
data. The article shows data pre processing technique to optimization query. 
This makes new data with suitable format to combine traditional technique to 
optimize query. The article introduces two models to pre process data. To 
evaluate the proposed method, we generated a test with 200.000 rows partial 
data set. Experiment results gave us speed of estimate 54 times compare old 
method. It’s very excellent. 
Keywords: Data optimization; Data pre processing; Data partition. 
Nhận bài ngày 28 tháng 6 năm 2018 
Hoàn thiện ngày 07 tháng 10 năm 2018 
Chấp nhận đăng ngày 05 tháng 11 năm 2018 
Địa chỉ: Viện Công nghệ thông tin/Viện KH-CN quân sự. 
 *Email: caodanghuy@gmail.com.