Nguyễn Khắc Huy: 04/07/12

Saturday, April 7, 2012

Video bài giảng toán,lý hóa...Hot nhất

Đây là các kênh lưu trữ bài giảng khá hay cho các bạn chuẩn bị thi đại học-cao đẳng 2012

http://www.youtube.com/user/theTsunamiO
http://www.youtube.com/user/theco5ucreative
http://www.youtube.com/user/thetcctacademy

Video bài giảng toán,lý hóa...Hot nhất

Index trong Sql Server Giúp Tăng Hiệu Năng Thực Hiện Như Thế Nào

Index là phương tiện rất mạnh để tăng hiệu năng thực hiện của câu lệnh. Bài post này sẽ cung cấp một ví dụ cho bạn thấy bên trong SQL Server sử dụng index để tăng hiệu năng như thế nào. Ở đây tôi dùng database AdventureWork là database mẫu đi kèm với SQL Server (bạn có thể dowload database này về và cài vào nếu chưa có sẵn).

Trước hết ta hãy dùng bảng Sale.Customer để tạo ra hai bảng mới là Sale.Customer_noIndex và Sale.Customer_Index, đồng thời tạo 1 index trên trường CustomerID cho bảng Sale.Customer_Index:

SELECT *
INTO Sales.Customer_NoIndex
FROM Sales.Customer
 
SELECT *
INTO Sales.Customer_Index
FROM Sales.Customer
GO
CREATE INDEX Idx_Customer_Index_CustomerID ON Sales.Customer_Index(CustomerID)

Nay ta có hai câu lệnh SELECT sau để truy vấn hai bảng:

-- #1
SELECT CustomerID, CustomerType
FROM Sales.Customer_NoIndex
WHERE CustomerID = 11001
-- #2
SELECT CustomerID, CustomerType
FROM Sales.Customer_Index
WHERE CustomerID = 11001

Hai câu lệnh này sẽ cho cùng kết quả, khác biệt duy nhất là câu lệnh thứ hai truy vấn bảng Sales.Customer_Index có index trên trường cần tìm (CustomerID). Ta sẽ xem hai câu lệnh trên được thực hiện như thế nào bằng cách nhìn vào kế hoạch thực thi (execution plan) của chúng. Khi bắt đầu thực hiện một câu lệnh, SQL Server lên một kế hoạch gồm các bước sẽ tiến hành để thực thi câu lệnh đó, gọi là kế hoạch thực thi.Trên hàng công cụ bạn hãy bấm vào nút “Include Actual Execution Plan”. Khi đó, mỗi lần bạn chạy câu lệnh hệ thống sẽ vừa thực hiện câu lệnh vừa đồng thời trả lại kế hoạch thực thi mà nó đã dùng để thực hiện câu lệnh đó.

Bạn hãy bôi đen câu lệnh thứ nhất và thực hiện nó, ở tab “Execution plan” hiện ra kế hoạch thực thi như thế này:

Như vậy ta thấy hệ thống sẽ thực thi câu lệnh bằng cách duyệt qua cả bảng (table scan) và tìm ra các bản ghi thỏa mãn yêu cầu tìm kiếm. Thao tác duyệt bảng có nghĩa là hệ thống cần phải đọc tuần tự từng bản ghi từ đầu đến cuối để tìm ra kết quả. Trong trường hợp này, nó phải đọc toàn bộ 19 185 bản ghi và tìm ra bản ghi có CustomerID=11011. Đây là một thao tác rất chậm vì nó phải xử lý tất cả các bản ghi trong bảng. Nên nhớ hệ thống sẽ không dừng lại khi nó tìm được bản ghi đầu tiên có CustomerID=11011, vì nó không biết liệu còn bản ghi nào khác có giá trị CustomerID tương tự hay không, cho nên để chắc chắn trả lại kết quả đầy đủ hệ thống vẫn phải tiếp tục đọc các bản ghi còn lại. Ta có thể nhận xét thấy chi phí của thao tác duyệt bảng tăng tuyến tính cùng với số lượng bản ghi trong bảng (độ phức tạp là O(n)).

