Il blog di Sandro Rizzetto

Il DataType MsSql hierarchyid: esperienze di uso reali

 

Nell'ambito dei nostri progetti astronomici di ottica adattiva ho dovuto affrontare la tematica di gestire quello che si chiama il Product Breakdown (o Product Tree), in pratica di gestire l'albero delle informazioni di come è composto un sistema con i suoi sottosistemi. Come si può immaginare un sistema finito come questo ha una tale complessità che la sua distinta base consta di migliaia (forse anche decine di migliaia) di oggetti e di qualche decina di livelli. In pratica quindi mi dovevo costruire dei tools per gestire in maniera efficiente un albero che parte dalla root del sistema e arriva alla singola vite o alla singola resistenza.

Dopo aver scartato strumenti non relazionali (un file xml penso avrebbe problemi prestazionali, i db no-sql li conosco poco) sono tornato al caro e vecchio Sql Server e cercando se la struttura migliore fosse il classico ItemId,ParentId,[Level] ho scoperto questo nuovo datatype di cui, mi vergogno a dirlo, ignoravo l'esistenza: il hierarchyid.

Senza andare a disquisire i singoli dettagli (visto che si trovano molte informazioni in rete come ad esempio questo tutorial) volevo raccontare le mie esperienze reali incontrate nello sviluppo.
Disclaimer: si tratta di esperienze maturate in pochi giorni di lavoro, quindi non prendeteli in assoluto come Best Practices, perché magari non è detto che siano sempre le soluzioni migliori

