PIVOT和UNPIVOT兩個運算符可將表中的數據進行行列置換；本文介紹這兩個關系運算的語法、語義、實現原理，及與其他關系運算聯合使用時，SQL Server 2005所做的優化。
翻譯得很爛，并沒有嚴格按照原文翻譯，有些容易理解但卻又不好翻譯的地方，直接Copy原文沒有翻譯。建議還是直接看原文：
Conor Cunningham, César A. Galindo-Legaria, Goetz Graefe,
PIVOT and UNPIVOT: Optimization and Execution Strategies in an RDBMS,
http://www.vldb.org/conf/2004/IND1P2.PDF

1. 簡介

    Pivot用于將行轉換成列，UnPivot用于將列轉換成行；
    Pivot transforms a series of rows into a series of fewer rows with additional columns. Data in one source column is used to determine the new column for a row, and another source column is used as the data for that new column.
    Unpivot provides the inverse operation, removing a number of columns and creating additional rows that capture the column names and values from the wide form.

    以前要實現Pivot功能，需要在關系數據庫之外或者Query Processing之后對結果集進行處理;例如，Excel支持Pivoting，用戶可以對數據源執行查詢得到一個結果集，然后將該結果集導入到Excel，再對結果Excel進行Pivot；Access也支持Pivoting，但其是通過在Query Processing之后通過游標來實現的；它們的實現都不是很高效，沒有將Pivot和UnPivot做為數據庫關系操作.

    現有的數據建模技術中，都要求將表之間的關系和表內的屬性(Attribute)進行持久存儲。將列按照自然特點進行強定義(columns be strongly defined contrasts with the nature)，可以很方便地進行插入和刪除行。PIVOT和UnPivot可以在編譯和執行時進行行列轉換；當列集不能預先確定，可以使用屬性表(包含ID、PropertyName、PropertyName的表)，用多行來存儲一組屬性值；通常，如果增加屬性時不想修改表結構(schema)定義，或需要避免關系數據庫的實現限制(例如表中列數量的限制、或storage overhead associated with many empty columns in a row)時，可以采用這種設計；這種設計引發的問題是如果更好地使用和查詢表，編寫和維護對屬性表的查詢相對較困難，而且復雜的操作可能會導致DB不能選擇最優的執行計劃；通常，操作屬性表中數據的應用程序，按Wide(Pivoted)格式處理時會比較費力。

    關系數據庫能高效地執行關系運算，在T-SQL中使用Pivot/Unpivot操作符，SQL Server可以很好地進行優化.

2. Imtroducing Pivot And Unpivot

2.1 Pivot And Unpivot in SQL

    使用SQL標準語法，也能實現Pivoting功能，但操作麻煩且性能很差；一種方法是在結果列中使用標量子查詢(use scalar subqueries in the projection list)；例如下面的示例sql，使用標量子查詢來創建需要的列:

SELECT

    Year

    ,(SELECT Sales FROM SalesTable AS T2 WHERE T2.Month='Jan' AND T2.Year=T1.Year) AS 'Jan'

    ,(SELECT Sales FROM SalesTable AS T2 WHERE T2.Month='Feb' AND T2.Year=T1.Year) AS 'Feb'

    ,(SELECT Sales FROM SalesTable AS T2 WHERE T2.Month='Mar' AND T2.Year=T1.Year) AS 'Mar'

FROM SalesTable AS T1

GROUP By Year;

    不幸的是，這種處理方式有很大的局限性，并不能充分發揮Pivoting的優勢：必須為每個要轉換的列定義相似語句的子查詢，列數越多越麻煩，DBMS只會當子查詢處理，不能很好的進行優化；而且可讀性差，很難根據語法來推斷查詢想要干嘛.
    因此，Pivot橫空出世了。如下例中的SQL所示，這樣的語法閱讀、書寫和維護都很方便，老少咸宜啊。。。