Giờ ta hãy thực hiện câu lệnh thứ hai, lần này kế hoạch thực thi sẽ như sau:

Lần này ta không thấy thao tác table scan nữa, mà thay vào đó là index seek và RID lookup. Index seek là khi hệ thống có thể nhảy đến được node trên cây index chứa khóa thỏa mãn yêu cầu tìm kiếm. Index là một cấu trúc dữ liệu có dạng B-tree, nên nó rất thích hợp với các thao tác tìm kiếm theo kiểu key=value, chỉ cần vài phép so sánh là hệ thống định vị được node chứa khóa cần tìm. Node này chứa khóa (trường được index, ở đây là giá trị của CustomerID) và RID là ID của bản ghi tương ứng trong bảng (đây là giá trị nội bộ chỉ dùng bên trong hệ thống, ta không truy cập được giá trị này). Vì thế bước tiếp theo là dùng RID này để nhảy đến bản ghi tương ứng trong bảng (RID lookup) để lấy các trường dữ liệu cần thiết. Với index seek, độ phức tạp giảm xuống thành O(logn), một bước tiến vượt bậc so với table scan.

Ta có thể so sánh chi phí của hai câu lệnh trên bằng cách thực hiện cả hai cùng nhau:

Ta thấy câu lệnh thứ nhất chiếm tới 95% tổng chi phí, trong khi câu lệnh thứ hai chỉ chiếm có 5%. Nói cách khác, index trên trường CustomerID đã giúp cho câu lệnh thực hiện nhanh lên đến 19 lần. Index đã giúp cho lượng dữ liệu hệ thống cần xử lý để tìm ra kết quả giảm xuống đến mức tối thiểu, và điều đó đã tạo ra bước nhảy về tốc độ. Từ đây ta rút ra một bài học quan trọng: Các trường thường được dùng trong mệnh đề WHERE là các ứng cử viên đầu tiên cần được tạo index.

Các Loại JOIN Trong SQL Server

JOIN là phép kết nối dữ liệu từ nhiều bảng lại với nhau. Khi bạn cần truy vấn các cột dữ liệu từ nhiều bảng khác nhau để trả về trong cùng một tập kết quả, bạn cần dùng JOIN. Đây có lẽ là chức năng được dùng nhiều nhất khi lập trình T-SQL. Nó giúp tái hiện lại thông tin thế giới thực từ dữ liệu lưu trữ trong mô hình quan hệ. Ví dụ, bạn cần JOIN bảng BanHang với bảng SanPham thông qua SanPhamID để lấy về thông tin đầy đủ của một đơn hàng bao gồm cả tên sản phẩm, vì người dùng cần quan tâm đến sản phẩm đó là gì thay vì mã hiệu của nó.
SQL Server cung cấp các kiểu JOIN là INNER JOIN, OUTER JOIN, và CROSS JOIN.

INNER JOIN trả về kết quả là các bản ghi mà trường được join ở hai bảng khớp nhau, các bản ghi chỉ xuất hiện ở một trong hai bảng sẽ bị loại.

(hình lấy từ codinghorror.com)

OUTER JOIN nới lỏng hơn, lấy về các bản ghi có mặt trong cả hai bảng và cả các bản ghi chỉ xuất hiện ở một trong hai bảng. Kiểu JOIN này được chia làm hai loại:

FULL OUTER JOIN: kết quả gồm tất cả các bản ghi của cả hai bảng. Với các bản ghi chỉ xuất hiện trong một bảng thì các cột dữ liệu từ bảng kia được điền giá trị NULL.
HALF OUTER JOIN (LEFT hoặc RIGHT): nếu bảng A LEFT OUTER JOIN với bảng B thì kết quả gồm các bản ghi có trong bảng A, với các bản ghi không có mặt trong bảng B thì các cột từ B được điền NULL. Các bản ghi chỉ có trong B mà không có trong A sẽ không được trả về.

