In diesem Blogbeitrag möchte ich näher erläutern, wie eine Slowly Changing Dimension (kurz SCD) in SSIS mithilfe des Algorithmus der binären Suche (engl. binary search) an die Fakten gebunden werden kann.
Betrachten wir als Beispiel eine Kundendimension bei der es sich um eine SCD vom Typ 2 handelt. Als Business Key für einen Kunden dienen die Spalten NAME, VORNAME und GEBURTSDATUM. Die Spalten STADT, EINKOMMEN, ANZAHL_KINDER und EMAIL sind über die Zeit veränderliche Attribute. Die Spalten SCD2_START_DATE_ID und SCD2_END_DATE_ID geben das Gültigkeitsintervall eines Datensatzes an. Für die Faktentabelle wird die Dimensionsspalte Surrogate_ID als Schlüsselspalte nachgeschlagen.
In unserem Beispiel haben sich beim Kunden Haley Allen (geb. am 07.12.1916) die Attribute EINKOMMEN, ANZAHL_KINDER am 20.08.2014 geändert. Aus diesem Grund wurde in der Dimensionstabelle ein neuer Eintrag für diesen Kunden angelegt. Dieser Kunde bekommt ein neues Gültigkeitsintervall und eine neue Surrogate_ID (18496).
Die Staging-Tabelle, die als Quelle für die Fakten fungiert, beinhaltet den Business Key eines Kunden, den Verkaufstag sowie 2 Kennzahlen (Verkaufsmenge und -betrag).
In Abhängigkeit davon, wann der Verkauf stattgefunden hat, soll die entsprechende Surrogate_ID des Kunden aus der Kundendimension an die Fakten gebunden werden. Für den Kunden Haley Allen sollen folgende Einträge in die Faktentabelle geladen werden:
Um dieses Ziel zu erreichen, betrachten wir nun Schritt für Schritt, wie der zu implementierende Algorithmus grundsätzlich funktioniert. Zunächst wird eine nach Business Key sortierte Liste der Kunden aus der Dimension DimCustomer erzeugt:
ListCustomers(NAME, VORNAME, GEBURTSDATUM, SCD_START_DATE_ID, SURROGATE_ID).
Dabei kann anhand von Business Key und SCD_START_DATE_ID genau bestimmen, ab wann der Surrogate_ID gilt. Um es einfach zu halten, nehmen wir an, dass die Liste nur aus 8 Elementen besteht.
ListCustomers (
[0] Allen Haley 1916-12-07 20000101 -> 6641
[1] Allen Haley 1916-12-07 20140820 -> 18496
[2] Allen Hunter 1942-02-27 20000101 -> 3248
[3] Allen Ian 1947-10-10 20000101 -> 5032
[4] Allen Isaac 1967-03-10 20000101 -> 11262
[5] Allen Isabella 1942-10-11 20000101 -> 4742
[6] Allen Isaiah 1959-10-11 20000101 -> 1530
[7] Allen Jack 1963-07-20 20000101 -> 18138
)
Gesucht wird der Surrogate_ID von Haley Allen geb. am 07.12.1916, die am 19.08.2014 ein Einkauf getätigt hat. Binäre Suche Algorithmus funktioniert so, dass zunächst das mittlere Element der Liste ListCustomers[3] überprüft wird. Ist es größer als das gesuchte Element (ja), dann wird in der oberen Hälfte der Liste weitergesucht. Danach wird das mittlere Element der oberen Hälfte ListCustomers[1] mit dem gesuchten Element verglichen. Ist es größer als das gesuchte Element (ja), dann wird die schon dividierte Hälfte der Liste wieder gesplittet, bis das Element gefunden wurde.
Allerdings, wie man es vielleicht merken konnte, wird die Suche nach dem Element
Allen Haley 1916-12-07 20140819
ein leeres Ergebnis liefern, da ein solches Element gar nicht in der Liste vorhanden ist. Für unsere Zwecke reicht es allerdings aus, die untere Grenze zu finden, also das Element
Allen Haley 1916-12-07 20000101,
da wir feststellen möchten, ab wann eine Surrogate_ID gültig ist, also ab dem Jahr 2000 für das Beispiel. Allerdings nach entsprechender Anpassung des Algorithmus würden wir trotzdem die von uns gewünschten Surrogate_ID 6641 bekommen. Dazu muss lediglich nach derfrühesten gültigen SCD_START_DATE_ID gesucht werden, falls keine eindeutige Übereinstimmung gefunden wurde. An dieser Stelle besteht allerdings die Gefahr, dass man eine falsche Surrogate_ID bekommt. Angenommen, es wird nach einem Element gesucht, das in unserer ListCustomers überhaupt nicht vorhanden ist:
Zheng Edwin geb. 1974-11-06 mit Verkaufsdatum 2014-07-01
Als Ergebnis würde man ListCustomers[7] bekommen, da nicht nach genauer Übereinstimmung, sondern nach der unteren Grenze gesucht wird. Bevor also das Ergebnis zurückgegeben wird, muss zusätzlich überprüft werden, ob das Business Key an sich übereinstimmt, ohne SCD_START_DATE_ID zu betrachten.
Nun gehe ich darauf ein, wie ein solcher Algorithmus in SSIS implementiert werden kann.
Im SSIS Paket zum Laden der Fakten wird zunächst das Verkaufsdatum (SALES_DATE_ID) in den Datentyp Integer konvertiert, da auch die beiden Gültigkeitsdaten vom gleichen Datentyp sind.
Anschließend nutzen wir eine Skript Komponente, mit der Transformationen im Datenfluss vorgenommen werden können.
Folgende Spalten werden als Input definiert:
Als Output wird die Spalte angelegt, nach der wir eigentlich nachschlagen wollen, der Spalte Surrogate_ID in der Kundendimension. Wir benennen sie als CUSTOMER_ID:
Um auf die Dimensionstabelle zugreifen zu können, müssen wir in der Skript Komponente einen Verbindungsmanager angeben.
Nachdem alle Vorbereitungen erledigt wurden, können wir mit dem eigentlichen Programmieren der Skript-Komponente anfangen (in diesem Beispiel mit C#).
Zunächst werden zwei globale Variablen deklariert: eine SqlConnection connection Variable und eine globale generische List<Customer> ListCustomers. Die connection Variable wird dafür benötigt, um die Verbindung zur Datenbank herzustellen, um die Einträge aus der Tabelle DimCustomer abzurufen. Anschließend werden die nach dem Business Key sortierte Datensätze aus der Tabelle in die generische Liste ListCustomers hinzugefügt.
public class ScriptMain : UserComponent
{
//global Variables
SqlConnection connection = new SqlConnection("");
List<Customer> ListCustomers = new List<Customer>();
Das passiert nur ein einziges Mal zur Laufzeit des SSIS Paketes. Dazu wird die Methode FillListCustomers in PreExecute() aufgerufen, der die globale Variable connection übergeben wird.
public override void PreExecute()
{
base.PreExecute();
string connString = AdjustConnectionString(this.Connections.DWH.ConnectionString);
//connextion corresponds to "Server=ABCServer;Database=TestDatabase;Trusted_Security=True;"
connection.ConnectionString = connString;
// fills the "List<Customer> ListCustomers" with objects from a SQL query:
FillListCustomers(connection);
}
Mit der Methode AdjustConnectionString werden noch bestimmte Elemente aus dem ConnectionString entfernt. Dabei werden unerlaubte Schlüsselwörter „Provider“ und „Auto Translate“ entfernt, da es sonst zu Fehlern während der Ausführung kommen kann.
/// <summary>
/// Modification of the Connection string: removes not allowed key words
/// see msdn article for allowed keywords:
/// http://msdn.microsoft.com/en-us/library/system.data.sqlclient.sqlconnection.connectionstring.aspx
/// </summary>
/// <param name="connStr"></param>
/// <returns>a modified String with removed key Words "Auto translate" and "Provider"</returns>
public static string AdjustConnectionString(string connStr)
{
string newConnString = "";
string[] strTeile = connStr.Split(';');
foreach (string teil in strTeile)
{
if (teil.Contains("="))
{
string[] keyValuePaar = teil.Split('=');
if (!(keyValuePaar[0].Contains("Auto Translate") || keyValuePaar[0].Contains("Provider")))
{
newConnString += keyValuePaar[0] + "=" + keyValuePaar[1] + ";";
}
}
}
return newConnString;
}
Es ist für die binäre Suche zwingend notwendig, dass die Datensätze in der Liste nach dem Businesskey sortiert werden. Dies erfolgt in der Methode FillListCustomers.
/// <summary>
/// Fills the global ListCustomers list with the records from DimCustomer table.
/// </summary>
/// <param name="conn"> current SqlConnection to the DB with DimCustomer table</param>
private void FillListCustomers(SqlConnection connection)
{
string sqlQuery = @"SELECT [NAME]
,[VORNAME]
,[GEBURTSDATUM]
,[SCD2_START_DATE_ID]
,[Surrogate_ID]
FROM [dwh].[DimCustomer]
ORDER BY [NAME], [VORNAME],[GEBURTSDATUM]";
SqlCommand cmd = new SqlCommand();
SqlDataReader reader;
cmd.CommandText = sqlQuery;
cmd.CommandType = CommandType.Text;
cmd.Connection = connection;
connection.Open();
reader = cmd.ExecuteReader();
while (reader.Read())
{
Customer customer = new Customer();
customer.Name = (String)reader["NAME"];
customer.Vorname = (String)reader["VORNAME"];
customer.Geburtstag = (DateTime)reader["GEBURTSDATUM"];
customer.Scd2StartDateID = (int)reader["SCD2_START_DATE_ID"];
customer.CustomerID = (int)reader["Surrogate_ID"];
ListCustomers.Add(customer);
}
reader.Close();
connection.Close();
}
Es muss weiterhin die Klasse Customer definiert werden. Diese implementiert die Schnittstelle IComparable, s.d. BinarySearch()-Methode angewendet werden kann. Deshalb enthält die Klasse außer dem Konstruktor auch eine Methode namens CompareTo().
public class Customer : IComparable<Customer>
{
public string Name { get; set; }
public string Vorname { get; set; }
public DateTime Geburtstag { get; set; }
public int Scd2StartDateID { get; set; }
public int CustomerID { get; set; }
/// <summary>
/// A constructer for the Customer class.
/// </summary>
/// <param name="name"></param>
/// <param name="vorname"></param>
/// <param name="geburtstag"></param>
/// <param name="scd2StartDateID"></param>
public Customer(string name, string vorname, DateTime geburtstag, int scd2StartDateID)
{
Name = name;
Vorname = vorname;
Geburtstag = geburtstag;
Scd2StartDateID = scd2StartDateID;
}
/// <summary>
/// An empty constructer
/// </summary>
public Customer()
{
}
/// <summary>
/// Compares the current instance with another object of the same type and
/// returns an integer that indicates whether the current instance precedes,
/// follows, or occurs in the same position in the sort order as the other object.
/// </summary>
/// <param name="otherCustomer"></param>
/// <returns></returns>
public int CompareTo(Customer otherCustomer)
{
int result;
// CompareTo() returns -1, 0 or 1
result = this.Name.CompareTo(otherCustomer.Name);
if (result != 0) return result;
result = this.Vorname.CompareTo(otherCustomer.Vorname);
if (result != 0) return result;
result = this.Geburtstag.CompareTo(otherCustomer.Geburtstag);
if (result != 0) return result;
result = this.Scd2StartDateID.CompareTo(otherCustomer.Scd2StartDateID);
if (result != 0) return result;
return 0; //All properties were equal
}
}
Im Grunde vergleicht CompareTo() zwei Objekte der gleichen Klasse und gibt -1, 0 oder 1 zurück, je nachdem, ob das aktuelle Objekt in der sortierten Reihenfolge zuvor, gleich oder nachher erscheint. In unserem Beispiel werden Business Keys und Gültigkeitsstartdatum von 2 Kunden nacheinander verglichen. Es ist wichtig, einzelne Attribute zu vergleichen und nicht etwa die Verkettungen von Business Keys, weil einzelne Attribute verschiedene Längen haben können, was zu falschen Ergebnissen führen kann.
In Input0_ProcessInputRow wird für jede Zeile aus dem Datenfluss die Methode GetCustomer() aufgerufen, die ein Objekt der Klasse Customer aus der zuvor gefüllten Liste ListCustomers zurück gibt (falls gefunden).
public override void Input0_ProcessInputRow(Input0Buffer Row)
{
Customer customer = new Customer();
if (!Row.NAME_IsNull && !Row.VORNAME_IsNull && !Row.GEBURTSDATUM_IsNull && !Row.SALESDATEID_IsNull)
{
customer = GetCustomer(Row.NAME, Row.VORNAME, Row.GEBURTSDATUM, Row.SALESDATEID);
if (customer != null)
{
Row.CUSTOMERID = customer.CustomerID;
}
else
Row.CUSTOMERID = -1;
}
}
Betrachten wir die Methode GetCustomer() etwas näher. Es wird mithilfe der binären Suche Algorithmus in der zuvor gefüllten und sortierten Liste ListCustomers nach dem übergebenen Objekt Customer gesucht.
Falls das Objekt gefunden wurde, dann wird der Null-basierte Index iScore in der Liste ListCustomers enthaltenen Elementes zurückgegeben. Wenn das Element nicht gefunden wurde, wird ein negativer Wert geliefert. Dieser Wert ist dann das Komplement (die Bits wurden gedreht) des nächstgrößeren Index. Da wir nach der frühesten gültigen SCD_START_DATE_ID suchen, erhalten wir also mit if (iScore < 0) iScore = (short)(~iScore – 1); genau das Ergebnis, das gesucht wird, also die untere Grenze:
/// <summary>
/// Returns the CustomerID from the ListCustomers based on teh Business Key and scd2StartDateID
/// </summary>
/// <param name="name"></param>
/// <param name="vorname"></param>
/// <param name="geburtstag"></param>
/// <param name="scd2StartDateID"></param>
/// <returns>Customer</returns>
private Customer GetCustomer(string name, string vorname, DateTime geburtstag, int scd2StartDateID)
{
//BinarySearch: The zero-based index of item in the sorted List<T>, if item is found; otherwise,
//a negative number that is the bitwise complement of the index of the next element that is larger than item or,
//if there is no larger element, the bitwise complement of Count.
Int32 iScore = (Int32)ListCustomers.BinarySearch(new Customer(name, vorname, geburtstag, scd2StartDateID));
if (iScore < 0) iScore = (short)(~iScore - 1);
if (iScore == -1
//it should also be ensured, that the found business key also exists in the dimension:
|| ListCustomers[iScore].Name != name
|| ListCustomers[iScore].Vorname != vorname
|| ListCustomers[iScore].Geburtstag != geburtstag)
return null;
return ListCustomers[iScore];
}
Die Prüfung
if (iScore == -1
|| ListCustomers[iScore].Name != name
|| ListCustomers[iScore].Vorname != vorname
|| ListCustomers[iScore].Geburtstag != geburtstag)
return null;
stellt sicher, dass bei einem nicht in der Dimension vorhandenen Business Key keine falsche CUSTOMER_ID geliefert wird.
Bei unserem vereinfachten Beispiel aus 8 Elementen
ListCustomers (
[0] Allen Haley 1916-12-07 20000101 -> 6641
[1] Allen Haley 1916-12-07 20140820 -> 18496
[2] Allen Hunter 1942-02-27 20000101 -> 3248
[3] Allen Ian 1947-10-10 20000101 -> 5032
[4] Allen Isaac 1967-03-10 20000101 -> 11262
[5] Allen Isabella 1942-10-11 20000101 -> 4742
[6] Allen Isaiah 1959-10-11 20000101 -> 1530
[7] Allen Jack 1963-07-20 20000101 -> 18138
)
wird der Aufruf
Int32 iScore = (Int32)ListCustomers.BinarySearch(newCustomer(Allen, Haley, 1916-12-07, 20140819))
als iScore das Komplement des nächstgrößeren Index liefern, also: -2 als Integer, oder ~1
Dann wird iScore mit dem Aufruf
if (iScore < 0) iScore = (short)(~iScore - 1)
auf 0 gesetzt: ~(-2)-1=0. Somit hätten wir als Ergebnis ListCustomers[0].
Hilfreich ist der Algorithmus besonders dann, wenn in den Tabellen mit großen Datenmengen gesucht wird. So, für 1 Mio Datensätze werden maximal log2N = 20 Schritte benötigt, um das gesuchte Element zu finden.
Kompletter Code der main.cs finden Sie hier.