Range-Lookups mit den Integration Services – Teil III

In den vorangegangenen beiden Teilen dieses Artikels (Teil I, Teil II) haben wir uns mit den Möglichkeiten des Range-Lookups beschäftigt, die ohne weitere Programmierung oder zusätzliche Komponenten mit reinen SSIS-Boardmitteln realisiert werden können. Nun wollen wir uns mit einer dritten Variante beschäftigen, um in unserem Beispielszenario die Kunden nach Ihrem Einkommen in die bereits bekannten Einkommensgruppen einzuteilen:



Lösung mittels Script Task – Wunderwaffe „Binary Search“


Wenn einen die mitgelieferten Standardkomponenten der Integration Services mal wieder nicht so richtig ans Ziel bringen, dann gibt es ja zum Glück immer noch den Script Task, den wir auch dazu nutzen können, um einen eigenen Lookup zu realisieren. Und genau das werden wir jetzt tun. Script Transformation in unseren Datenfluss gezogen und schon kann es mit der Definition der Eingabespalten beginnen. In unserem Fall reicht das YearlyIncome aus:



Danach müssen wir dann noch die zugehörige Ausgabespalte definieren, die dann später unsere Gruppen-ID aufnehmen soll:



Da ich die möglichen Gruppen direkt im Script-Task aus der Datenbank lesen möchte (es gibt auch andere, durchaus sauberere Wege), benötige ich auch noch einen Verbindungsmanager (der Einfachheit halber mit dem .NET Provider für SQL Server):



Nun kann ich mir noch die Programmiersprache auswählen (ich nehm mal C#) und endlich mit der eigentlichen Arbeit beginnen.

Als erstes benötige ich einen gefüllten Cache, der die möglichen Ausprägungen meiner Gehaltsgruppen aufnehmen kann. Diesen definiere ich als globale generische Liste einer eigens dafür gedachten Klasse Namens „NumericRangeItem“:



Im PreExecute übernehme ich dann den Freigegebenen Verbindungsmanager und fülle einmalig den besagten Cache:



Im FillCache() werden dann die oben gezeigten Zeilen aus der Datenbank gelesen und für jede Zeile ein neues NumericRangeItem in den Cache übernommen. Das NumericRangeItem ist dabei im wesentlichen ein Key-Value-Pair, wobei IncomeFrom als Key und die zugehörige IncomeGroupID als Value übernommen wird :



Besonderheit ist, dass es die Schnittstelle IComparable implementiert. Dazu muss die Klasse also eine Methode namens CompareTo enthalten, die aber auch ziemlich simpel ist.



Damit wird lediglich festgelegt, dass beim Vergleich zweier NumericRangeItems die Schlüssel (also die Einkommensgrenze) miteinander verglichen werden.

Ergebnis ist, dass ich nach dem PreExecute alle Einkommensgrenzen als generische Liste vergleichbarer Elemente im Speicher habe. Belohnt werde ich für diesen Aufwand dann damit, dass eine solche Liste eine Methode namens BinarySearch() zur Verfügung stellt, die wir dann für den eigentlichen Lookup nutzen können:



Für jede Zeile die ein Einkommen enthält wird die Funktion GetID aufgerufen, die einen numerischen Wert übergeben bekommt und das dazu passende NumericRangeItem zurückgibt. Der zu suchende Wert wird dabei selbst in einem NumericRangeItem verpackt, damit der Vergleich funktioniert. Und dann kann BinarySearch() die eigentliche Arbeit übernehmen. Dabei wird immer in die Mitte der Wertmenge geschaut und überprüft ob der dort vorhandene Wert größer oder kleiner als der Vergleichswert ist und dann mit der jeweils passenden Hälfte weitergearbeitet. Dadurch kann man mit BinarySerach auch in großen Datenmengen sehr schnell suchen (im schlimmsten Fall werden log2(N)  +  1 Iterationen benötigt => zum Durchsuchen von 1 Mio Datensätzen werden höchstens 20 Versuche gebraucht). Was das Ganze für unser Szenario aber erst nutzbar macht, ist, dass auch für Werte, die nicht gefunden werden können ein Ergebnis geliefert wird.

Mathematisch ist dieser negative Rückgabewert das Komplement des nächstgrößeren Index. Da wir über die Untergrenzen suchen (IncomeFrom) erhalten wir also mit if (iScore < 0) iScore = (short)(~iScore – 1); genau das Ergebnis, dass wir für unseren RangeLookup brauchen.

Das Ergebnis sieht dann wie zu hoffen war folgendermaßen aus:



Dieses Bild haben wir so ähnlich bereits im Teil I gesehen, nur dass das Ergebnis diesmal in nicht mal einem Sechstel der Zeit berechnet war. Bei größeren Datenmengen verstärkt sich dieser Effekt sogar noch weiter. In unserem kleinen Beispiel benötigt der Script Task noch fast die Hälfte für das PreExecute, in dem ja auch der Cache gefüllt werden muss. Wenn wir aber nicht mehr 18k sondern ein paar Millionen Datensätze durch die Pipeline schicken, fällt dieser Overhead nicht mehr ins Gewicht.

Mit der Wunderwaffe BinarySearch brauchen wir also in Zukunft keine Angst mehr vor Range-Lookups bei großen Datenmengen zu haben.

3 Antworten auf „Range-Lookups mit den Integration Services – Teil III“

  1. Sehr geehrter Herr Schechner, ein sehr schönes Beispiel, für einen c#-Neuling aber schwer nachvollziehbar. Könnten Sie mir den kompletten Code des BinarySearch-Objects bereitstellen? Oder das Beispielprojekt selbst? Das wäre sehr schön. Vielen Dank. MfG, M. Schmuck

  2. Guten Tag Herr Schmuck,

    mittlerweile haben wir nicht mehr die Möglichkeit auf die vorgestellte Lösung zuzugreifen. Wir hoffen, dass mit diesem Blogbeitrag, der das Thema binäre Suche ausführlicher behandelt, alle offenen Fragen beantwortet werden. Gern können Sie bei weiteren Fragen eine Nachricht in den Kommentaren hinterlassen.

    MfG

    Christopher Glomb

  3. Eine kleine inhaltliche Korrektur: es werden nicht 20 Versuche für 1 Mio Datensätze benötigt, sondern 20 Versuche werden für eine Intervallpunktsuche benötigt bei dem die Intervallskala 1 Mio Intervallpunkte (hier: IncomeGroupID) hat. Die Problemgröße ist nicht die Anzahl der Datensätze sondern die Anzahl der Intervallpunkte in einer Intervallskala. Die binäre Suche spielt ihren Vorteil also erst bei größerenen Intervallskalen aus.

Schreibe einen Kommentar zu Christopher Glomb Antworten abbrechen