CROSS JOIN: mỗi bản ghi của bảng A được kết hợp với tất cả các bản ghi của bảng B, tạo thành một tích Đề-các giữa hai bảng (số bản ghi trả về bằng tích của số bản ghi trong hai bảng).

Ví dụ:

CREATE TABLE T1(ID1 INT, Ten VARCHAR(100) )
INSERT INTO T1
SELECT 1, 'Mozart' UNION ALL
SELECT 2, 'Beethoven' UNION ALL
SELECT 3, 'Chopin' 
 
CREATE TABLE T2(ID2 INT, Email VARCHAR(100) )
INSERT INTO T2
SELECT 2, 'beethoven@gmail.com' UNION ALL
SELECT 3, 'chopin@hotmail.com'  UNION ALL
SELECT 4, 'haydn@yahoo.com'  UNION ALL
SELECT 5, 'bach@yahoo.com'

INNER JOIN:

FULL OUTER JOIN:

LEFT OUTER JOIN:

CROSS JOIN:

Lưu ý là “A INNER JOIN B” có thể viết tắt thành “A JOIN B”, còn “A LEFT OUTER JOIN B” có thể viết “A LEFT JOIN B”.

Trong các loại JOIN trên, chỉ trừ HALF OUTER JOIN còn tất cả đều có tính đối xứng, nghĩa là “A JOIN B” tương tự như “B JOIN A”. Riêng HALF OUTER JOIN thì phân biệt thứ tự, ví dụ “A LEFT JOIN B” khác với “B LEFT JOIN A”. Tuy nhiên, “A LEFT JOIN B” tương đương với “B RIGHT JOIN A”, vì thế để tránh nhầm lẫn tôi luôn hay dùng LEFT JOIN thay cho RIGHT JOIN, và ngầm qui định trong đầu là A là bảng chính còn B là bảng join (bảng để kéo thêm dữ liệu vào).

Bạn cần đặc biệt chú ý khi dùng CROSS JOIN vì nó có thể tạo ra bùng nổ về số bản ghi. Ví dụ nếu hai bảng có số bản ghi tương ứng là 1 nghìn và 1 triệu thì kết quả sẽ là 1 tỷ bản ghi. Nói chung CROSS JOIN thường được dùng rất ít nhưng vẫn có lúc cần, ví dụ bảng kết quả điểm thi của sinh viên là CROSS JOIN của bảng sinh viên và bảng môn học (giả sử mỗi sinh viên cần lấy đủ tất cả các môn học).

Các kiểu viết JOIN

Cách viết JOIN như trên gọi là theo kiểu ANSI (ANSI style), cách viết kiểu cũ là đưa điều kiện join vào mệnh đề WHERE:

--INNER JOIN kiểu ANSI
SELECT *
FROM T1 JOIN T2 ON T1.ID = T2.ID
--INNER JOIN kiểu cũ
SELECT *
FROM T1, T2
WHERE T1.ID = T2.ID
 
-- LEFT OUTER JOIN kiểu ANSI
SELECT *
FROM T1 LEFT JOIN T2 ON T1.ID = T2.ID
--LEFT OUTER JOIN kiểu cũ
SELECT *
FROM T1, T2
WHERE T1.ID *= T2.ID

Cả hai kiểu viết đều cho cùng kết quả và cũng không khác nhau về hiệu năng thực hiện. Tuy vây bạn có thể thấy cách viết kiểu ANSI trong sáng hơn. Kiểu viết này gần với diễn đạt của ngôn ngữ tự nhiên hơn, nó tách bạch rõ ràng điều kiện join ra khỏi điều kiện lọc dữ liệu (dùng ở mệnh đề WHERE). Đây là kiểu viết bạn nên dùng. Microsoft trong 10 năm qua liên tục khuyến cáo dùng kiểu viết ANSI và nhắc nhở, các phiên bản sau có thể sẽ không hỗ trợ kiểu cũ. Và đến nay, bản SQL Server 2008 đã không còn hỗ trợ LEFT JOIN viết theo kiểu cũ (trừ khi bạn phải đặt lại COMPATIBILITY_LEVEL xuống mức thấp hơn).