Prima di iniziare una rapida carrellata dei pro e contro:

  • PRO
    • Ordinare il tree in modo naturale (dalla root all'ultima foglia) oppure per livello è assolutamente banale, cosa invece molto più complicata nel caso di strutture id,parentid (anche usando le CTE ricorsive)
    • Se devo spostare interi rami da un livello ad un altro (oppure sotto un altro parent) ci sono delle funzioni che facilitano molto il lavoro
  • CONTRA
    • Per gestire le operazioni CRUD bisogna customizzare il vostro DAL (Data Access Layer); se avete già un vostro framework basato magari su un OR/M come Linq to Sql o EF, il tipo campo non è supportato e quindi le cose non funzionano; alla fine comunque basta scriversi qualche stored procedure e mappare le proprie entities con i dati ritornati da queste.
    • Non possiamo aspettarci che tool esterni (magari di reportistica) conoscano il campo e lo trattino nativamente

Struttura della tabella, views e stored procedure

In questo esempio ho dati dei nomi più generici possibili (item) in quanto questo tipo di struttura può servire sia per la sopracitata distinta base, come anche per organigrammi aziendali (classico Employee, Manager) o altre informazioni che hanno una struttura ad albero; come case study ho preso un po' di record di nomi geografici.

Consideriamo l'esempio di dover gestire un albero a n livelli del tipo

  • Pianeta
    • Continente
      • Nazione
        • Regione
          • … (fino al dettaglio di dove volete arrivare)

La tabella che ho costruito avrà questa forma:

image

Il primo campo è quello di tipo hierarchyid; ne esistono due calcolati che ci forniscono il primo una rappresentazione più "umana" (nella forma /a/b/c/d/) che non quella binaria e il secondo il livello del nodo (che parte da zero, quindi in alcuni caso conviene farsi tornare direttamente GetLevel()+1). Come si può notare i due campi classici ItemId e ParentId (messi in constraint da una self-reference) esistono ancora perché è molto più semplice gestire le stored procedure di CRUD e tutte le operazioni che faremo quando non abbiamo bisogno del campo ItemNode.

A parte l'indice della PK, ne ho aggiunto uno di univocità per l'itemId; a seconda delle query sarà poi possibile fare il tuning su eventuali altri indici necessari (es ItemLevel+ItemNode nel caso si facciano spesso ricerche o sort su foglie dello stesso ramo).

Lo script per creare la tabella è quindi:

CREATE TABLE [dbo].[Items](
    [ItemNode] [hierarchyid] NOT NULL,
    [ItemNodePath]  AS ([ItemNode].[ToString]()),
    [ItemId] [int] IDENTITY(1,1) NOT NULL,
    [ParentId] [int] NULL,
    [ItemLevel]  AS ([ItemNode].[GetLevel]()),
    [ItemName] [nvarchar](100) NOT NULL,
 CONSTRAINT [PK_Items] PRIMARY KEY CLUSTERED 
(
    [ItemNode] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]
GO
ALTER TABLE [dbo].[Items]  WITH CHECK ADD  CONSTRAINT [FK_Items_Items] FOREIGN KEY([ParentId])
REFERENCES [dbo].[Items] ([ItemId])
GO
ALTER TABLE [dbo].[Items] CHECK CONSTRAINT [FK_Items_Items]
GO

 

Inserimento un record

Per gestire l'inserimento di un record (sia il primo "root" che i successivi) bisogna usare due metodi speciali chiamati GetRoot e GetDescendant. Supponendo che l'applicazione abbia una UI (e non si lavori solo dentro il Sql Server Management Studio) sarà quindi necessario costruirsi una stored procedure di questo tipo al quale si passa il nome dell'item e il suo nodo parent (tramite il nostro ItemId che nell'esempio è un int ma potrebbe essere di qualsiasi tipo); il caso specifico del parent = null (nodo root) deve essere trattato. Per gli altri dettagli della GetDescendant e GetAncestor riferirsi ai link precedenti.

CREATE PROCEDURE [dbo].[spInsertItem]
@ItemName NVARCHAR(100), @ParentId INT
AS
BEGIN  
    SET NOCOUNT ON;
    IF (@ParentId IS NULL)    --root node
        INSERT INTO dbo.Items (ItemNode, ParentId, ItemName)
        VALUES ( hierarchyid::GetRoot(), @ParentId, @ItemName) 
    ELSE
        BEGIN
            DECLARE @parentNode hierarchyid, @lc hierarchyid, @itemNumber int
            SELECT @parentNode = ItemNode FROM dbo.Items WHERE ItemId = @ParentId
            SET TRANSACTION ISOLATION LEVEL SERIALIZABLE
            BEGIN TRANSACTION
               SELECT @lc = max(ItemNode) FROM dbo.Items WHERE ItemNode.GetAncestor(1) = @parentNode 
               INSERT INTO dbo.Items (ItemNode, ParentId, ItemName)
               VALUES ( @parentNode.GetDescendant(@lc,NULL),
                        @parentId,
                        @ItemName)          
             COMMIT
        END
    RETURN
END
GO

Il primo inserimento sarà quindi fatto chiamando la sp con parent = null e i successivi conoscendo l'id del parent (ovviamente in una applicazione reale ci sarà una tendina o un altro controllo che fornisce questo valore automaticamente)

EXEC dbo.spInsertItem @ItemName = N'World', @ParentId = NULL
EXEC dbo.spInsertItem @ItemName = N'Africa', @ParentId = 1
EXEC dbo.spInsertItem @ItemName = N'America', @ParentId = 1
..
EXEC dbo.spInsertItem @ItemName = N'Italy', @ParentId = 6
EXEC dbo.spInsertItem @ItemName = N'Trentino Alto Adige', @ParentId = 8
EXEC dbo.spInsertItem @ItemName = N'Bolzano', @ParentId = 11
..

Se adesso proviamo a fare un

SELECT * FROM Items ORDER BY ItemNode

abbiamo già il nostro albero ordinato "naturalmente" senza fare nessuno sforzo; anche se i nodi vengono inseriti non consecutivamente o con buchi di id (simulando cancellazioni e quindi salti di ItemId) non vi è nessun problema, in quanto è il campo ItemNode che si occupa di tutto
(l'ultimo campo è un banale REPLICATE(' ', 3*ItemLevel) + ItemName AS PaddedItemName tanto per far capire meglio il nesting)

image

Molte altre query sono facilitate dai metodi messi a disposizione, uno dei più comodi è IsDescendantOf che ritorna tutti i nodi "figli di" (compreso il padre); es.

DECLARE @node HIERARCHYID
SELECT @node = ItemNode FROM dbo.Items WHERE ItemName = 'Italy'
SELECT * FROM dbo.Items WHERE ItemNode.IsDescendantOf(@node) = 1

Una stored procedure per contare il numero di elementi di un nodo potrebbe essere questa (notare il –1 per escludere sé stesso e il cast se vogliamo passare la rappresentazione testuale /x/y/z/)

CREATE PROCEDURE [dbo].[GetTotalNumberOfChildren] 
    @itemNodePath VARCHAR(8000)
AS
BEGIN
    SET NOCOUNT ON;

    SELECT COUNT(*)-1 AS ChildrenCount
    FROM dbo.Items
    WHERE ItemNode.IsDescendantOf(CAST (@itemNodePath AS HIERARCHYID)) = 1
END

Modifica e cancellazione

Per quanto riguarda la cancellazione basta una banale stored procedure che faccia un DELETE From Items Where ItemId = @ItemId, ovvero useremo la nostra chiave univoca secondaria per identificare il record. Diverso il caso della modifica: se si tratta solo di cambiare qualche campo (come il nome dell'item) che non ha impatto sul tree, allora basta un banale UPDATE.. Where ItemId = @ItemId

Se invece dobbiamo muovere la nostra gerarchia, allora la cosa si fa più tricky e bisogna avvantaggiarsi del metodo GetReparentedValue. Facciamo l'esempio di aver assegnato per sbaglio un paese in un continente errato e di volerlo spostare.

image

Usando il metodo e passando il vecchio e nuovo parent, le cose si aggiustano

DECLARE @currentNode HIERARCHYID, @oldParent HIERARCHYID, @newParent HIERARCHYID
SELECT @currentNode = ItemNode FROM dbo.Items WHERE ItemId = 30 -- 'Egypt'
SELECT @oldParent = ItemNode FROM dbo.Items WHERE ItemId = 3 -- 'America'
SELECT @newParent = ItemNode FROM dbo.Items WHERE ItemId = 2 -- 'Africa'

UPDATE dbo.Items
 SET ItemNode = @currentNode.GetReparentedValue(@oldParent, @NewParent) 
 WHERE ItemNode = @currentNode 


image

Per spostare invece un intero ramo sotto un altro padre bisogna per forza usare un cursore o lato client oppure con una FETCH NEXT all'interno di una stored procedure. Facciamo un analogo esempio di voler spostare tutto il ramo United States sotto America invece che Africa

image

DECLARE @oldParent HIERARCHYID, @newParent HIERARCHYID

SELECT @oldParent = ItemNode FROM Items WHERE ItemId = 3 -- 'Africa'
SELECT @newParent = ItemNode FROM Items WHERE ItemId = 2 -- 'America'

DECLARE children_cursor CURSOR FOR
SELECT ItemNode FROM Items WHERE ItemId = 31    -- 31=USA; 
--se volessi spostare TUTTI i figli di Africa
--SELECT ItemNode FROM Items WHEREItemNode.GetAncestor(1) = @OldParent 

DECLARE @ChildId hierarchyid;
OPEN children_cursor
FETCH NEXT FROM children_cursor INTO @ChildId;
WHILE @@FETCH_STATUS = 0
BEGIN
START:
    DECLARE @NewId hierarchyid;
    SELECT @NewId = @NewParent.GetDescendant(MAX(ItemNode), NULL)
    FROM Items WHERE ItemNode.GetAncestor(1) = @NewParent;

    UPDATE Items
    SET ItemNode = ItemNode.GetReparentedValue(@ChildId, @NewId)
    WHERE ItemNode.IsDescendantOf(@ChildId) = 1;
    IF @@error <> 0 GOTO START 
        FETCH NEXT FROM children_cursor INTO @ChildId;
END
CLOSE children_cursor;
DEALLOCATE children_cursor;


image

E' ovviamente opportuno e banale farsi una stored procedure (la mia si chiama spMoveNode) che accetta in input gli ItemId numerici del nodo da spostare, e il vecchio e nuovo parentId.

Data Access Layer

Se il nostro DAL è fatto "alla vecchia" e utilizza direttamente ADO.NET (SqlConnection, SqlCommand, SqlDataReader, ecc.) non ci saranno problemi a chiamare le nostre Stored Procedure (List, GetSingle, ListBy, Insert,Update, Delete,MoveNode, ecc.) e utilizzare quelle bindando i nostri controlli o mappando a mano le nostre Business Entities.

Se invece usassimo un OR/M come Linq to Sql o Entity Framework, le cose si complicano un attimo, in quanto il datatype non è riconosciuto. Se infatti tentiamo di portare la nostra tabella Items dentro il Designer di L2S o EF (anche la 6.1.1) ci becchiamo un bel errore di "not supported".

La MIA soluzione (che non è detto sia quella corretta) è stata di farmi una view che ha gli stessi campi della tabella tranne quello hieararchyid e portare dentro quella per creare l'Entity L2S. Per ovviare al problema della mancanza del campo principale sul quale fare il sort, si può usare lo stesso campo convertito a varbinary (CAST itemNode as varbinary(892)). Attenzione infatti a non fare il mio errore di pensare che ItemNodePath vada bene, in quanto se abbiamo più di 10 items  il ramo /1/4/10/ viene prima di /1/4/9/ essendo trattato come una stringa; io comunque ho preferito portarmi dentro anche le varie stored procedure (che al loro interno fanno ORDER BY itemNode) e che esponendo gli stessi campi della vista, possono ritornare l'entità generata dalla vista.

image

(NB l'entità ORM può essere usata direttamente dalla UI come nell'esempio sottostante, ma ovviamente è buona norma avere delle proprie Custom Entities e un Mapper "frullino" che le gira e le fa ritornare da un layer Biz… se non lo scrivo, l'amico Rob mi toglie il saluto!!)

private void BindGrid()
    {
        GeoManagerDataContext db = new GeoManagerDataContext();
        var items = db.spListItems();
        grdList.DataSource = items;
        grdList.DataBind();
    }

imageimage

NB: per avere nella dropdown gli elementi nested ho usato il trucco di prima del Replicate solo usando un &nbsp; al posto dello spazio. Questo però non è sufficiente in quanto bisogna fare il decode dell'html nell'evento OnDataBound del controllo

protected void ddlItems_DataBound(object sender, EventArgs e)
   {
        foreach (ListItem listItem in ddlItems.Items)
        {
            listItem.Text = HttpUtility.HtmlDecode(listItem.Text);
        }
    }

Per completare l'argomento, bisogna dire che nel namespace Microsoft.SqlServer.Types, esiste la structure SqlHierarchyId; sarebbe quindi possibile estendere la partial class dell'entità generata dall'OR/M con una proprietà di questo tipo mappare il campo convertito in varbinary tramite dei BinaryReader/BinaryWriter. E' da notare comunque che questa colonna di tipo SqlHierarchyId non può essere usata in query Linq, quindi rimango dell'avviso che l'approccio surrogate key e stored procedure sia la strada da percorrere.

Trasformare i dati in XML

Quando si vede una struttura gerarchica si pensa subito ad un albero XML che in effetti ogni tanto potrebbe essere comodo per serializzare l'albero o per fare il binding a controlli che supportano questa fonte. E' ovvio che in C# a colpi di XDocument, XElement, ecc possiamo iterare la nostra collection e costruirci il nostro documento xml come ci aggrada; visto però che anche SQL Server riesce a generare dell'xml in modo molto efficiente (più del mio codice di sicuro!), perché non sfruttare questa possibilità? Ecco quindi una stored procedure che tramite una User Defined Function ricorsiva genera i nostri nodi con gli attributi che ci servono (nell'esempio solo id e nome).

CREATE FUNCTION [dbo].[udf_GetChildren](@id hierarchyId)
RETURNS XML
WITH RETURNS NULL ON NULL INPUT 
BEGIN 
RETURN
(
    SELECT 
         ItemId AS "@ItemId",
         ItemName as "@ItemName",
        CASE WHEN @id = ItemNode.GetAncestor(1) THEN dbo.udf_GetChildren(ItemNode) END
    FROM dbo.Items 
    WHERE @id = ItemNode.GetAncestor(1)
    FOR XML PATH('Item'), TYPE
);
END

CREATE PROC [dbo].[spListItemsXML]
AS

DECLARE @ResultXML xml

SET @ResultXML = 
(
SELECT  
ItemId AS "@ItemId",
ItemName as "@ItemName",
dbo.udf_GetChildren(ItemNode)
FROM dbo.Items
WHERE ItemNode.GetLevel() = 0
FOR XML PATH('Item'),  TYPE
)

SELECT @ResultXML as [ItemTreeXML]

RETURN 
GO

Lanciata la stored l'output è qualcosa di simile

image

Come possiamo sfruttare questa fonte ? Per esempio mettendolo in binding a un asp:Treeview ( o analogo controllo Ajax o jQuery) per avere il classico tree collapsed/expanded.

<asp:XmlDataSource ID="xmlDS" runat="server" XPath="/Item" />

<asp:TreeView ID="tvItem" runat="server" DataSourceID="xmlDS">
    <DataBindings>
        <asp:TreeNodeBinding DataMember="Item" TextField="ItemName" />
    </DataBindings>
</asp:TreeView>

private void BindTreeView()
{
    var xmlResult = db.spListItemsXML().SingleOrDefault();
    if (xmlResult != null)
    {
        xmlDS.Data = xmlResult.ItemTreeXML.ToString();
        tvItem.DataBind();
    }
}

Risultato:

image

Rendering dei dati in un organigramma

Concludo questa lunga trattazione con un accenno ad una API di Google che mi è venuta in aiuto per generare un diagramma ad albero in modo molto semplice. Si tratta della Organizational Chart (che fa parte della suite free Google Charts) alla quale basta passare un array che contiene Item, ParentId, eventuale tooltip. L'item può essere passato nella forma value/format, quindi v: sarà il suo id e f: il suo nome, eventualmente anche corredato da tag HTML per decorarlo.

Ad ogni nodo può essere associata una classe css ad esempio per colorare i continenti in colori diversi, oppure –perché no- per mettere come sfondo al DIV le bandiere delle nazioni!! I nodi possono essere collassati/espansi con un doppio click (ma non viene fatto il resize del diagramma).

La generazione del dati ovviamente può avvenire in vari modi (con un asp:Repeater, iterando e costruendosi con uno StringBuilder il ClientScript, con un servizio che restituisce JSON, ecc.)

<html xmlns="http://www.w3.org/1999/xhtml">
<head runat="server">
    <title></title>
    <script type="text/javascript" src="https://www.google.com/jsapi"></script>
    <script type="text/javascript">
        google.load("visualization", "1", { packages: ["orgchart"] });
        google.setOnLoadCallback(drawChart);
        function drawChart() {
            var data = new google.visualization.DataTable();
            data.addColumn('string', 'Item');
            data.addColumn('string', 'Parent');
            data.addColumn('string', 'ToolTip');

            data.addRows([
                [{ v: '1', f: 'World' }, '', ''],
                [{ v: '2', f: 'Africa' }, '1', ''],
                [{ v: '36', f: 'Egypt' }, '2', ''],
                [{ v: '3', f: 'America' }, '1', ''],
                [{ v: '31', f: 'United States' }, '3', ''],
                [{ v: '32', f: 'California' }, '31', ''],
                [{ v: '33', f: 'Los Angeles' }, '32', ''],
                [{ v: '35', f: 'Anaheim' }, '33', ''],
                [{ v: '34', f: 'Utah' }, '31', ''],
                [{ v: '4', f: 'Antarctica' }, '1', ''],
                [{ v: '5', f: 'Asia' }, '1', ''],
                [{ v: '6', f: 'Europe' }, '1', ''],
                [{ v: '8', f: 'Italy' }, '6', ''],
                [{ v: '11', f: 'Trentino Alto Adige' }, '8', ''],
                [{ v: '14', f: 'Bolzano' }, '11', 'Bozen'],
                [{ v: '18', f: 'Appiano Ssdv' }, '14', ''],
                ...ecc.
            ]);
            
            data.setRowProperty(15, 'style', 'border: 2px solid red;');

            var chart = new google.visualization.OrgChart(document.getElementById('chart_div'));
            chart.draw(data, { allowHtml: true, allowCollapse:true });
        }
        </script>
    

</head>
<body>
    <form id="form1" runat="server">
        <p>&nbsp;</p>
    <div id="chart_div""></div>
    </form>
</body>
</html>

Il risultato è questo (United States è selected e si potrebbe recuperare con getSelection(), Lombardia è collapsed, alla riga 15 –Appiano- è stato cambiato lo stile e il tooltip sopra Bolzano purtroppo non viene nello screenshot)

image

Conclusioni

Quello che manca a questo lungo "compendio" sarebbero delle considerazioni sulle performance e sull'uso dopo molti mesi dalla messa in produzione. Alcuni post mettono in guardia sulla realibility (come quello di Paul Nielsen, autore di Sql Server Bible), mentre altri sostengono che con decine di migliaia di record non hanno avuto nessun problema…  Tra qualche mese/anno, quando avrò dentro tutta la struttura dello specchio quaternario M4 di E-ELT , vi farò sapere…

Aggiungi Commento

Copyright © 1997-2017 Sandro Rizzetto | All Rights Reserved | Riproduzione delle fotografie vietata | Powered by me