Calcolo progressivo via Cte e operatore Apply

Sql 2005, come è universalmente noto, ha introdotto, rispetto al predecessore, molte novità. Quello che ci interessa qui è un uso intrecciato e non standatd delle nuove Common Table Expression [cte] ricorsive e dell’operatore Apply.

L’idea base del funzionamento di una cte ricorsiva è abbastanza semplice, si consideri il set di dati S1. Mettendo questo set in join con altro posso ottenere un set di dati S2 che supporremo avere una struttura identica [Colonne e tipi] a S1. Fatto ciò è possibile usare S2 al posto di S1 per generare S3 e così via finché l’operazione non genera più alcun record. I risultati S1, S2, S3, S4… ottenuti, avendo la stessa identica struttura, saranno restituiti come concatenazione di records tramite union all.
Questo genere di strutture sono perfette per la gestione dei dati ricorsivi, volendo estrarre da un’organigramma una persona e tutti i suoi sottoposti, si può procedere come sopra con:

S1= Persona di Id=x
S2= Sottoposti di qualcuno che sta in S1
S3= Sottoposti di qualcuno che sta in S2
S4= Sottoposti di qualcuno che sta in S3
..

procedendo in questo modo fino ad incontrare un’estrazione vuota e unendo tutti i risultati si ha la query richiesta.
Questa stessa tipologia di approccio può essere usata, sulla carta, per lavorare con la stessa modalità sequenziale dei cursori pur rimanendo nell’ambito set based, con tutti i vantaggi che ciò comporta, la logica potrebbe essere:

S1= Record1
S2= SuccessoreDiRecord1=Record2
S3= SuccessoreDiRecord2=Record3
S4= SuccessoreDiRecord3=Record4
…

Se riuscissimo a scrivere questa cosa potremmo risolvere tutti i problemi di calcolo progressivo con una query molto elegante e performante, riducendo davvero a zero i casi in cui risultano più performanti i cursori.
C’è un problema però, il concetto di successore, ovviamente rispetto ad un certo ordinamento, è implementabile in SQL tramite la clausola TOP. Prendiamo per esempio la tabella di sistema sys.objects e immaginiamo di voler estrarre il successore, rispetto a object_id, del valore 100, avremo una query del tipo:

select top 1 * from sys.obejcts where object_id>100 order by object_id

ma, purtroppo, la clausola top non è ammessa nella parte ricorsiva di una cte.
Il fatto interessante di cui mi sono accorto in questi giorni è che questo vincolo è solo sintattico e non formale e si può quindi aggiarare con una funzione inline, consideraimo la seguente funzione:

create function fi_NextObject(@object_id int)
returns table as return

  select top 1 * from sys.objects 
  where object_id>@object_id 
  order by 
object_id

Questa funzione ritorna la tupla di sys.objects successiva a @object_id rispetto alla colonna object_id.
Ora, come usare questo strumento per risolvere il nostro

S2= SuccessoreDiRecord1=Record2

Con l’operatore Apply naturalmente.
Apply permette sostanzialmente di creare una tabella di join diversa per per ogni riga della tabella principale, nel nostro caso, questo potentissimo operatore potrà essere usato alla maniera di:

select n.* from S1
cross apply fi_NextObject(S1.object_id) n

Il bello naturalmente è che quella sintassi è ammessa in una cte ricorsiva, quindi possiamo scrivere:

with cte as(
  select * from dbo.fi_NextObject(0)
  union all
  select t.*
  from cte c

  cross apply dbo.fi_NextObject(c.object_id) t
)

  select * from cte

Il risultato è identico a quello che otterremmo facendo una banale:

  select * from sys.objects

ma abbiamo una differenza essenziale, l’accesso riga per riga!
Supponiamo infatti di voler calcolare la somma progressiva di object_id, otterremo il risultato con:

with cte as(

  select object_id, convert(bigint,object_id) s from dbo.fi_NextObject(0)

  union all

  select t.object_id, t.object_id+c.s

  from cte c

  cross apply dbo.fi_NextObject(c.object_id) t
)

  select * from cte

Ancora, supponiamo di voler ottenere una concatenazione di stringhe progressiva:

with cte as(

  select object_id, convert(varchar(max),Name) c from dbo.fi_NextObject(0)

  union all

  select t.object_id, c.c + ', ' + convert(varchar(max),t.Name)

  from cte c

  cross apply dbo.fi_NextObject(c.object_id) t
)

  select * from cte

E da questo possiamo quindi desumere una tecnica inline per ottenere la concatenazione di stringhe e che non faccia uso di XML.
Le prestazioni di questa forma di calcolo sono molto buone, paragonabili [Come ordine di grandezza, non come valore assoluto] ad un semplice join.
Di conseguenza, questa strategia batte pesantemente tutte le tecniche tradizionali basate su aggregazioni e su autojoin del tipo "on x1.id<x2.id" rispetto alle prestazioni ovviamente a patto che l’accesso al record successore avvenga tramite index scan su un covered index adeguato.

Il pluricitato post dell’amico Andrea Montanari che riepilogava le tecniche di estrazione dei Running-Totals va aggiornato. 😀
Inoltre il livello di calcolo progressivo offerto da questa strategia non è limitato dalla disponibilità di funzioni di aggregazione, ma è completamente libero, permettendo un approccio nuovo al calcolo progressivo avanzato come Lifo, Fifo, Valorizzazioni, Riordino merci, Calcolo disponibilità future ecc…

marc.

P.S. Uno speciale ringraziamento a Itzik Ben-Gan per aver testato e valutato apporofonditamente questa strategia inconsueta.