Nguồn: Sqlviet.com

Các Cơ Chế Thực Thi Lệnh JOIN trong Sql server

Tiếp theo bài Các Loại JOIN Trong SQL Server, bài này giới thiệu về các cơ chế bên trong SQL Server sử dụng để xử lý các câu truy vấn JOIN. Về cơ bản khi thực hiện câu lệnh JOIN, SQL Server duyệt qua hai bảng tham gia vào, lấy ra từng cặp bản ghi để so sánh, rồi trả về tập kết quả nếu thỏa mãn điều kiện JOIN hoặc loại bỏ nếu không thỏa mãn. SQL Server cài đặt một vài thuật toán khác nhau, thích hợp với các tình huống khác nhau (như số lượng bản ghi cần so sánh nhiều hay ít, cột JOIN có index hay không…). Các thuật toán đó là Nested Loop Join, Merge Join, và Hash Join.

Nested Loop Join
Đây là thuật toán rất đơn giản và cũng rất hiệu quả đối với tập dữ liệu nhỏ, nó lấy mỗi bản ghi trong một bảng (gọi là inner table) và so sánh với từng bản ghi của bảng kia (gọi là outer table) để tìm ra bản ghi thỏa mãn. Thuật toán này có thể được viết ở dạng pseodo-code như sau:

for each row R1 in the outer table
   for each row R2 in the inner table
      if R1.join_column = R2.join_column
         return (R1, R2)

(pseodo-code được copy từ Craig Freedman’s Blog)
ví dụ 1:

USE AdventureWorkds
GO
SELECT a.SalesOrderDetailID, b.Name
FROM Sales.SalesOrderDetail a
JOIN Production.Product b
    ON a.ProductID = b.ProductID
WHERE a.SalesOrderID = 43659

Trong phương án thực thi ở hình trên, bạn thấy hai thao tác Clustered index seek, bảng ở thao tác trên luôn luôn là outer table, và bảng dưới luôn là inner table. Vì số bản ghi được trả về là nhỏ, bộ Optimizer đã chọn Nested Loop Join. Nói chung Nested Loop Join thích hợp khi outer table có số bản ghi nhỏ và inner table đã được sắp xếp theo trường được JOIN (ví dụ trường này có clustered index). Khi đó, việc quét bảng inner table (vòng lặp trong) trở thành index seek.

Khi xây dựng phương án thực thi, bộ Optimizer sẽ tự động chọn một bảng làm outer table và bảng kia làm inner table theo cách để đảm bảo chi phí là nhỏ nhất.

Nested Loop Join là thao tác join bạn mong đợi xuất hiện nhất trong phương án thực thi, vì nó chứng tỏ câu truy vấn được thực hiện hiệu quả và có chi phí thấp. Khi số bản ghi tăng lên hoặc bảng inner table không được sắp thứ tự (vì không có index hỗ trợ), bộ Optimizer sẽ xem xét đến Merge Join hoặc Hash Join, vì lúc đó các thuật toán này có thể sẽ hiệu quả hơn so với Nested Loop Join.

Cần phân biệt các thuật toán kể trên với các loại JOIN mà bạn dùng khi viết code như INNER JOIN, OUTER JOIN. Theo thuật ngữ của Microsoft, các loại JOIN đó được gọi là logical operator (các toán tử ở mức logic); còn các thuật toán trên gọi là physical operator (các toán tử ở mức vật lý). Khi viết code, bạn dùng các toán tử mức logic để diễn đạt yêu cầu, hệ thống sẽ xem xét và sử dụng một toán tử mức vật lý (một trong ba thuật toán) thích hợp để thực thi câu lệnh.

Merge Join
Kỹ thuật này đòi hỏi hai bảng phải cùng được sắp xếp theo thứ tự của trường JOIN. Nó đọc từng cặp bản ghi của mỗi bảng và so sánh với nhau. Nếu khớp thì gửi ra tập kết quả. Nếu không thì nó loại bản ghi có trường JOIN nhỏ hơn, đọc tới bản ghi tiếp theo của bảng tương ứng và tiếp tục quá trình. Với thuật toán này, hai bảng được đọc từ đầu và cùng tiến lên song song với nhau. Pseodo-code của thuật toán Merge Join như sau:

