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

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.