SELECT * FROM 

    (SalesTable Pivot (Sales FOR Month IN ('Jan','Feb','Mar'));

    上面的查詢中，Pivot對SalesTable進行操作；Sales列中的值被轉置到pivoted column中，Month列中的值限制該如何轉置(定義了映射關系)；IN列表中的值來自于Month列，并作為pivoted column的列名；SalesTable中其余的沒有列出來的列，會被隱式地進行分組，每組對應Pivot結果集中的一行。

    至于Unpivot，其語法與Pivot相似，但執行與Pivot相反的操作，將IN列表中的列轉換成行。

SELECT * FROM 

    (SalesReport Unpivot (Sales FOR Month IN ('Jan','Feb','Mar'));

2.2 Pivot AND Unpivot Semantics

    使用Pivot和Unpivot時，還需要注意數據沖突(例如兩個值映射到同一個位置)和缺值的情況。
    出現數據沖突時，有以下幾種處理方式:(1).報錯；(2).使用聚集函數(sum、avg等),如下例所示；(3).數據在進行Pivot處理之前先除掉重復值；(4).引入嵌套結果集。

SELECT * FROM 

    (SalesTable Pivot (SUM(Sales) FOR Month IN ('Jan','Feb','Mar'));

3.代數優化

PIVOT的定義：

UNPIVOT的定義：

3.1 Projection(投影)和Filters(選擇)

    (1) 投影+Pivot：如果一個查詢對Pivot生成的列進行投影操作，則查詢將被優化成Pivot時就不處理這些列，從而避免不必要的計算。
 

    (2) 選擇+Pivot：Select對Pivot的輸出結果進行過濾時，并不會在Pivot之前就對行進行過濾；Pivot會為輸入源中的每組數據生成一行，即使輸入源中的數據于pivot生成的轉置列不匹配。如果提前進行過濾，有些情況下可能產生錯誤的結果；當且僅當分組列與Pivot生成的裝置列組合后正好包含鍵(候選碼)，且折疊函數滿足恒等性(the collapsing function is the identity)，這種提前過濾得到的最終結果才是正確的，且可以有效地應用索引(如果有的話)。如下圖所示:

    (3) 投影+Unpivot：Projections over UNPIVOT are straightforward. Projections limiting grouping columns can be safely applied below the UNPIVOT.

    (4) 選擇+Unpivot：A filter on the columns introduced by UNPIVOT enables a whole column to be removed from the input to UNPIVOT. 這里不存在上面(2)總存在的問題。

3.2 PIVOT and Property Tables

    屬性表包含兩列：屬性名稱和屬性值；我們可以用這種存儲方式來代替稀疏矩陣。 我們可以用PIVOT來將屬性表轉換成包含所有列的虛擬表(稀疏矩陣，缺值時用NULL進行填充)，其是通過將主表與從表進行Left Outer Join(LOJ)來實現的。
    屬性表的設計增加了使用復雜性；通常情況下，在主表中用于分組的列(grouping columns)和屬性表中的屬性名、屬性值上創建索引，可以提高查詢效率；
    (1) 投影：對Pivot生成的結果集執行投影，投影操作會提前到LOJ之前；如果投影會去掉轉置生成的列，則在Pivot時就不會轉置這些列；特別地，當對Pivot結果集執行去掉所有生成的轉置列的投影操作，則數據庫可以不用查找屬性表，直接優化掉Left Outer Join，如下圖所示：
 
    (2) 選擇：執行Pivot時，屬性表中的數據可以根據IN列表中的值來進行提前(在LOJ之前)過濾，執行過程如下圖所示：
 
    如果對選擇條件是根據生成的轉置列進行過濾，則優化成如下如下：
 
    顯然這樣優化后，增加了一次對屬性表的查詢，當且僅當在屬性表上建立了合適的索引后，此優化才是合理的。
 

3.3 PIVOT as GROUP BY

    可以用Group By來實現Pivot：

MIN(CASE Month WHEN 'Jan' THEN Sales ELSE

NULL END) AS 'Jan',

MIN(CASE Month WHEN 'Feb' THEN Sales ELSE

NULL END) AS 'Feb',

MIN(CASE Month WHEN 'Mar' THEN Sales ELSE

NULL END) AS 'Mar'

     在Group By中使用了多個聚合運算，DBMS的優化器將將很難檢查和理解；如果使用Pivot，邏輯相對集中，不是分散在那些聚合函數中，it is easier for rule-based optimizers to target with special-purpose transformation logic.

    將PIVOT當作Group By處理(Mapping PIVOT to GROUP BY)需要滿足一個假設：增加NULL值時，聚合函數的結果不變(the collapsing (aggregate) function be invariant to additional NULLs)。也就是說，聚合函數F需要滿足F(S)=F(S U {Null}) (S是輸入值，U表示Union)；SUM()、MAX()等聚合函數滿足次條件，但Count(*)不滿足!

    既然PIVOT是一種特殊的GROUP BY，RDBMS可以很容易地支持PIVOT功能，而不用專門在查詢處理器中每個地方為其寫一套新的邏輯。在編譯查詢(query compilation)時，盡可能早地將PIVOT轉換成GROUP By(例如，在查詢優化或啟發式重寫的最開始[at or near the start of query optimization or heuristic rewrite])，數據庫為實現PIVOT功能所需要做的改動最小：不需要增加新的執行操作符(execution operator)，little new optimization or costing logic is needed。

    將PIVOT看作GROUP BY，則不需要做重大更改，就可以將現有的GROUP BY優化邏輯應用到PIVOT。These benefits include:
(1). Removal of duplicate or grouping columns by other grouping columns, which  reduces overall row width;
(2). Filters and semi-joins restricting complete groups can be performed below the GROUP BY;
(3). Local/Global techniques for pushing grouping optimizations below joins and other operations;
(4). Query logic to perform groupings using parallel threads of execution.

3.4 UNPIVOT as Apply

    從本節開始UNPIVOT的定義中，我們可以看到，PIVOT是通過APPLY來實現的。Apply can be reordered easily with other join operators, and it has well-defined interactions with filters, projections, and other query operations. It is also possible to perform these operations in parallel by segmenting the input rows into different groups。DBMS已經對Apply進行了很多優化，這些優化對UNPIVOT同樣適用。

3.5 減少JOIN結果集的基數(Join Cardinality Reduction)

    如果聯合使用PIVOT和UNPIVOT并執行相反的操作(If PIVOT and UNPIVOT are inverses)，查詢優化器(query optimizer)可以在查詢樹(query tree)中引入PIVOT和UNPIVOT，從而減少高代價運算符所處理的關系集的基數(reduce cardinality in portions of a query tree around expensive operations, such as joins.)。如果使用PIVOT能無損地減少輸入源的基數，則JOIN(或者其他的高代價運算符)可以執行更少地次數；UNPIVOT也同樣。基于代價的查詢優化器(Cost-based optimizers)可以在查詢評估(query evaluation)時使用此技術。如下圖所示：

4. 執行策略(Execution Strategies)

    用GROUP BY來表示PIVOT，提供了一種新的方式來重用現有的操作符。上面的3.3節中，演示了PIVOT可以通過GROUP BY來實現。PIVOT中可以使用hash和stream聚集函數(hash and stream aggregation)，且保留了聚集函數原有的行為特性；只要每組中的所有記錄是在一個線程中被處理，使用這種PIVOT實現策略 就可以并行地執行查詢(Parallel query execution can also be supported using these execution strategies as long as the members of each group are processed in the same thread.)。PIVOT的實現過程中，使用了大量的聚集函數(PIVOT does use a relatively large number of identical aggregates with almost identical scalar logic.)。PIVOT的一種新的執行策略是：group the computation of these aggregates together，有如下兩種實現方式：(1). 將這組聚合函數當過向量運算來進行處理(treating the set of aggregates as a vector computation);
(2). 重寫現有的聚集函數：rewriting each individual aggregate computation into a dispatch table (as each column will be looking for a single and likely unique scalar for each input row).

    也可以通過行轉列的迭代器(a specialpurpose iterator transposing rows into column)來實現PIVOT。當遍歷已經排序(根據要分組的列[Grouping columns]和轉置列[pivot column])的輸入流時(Consuming a sorted stream)，當前組中的下一行中的值就是下一列的值；如果輸入源中，轉置列沒有相應行，就用空值代替；與grouping運算相似，這種實現方式中，也可以實現不同分組并行計算。

    如前面所述，可以通過相關的嵌套循環連接(nested loops join, apply)來實現UNPIVOT，Apply中的每個步驟可以并行處理(Each invocation of the Apply can be performed in parallel)。也可以通過列轉行的迭代器(a special purpose execution iterator that consumes one row and returns a number of rows in unpivoted form.)來實現UNPIVOT，這種實現方式中，輸入源中的每行能獨立地被處理，因此要實現并行運算也很簡單。

5. Experimentation

    SQL Server 2005中已經實現了PIVOT和UNPIVOT。SQL Server 2005查詢優化器的體系結構是基于Cascades framework的，該framework允許定義新的關系運算符和為這些運算符定義新的優化規則。這些優化規則是根據上面所描述的PIVOT和UNPIVOT的屬性(property)得出的。

    這節中，通過幾個示例來展示系統的性能。使用TPCH數據庫，1GB規模；測試機為2GHz雙處理器，1GB內存。每次執行前清理數據緩存，所以展示結果數據都是基于cold cache的。測試時禁用了并行執行，這不會對測試結果產生重大影響(Parallel execution is disabled in the results we present, since it does not qualitatively affect our results)。

5.1 PIVOT vs. SQL子查詢

    比較Pivot與2.1中的子查詢兩種寫法，實現如下功能：統計Orders表中的銷售數據，每年一條記錄，每月占一列。

SELECT * FROM

(SELECT

YEAR(O_ORDERDATE),

MONTH(O_ORDERDATE),

O_TOTALPRICE

FROM ORDERS) ORD(YEAR, MONTH, PRICE)

PIVOT (SUM(PRICE)

FOR MONTH IN (1,2,3,4,5,6,7,8,9,10,11,12)) T

     下圖展示了兩種寫法的執行時間。分別改變兩種寫法中的月數，3個月、6個月、12個月；子查詢的性能差異主要是由于子查詢中的重復計算，而Pivot的性能差異很小，因為每個轉置列是被獨立計算的(as each pivoted column is computed separately)。子查詢的寫法中，不能對每列進行獨立計算。

    可以使用索引來優化子查詢的性能；在上面的例子中，在year、month、price列上建立索引，可以讓子查詢的性能優化到接近Pivot性能的程度(Fast lookup of the value from the dimensions columns (e.g. and index on year, month, price in the case above) would make performance comparable to the PIVOT form.)。但是, 這樣會給應用程序開發人員帶來冗余和重復的工作(it remains verbose and repetitive to the application writer)。

5.2. 訪問屬性表(Property table access)

    前面提到了使用Pivot來支持屬性表。數據按照稀疏格式存儲在屬性表，應用程序開發人員可以用Pivot來使其展現成wide rows。在這個實驗中，我們將TPCH CUSTOMER表中的數據按照屬性表的方式來進行存儲，屬性表的Schema如下：

CUSTPROPERTY(CP_CUSTKEY, CP_NAME, CP_VALUE);

    列 (CP_CUSTKEY, CP_NAME)組成屬性表的復合主鍵；記錄customer的屬性時，就向該表中增加一條記錄；我們在CP_NAME、CP_VALUE、CP_CUSTKEY上創建索引，以高效地查詢屬性值。

    現在創建一個視圖按縱表格式來展示屬性表中的數據。由于要保留沒有定義屬性的customer，所以視圖中使用了outer join。假定我們只關心‘A’到‘E’ 5個屬性：

CREATE VIEW EXTCUSTOMER AS

SELECT *

FROM (

    SELECT *

    FROM CUSTOMER 

    LEFT JOIN CUSTPROPERTY

        ON C_CUSTKEY = CP_CUSTKEY

) CUSTNARROW

PIVOT 

(

    MIN(CP_VALUE) FOR CP_NAME IN ('A','B','C','D','E')

) CUSTPIVOTED

    應用程序如果想查找具有特定屬性的customer，則可以直接查詢該視圖，例如：

SELECT * FROM EXTCUSTOMER

    WHERE A IS NOT NULL

    下圖展示了視圖的性能，其中比較了三種實現方式：
(1). 將所有信息放在縱表(Wide Table)中，為'A'——'E' 5個屬性分別創建5列，并在每列上分別創建索引；
(2). 使用屬性表，并為屬性表創建視圖，然后在視圖上執行操作，例如選擇(filtering)；
(3). 使用屬性表，直接對在屬性表上進行Pivot操作；

    為了改變謂詞的選擇度(To change the selectivity of predicates)，我們對屬性值進行了分類。10個customer定義(縱表格式中不是NULL值)了屬性'A'，定了屬性'B'到'E'的customer數量分別為100、1000、1000、10000。在這個實驗中，customer的記錄數在15萬～60萬之間。屬性'A'和'B'的選擇度很低，下圖展示了其查詢計劃。先通過索引查找，根據CUSTPROPERTY表的非聚集索引查詢到具有此屬性的customer；然后，通過CUSTOMER表上的聚集索引進行索引查找，取得表中所有的列；接著再功過索引查找來為這些customer取得剩余的屬性值；最后對數據進行組合，使用分組和聚合(stream aggregation)來完成pivot。

    相比之下，屬性表比CUSTOMER表小；當所有的數據都已被加載，使用屬性表與縱表("wide" table)的性能差異主要在于Pivot的執行代價。當查詢中有謂詞存在時，我們的轉換規則可以生成高效的執行計劃，使用索引來快速地定位需要的行，使Pivot的性能接近與使用縱表。

    另外還需要指出的是，索引帶來有的優勢也有一定的限制。當在數據建模中直接使用縱表，則可以創建并使用多列的組合索引；但屬性表卻無法提供這種訪問方式，所以其預期行為與在每列上分別建立索引的效果比較接近。

6. 擴展(Extensions)

    本文展示了PIVOT和UNPIVOT處理單列的情況，我們也可以很容易地擴展它們來處理任意多列的情況：Pivot可以將每列轉換到獨立的列集中(Each value column could be transposed into independent sets of columns in PIVOT)；同樣地，UNPIVOT可以同時拆分不同的分組(UNPIVOT can collapse different groups at the same time)。各組使用不同聚集函數，且不同的聚集函數可以應用到同一列上。或者根據具體需要，創建復雜數據類型來存儲多值。這些擴展都不會影響上面描述的優化和實現技術。

    擴展折疊函數(collapsing function)也可以增加PIVOT和UNPIVOT的功能。折疊函數就是單列聚集函數(例如SUM()、MIN()等)。可以使用RDBMS中的任何聚集函數(包括用戶自定義函數和順序敏感的聚集函數)，這些函數都不會影響上面描述的行列轉換方式。即使引入其他的聚集函數(例如允許輸入多列或輸出多列)，也可以通過簡單的擴展來適配PIVOT和UNPIVOT的語法。在這種上下文中，也可以考慮不使用聚集函數(it is possible to consider non-aggregate functions in this context)，當出現數據沖突時拋出異常，或者使用嵌套關系來處理數據沖突(handle data collisions by storing data from multiple rows as a nested relation)，或者some other format that UNPIVOT can reassemble into multiple rows without losing data。這些擴展使PIVOT和UNPIVOT具有很大的擴展性。

    PIVOT and UNPIVOT are related to OLAP structures such as data cubes。但是，OLAP操作并不是總能很好地適合SQL language。如果SQL可以訪問多維結構，PIVOT和UNPIVOT就可以將CUBE當作關系集合來處理(例如二維的行列)(If a multidimensional structure is accessible through SQL, PIVOT and UNPIVOT could work on a portion of a cube visible as a relation)。

7. Related Work

    PIVOT并不是一個新的概念，[4]描述了關于分組的一些擴展，包括“cross-tab”查詢，里面的討論對與PIVOT沒有多少幫助，并且沒有討論如何有效地實現、如果與其他運算符聯合使用。

    SchemaSQL [5] 實現了轉置運算符。其實現是在RDBMS之外，因此沒有關于查詢優化的討論。[6]通過unfold和fold運算符來分別實現了pivoting和unpivoting功能。這些工作都沒有嘗試將行列轉置功能深入到RDBMS內部去實現。

    [8] describes a system to expose spreadsheet-like functionality into a RDBMS, 包括這種訪問方式中如何優化查詢。This model exposes behavior closer to OLAP than traditional flat relations, though some predicate pushing would be related in these two models.

    [8]也描述了一個N維數組數據模型，其中數組中每個單元(cell)described through a coordinate system using names。雖讓實現了功能，但范例與傳統的SQL運算符不同，很難理解。我們的表示法使用SQL語言實現數據旋轉(data rotation)，是一種更加自然的表示法。

    [8]和[4]都描述了一個關系表是從二維的角度來看CUBE，可以表現cross-tabulation數據。但是，只有[4]中討論了如何在cross-tabulated和flat (narrow) form兩種格式之間轉換數據，并且[4]只提到了Microsoft Access具有此功能。

    最后，我們先前的工作[2]使用unpivot運算符的設計來實現一個特殊功能。

8. Conclusion

    我們介紹了兩個新的可以在RDBMS內部使用的數據操作運算符：Pivot和Unpivot。These improve many existing user scenarios and enable several new ones。此外，這篇文章概況地描述了他們的基本語法、語義，及如何在現有的RDBMS(based on algebraic, cost-based optimization and algebraic data flow execution)中實現它們。Pivot is an extension of Group By with unique restrictions and optimization opportunities，這使得Pivot在grouping的基礎上很容易實現。最后，我們使用Pivot和Unpivot展示了幾個有用的代數轉換公理。

9. References

[1] C. A. Galindo-Legaria, M. M. Joshi. Orthogonal Optimization of Subqueries and Aggregation, ACM SIGMOD 2001, May 21-24, 2001, Santa Barbara, California, USA, pages 571-581.
[2] G. Graefe, U. Fayyad, and S. Chaudhuri. On the Efficient Gathering of Sufficient Statistics for Classification from Large SQL Databases, Proceedings of The Fourth International Conference on Knowledge Discovery and Data Mining, 1998, pages 204-208.
[3] G. Graefe. The Cascades Framework for Query Optimization. Data Engineering Bulletin 18 (3) 1995, pages 19-29.
[4] J. Gray, A. Bosworth, A. Layman, H. Pirahesh. Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals, Data Mining and Knowledge Discovery, vol. 1, no. 1, 1997.
[5] L. V. S. Lakshmanan, F. Sadri, and S. N. Subramanian. On Efficiently Implementing SchemaSQL on a SQL Database System. In Proceedings of 25th International Conference on Very Large Data Bases, September 7-10, 1999, Edinburgh, Scotland, pages 471-482.
[6] R. Agrawal, A. Somani, Y. Xu. Storage and Querying of ECommerce Data, In Proceedings of 27th International Conference on Very Large Data Bases, September 11-14, 2001, Roma, Italy, pages 149-158.
[7] M. Jaedicke, B. Mitshcang. On Parallel Processing of Aggregate and Scalar Functions in Object-Relational DBMS. 1998 Proceedings of the ACM SIGMOD International Conference on Management of Data, Seattle, WA, pages 379-389.
[8] A. Witkowski, S. Bellamkonda, T. Bozkaya, G. Dorman, N. Folkert, A. Gupta, L. Shen, S. Subramanian. Spreadsheets in RDBMS for OLAP. 2003 Proceedings of the ACM SIGMOD International Conference on Management of Data, San Diego,CA, pages 52-63.1009

happyhippy補充:

(1). 關于基數(Cardinality)的定義：
Cardinality represents the number of rows in a row set. Here, the row set can be a base table, a view, or the result of a join or GROUP BY operator.
Base cardinality is the number of rows in a base table. The base cardinality can be captured by analyzing the table. If table statistics are not available, then the estimator uses the number of extents occupied by the table to estimate the base cardinality.
Effective cardinality is the number of rows that are selected from a base table. The effective cardinality depends on the predicates specified on different columns of a base table, with each predicate acting as a successive filter on the rows of the base table. The effective cardinality is computed as the product of the base cardinality and combined selectivity of all predicates specified on a table. When there is no predicate on a table, its effective cardinality equals its base cardinality.
Join cardinality is the number of rows produced when two row sets are joined together. A join is a Cartesian product of two row sets, with the join predicate applied as a filter to the result. Therefore, the join cardinality is the product of the cardinalities of two row sets, multiplied by the selectivity of the join predicate.
Distinct cardinality is the number of distinct values in a column of a row set. The distinct cardinality of a row set is based on the data in the column. For example, in a row set of 100 rows, if distinct column values are found in 20 rows, then the distinct cardinality is 20.
Group cardinality is the number of rows produced from a row set after the GROUP BY operator is applied. The effect of the GROUP BY operator is to decrease the number of rows in a row set. The group cardinality depends on the distinct cardinality of each of the grouping columns and on the number of rows in the row set. For an illustration of group cardinality.