get first row R1 from table 1
get first row R2 from table 2
while not at the end of either table
begin
   if R1.join_column = R2.join_column
   begin
      return (R1, R2)
      get next row R2 from table 2
   end
   else if R1.join_column < R2.join_column
      get next row R1 from table 1
   else
      get next row R2 from table 2
end

(pseodo-code được copy từ Craig Freedman’s Blog )
Ví dụ 2: Cùng câu truy vấn như ở phần trước, nhưng bỏ qua mệnh đề WHERE

SELECT a.SalesOrderDetailID, b.Name
FROM Sales.SalesOrderDetail a
JOIN Production.Product b
    ON a.ProductID = b.ProductID
--WHERE a.SalesOrderID = 43659

Với câu lệnh trên thì Merge Join trở nên thích hợp, vì số bản ghi trả về là lớn và cả hai bảng đều đã được sắp xếp (nói chính xác ra là, đối với bảng SalesOrderDetail nó chỉ cần đọc index trên trường ProductID, và tất nhiên index đã sắp xếp sẵn).

Số phép so sánh, và do đó, chi phí của thuật toán này, tương đương với tổng của số bản ghi trong hai bảng. Do đó thuật toán này hoạt động hiệu quả hơn Nested Loop khi số bản ghi tăng cao. Trong nhiều trường hợp, thuật toán kết thúc khi nó mới chỉ quét xong bảng nhỏ hơn, vì bảng kia nếu có quét tiếp cũng không tìm được bản ghi nào thỏa mãn nữa. Khi đó số lần so sánh chỉ bằng hai lần số bản ghi của bảng nhỏ.

Nếu một trong hai bảng không được sắp sẵn thứ tự, bộ Optimizer có hai lựa chọn: (1) sắp xếp lại bảng theo thứ tự trường JOIN rồi áp dụng Merge Join hoặc (2) chuyển sang dùng Hash Join. Phương án nào rẻ hơn sẽ được chọn.

Hash Join
Thuật toán này phát huy hiệu quả nhất đối với lượng dữ liệu lớn và không được sắp xếp sẵn. Nó được thực hiện làm hai giai đoạn: xây dựng (build) và dò tìm (probe).

Ở bước xây dựng, nó quét qua một bảng (gọi là build table), và băm (hash) các bản ghi dựa vào trường JOIN, rồi xây dựng một bảng băm (hash table) trong bộ nhớ.

Đến bước dò tìm, nó đọc bảng thứ hai (gọi là probe table) và cũng băm các bản ghi dùng trường JOIN, rồi dùng giá trị băm đó để tìm trên bảng băm. Mỗi lần tìm được nó gửi cặp bản ghi tương ứng ra tập kết quả. Pseodo-code:

for each row R1 in the build table
begin
   calculate hash value on R1.join_column
   insert R1 into the appropriate hash bucket
end
for each row R2 in the probe table
begin
   calculate hash value on R2.join_column
   for each row R1 in the corresponding hash bucket
      if R1.join_column = R2.join_column
         return (R1, R2)
end

(pseodo-code được copy từ Craig Freedman’s Blog )
Ví dụ 3: giống như ví dụ 2 nhưng thêm một trường OrderQty vào phần SELECT

SELECT a.SalesOrderDetailID, a.OrderQty, b.Name
FROM Sales.SalesOrderDetail a
JOIN Production.Product b
    ON a.ProductID = b.ProductID
--WHERE a.SalesOrderID = 43659

Ở ví dụ này Hash Join đã được sử dụng, mặc dù số bản ghi được trả về giống như ở ví dụ 2. Lưu ý ở ví dụ 2, bảng SalesOrderDetail chỉ cần đọc index trên trường ProductID là đủ, và vì input cho việc join đã được sắp xêp nên Merge Join đã được dùng. Nhưng ở ví dụ 3, vì có thêm trường OrderQty nên chỉ đọc index trên trường ProductID là không đủ mà hệ thống phải đọc cả vào bảng nữa. Input cho thao tác join lúc này không còn được sắp xếp nữa và do đó, Hash Join trở nên thích hợp hơn.

Trong các tình huống như thế này Hash Join có ưu thế hơn Merge Join vì việc xây dựng bảng băm nhanh hơn sắp xếp lại bảng, hơn nữa nó chỉ cần áp dụng đối với một bảng.

Thông thường bộ Optimizer chọn bảng nhỏ để xây dựng bảng băm để không cần chiếm quá nhiều bộ nhớ. Tuy vậy so với Nested Loop Join và Merge Join thì thuật toán này đòi hỏi rất nhiều tài nguyên CPU và bộ nhớ. Khi Hash Join xuất hiện trong phương án thực thi, đó là chỉ dấu cho thấy lượng dữ liệu cần xử lý khá lớn (do không có mệnh đề WHERE, chủ ý hoặc do quên không đưa vào) và không có index hỗ trợ.

Trong các hệ thống OLTP, vốn đặc trưng bởi nhiều giao dịch được thực hiện nhanh, Hash Join cho thấy nhiều khả năng là câu lệnh chưa được thực hiện tối ưu. Còn trong môi trường data warehouse, các thao tác xử lý thường trên một lượng dữ liệu lớn, do đó Hash Join được sử dụng rất thường xuyên.

Lời kết
Trên đây giới thiệu các thuật toán SQL Server dùng để thực thi câu lệnh JOIN. Trên thực tế các thuật toán phức tạp hơn và còn có nhiều biến thể để bộ Optimizer tinh chỉnh trong từng tình huống cụ thể. Tuy nhiên mức sâu nhất mà bạn có thể nhìn vào hệ thống là biết thuật toán nào đã được sử dụng cho câu lệnh, do Microsoft che dấu toàn bộ các chi tiết bên dưới. Việc hiểu biết cơ chế hoạt động của các thuật toán giúp bạn có thêm một công cụ để tối ưu hóa câu lệnh. Ví dụ, với câu truy vấn ở phần Hash Join, khi quan sát kế hoạch thực thi và thấy Hash Join được sử dụng bạn hiểu rằng đây có thể là chỉ dấu câu lệnh chưa được thực hiện tối ưu. Bạn cố gắng tạo thay đổi để hệ thống chuyển sang chọn Merge Join (vì số bản ghi trả về lớn nên Nested Loop Join chắc chắn không thích hợp). Để dùng Merge Join thì đầu vào phải được sắp xếp. Vì thế bạn có thể sửa lại index trên trường ProductID để nó cover cả trường OrderQty. Và giờ câu lệnh đã được thực hiện bằng Merge Join và hiệu năng đã được cải thiện đáng kể:

--Tạo một bảng copy của Sales.SalesOrderDetail
SELECT *
INTO Sales.SalesOrderDetail_2
FROM Sales.SalesOrderDetail
GO
-- tạo các index trên bảng copy
CREATE CLUSTERED INDEX IX_SalesOrderDetail_SalesOrderID_SalesOrderDetailID_2
ON Sales.SalesOrderDetail_2 (
 SalesOrderID,
 SalesOrderDetailID)
GO
CREATE NONCLUSTERED INDEX IX_SalesOrderDetail_ProductID_2 
ON Sales.SalesOrderDetail_2(ProductID)
INCLUDE(OrderQty)
 
-- so sánh hai câu lệnh:
-- Query 1: câu lệnh trên bảng cũ
SELECT a.SalesOrderDetailID, a.OrderQty, b.Name
FROM Sales.SalesOrderDetail a
JOIN Production.Product b
 ON a.ProductID = b.ProductID
 
-- Query 2: câu lệnh trên bảng copy
SELECT a.SalesOrderDetailID, a.OrderQty, b.Name
FROM Sales.SalesOrderDetail_2 a
JOIN Production.Product b
 ON a.ProductID = b.ProductID

Nguồn: sqlviet.com