Running totals: cursori, complessità lineari, complessità esponenziali

Tra una birra ed un'altra qui a Madrid, continuano le chiacchere tra il sottoscritto, Davide e Itzik.

In queste righe voglio cercare di sottolineare come le soluzioni cursore non siano sempre da evitare come la peste...

Supponiamo di avere una tabella ORDERS, simile alla seguente:

Ovvero una tabella in cui abbiamo memorizzate, per semplicità, una quantità in ordine ed un identificativo cliente.

Quello che ci viene chiesto è: visualizzare la quantità in ordine e, accanto, il totale aggiornato degli stessi ordini. Ovvero una nuova colonna data dalla somma della quantità in ordine del record sommata alle quantità ordinate in precedenza dallo stesso cliente.

Il nostro problema ci chiede anche di ordinare i risultati secondo la colonna [customerID] (attenzione, i dati nella nostra tabella NON sono ordinati secondo questa colonna).

Un classico esempio di running totals insomma.

Graficamente,quindi, otterremmo qualcosa del genere:

Quello che ci serve per le nostre analisi è:

1. una tabella ordini (orders)
2. una procedura che popoli con un numero N di record la nostra tabella (up_populateOrders)
3. una procedura che risolva il nostro problema senza cursorse (up_withoutCursor)
4. una proceduda che risolva il nostro problema con cursore (up_withCursor)

All'interno delle due procedure che risolvono il nostro problema inseriremo anche una semplice istruzione che ci fornisca, in uscita, il tempo (espresso in millisecondi) trascorso per l'elaborazione ( SELECT datediff(ms,@StartDate, @EndDate) AS 'Execution time in ms' ).

Sottolineo come non sia il mio scopo, almeno non in questo post, analizzare come scriviamo il codice TSQL per risovlere il nostro problema.

Quello che voglio è valutare la bontà delle due soluzioni (con e senza cursore) e ragionare su queste.

Soluzioni che, evidentemente, devono necessariamente lavorare riga per riga per effettuare i calcoli necessari alla risoluzione del problema.

Il codice per costruire tutto quello che ci serve:

/* *** INIZIO CODICE TSQL *** */

USE tempdb
GO

IF OBJECT_ID('dbo.orders', 'U') IS NOT NULL
    DROP TABLE dbo.orders
GO

IF EXISTS ( SELECT  *
            FROM    INFORMATION_SCHEMA.ROUTINES
            WHERE   SPECIFIC_SCHEMA = N'dbo'
                    AND SPECIFIC_NAME = N'up_withoutCursor' )
    DROP PROCEDURE dbo.up_withoutCursor
GO

IF EXISTS ( SELECT  *
            FROM    INFORMATION_SCHEMA.ROUTINES
            WHERE   SPECIFIC_SCHEMA = N'dbo'
                    AND SPECIFIC_NAME = N'up_withCursor' )
    DROP PROCEDURE dbo.up_withCursor
GO

IF EXISTS ( SELECT  *
            FROM    INFORMATION_SCHEMA.ROUTINES
            WHERE   SPECIFIC_SCHEMA = N'dbo'
                    AND SPECIFIC_NAME = N'up_populateOrders' )
    DROP PROCEDURE dbo.up_populateOrders
GO

/* Creo la tabella ordini su cui faremo le nostre analisi */
CREATE TABLE orders
    (
      idRecord INT PRIMARY KEY
                   IDENTITY(1, 1),
      qty SMALLINT,
      customerID CHAR(1)
    )
GO

CREATE PROCEDURE dbo.up_populateOrders ( @numOrders int )
AS
    SET NOCOUNT ON

    TRUNCATE TABLE orders

    DECLARE @ciclo INT
    SET @ciclo = 0

    WHILE @ciclo < @numOrders
        BEGIN
            INSERT  orders
                    SELECT  CAST(RAND() * 100 AS INT),
                            'C'

            SET @ciclo = @ciclo + 1
        END

    SET @ciclo = 0
    WHILE @ciclo < @numOrders
        BEGIN
            INSERT  orders
                    SELECT  CAST(RAND() * 100 AS INT),
                            'A'

            SET @ciclo = @ciclo + 1
        END

    SET @ciclo = 0
    WHILE @ciclo < @numOrders
        BEGIN
            INSERT  orders
                    SELECT  CAST(RAND() * 100 AS INT),
                            'B'

            SET @ciclo = @ciclo + 1
        END

    SELECT  COUNT(*) AS numOrders
    FROM    orders

    SET NOCOUNT OFF
GO

CREATE PROCEDURE dbo.up_withoutCursor
AS
    SET NOCOUNT ON

    DECLARE @StartDate datetime,
        @EndDate DATETIME
    SET @StartDate = getdate()

    SELECT  customerID,
            O1.qty,
            O1.qty + ISNULL(( SELECT    SUM(O2.qty)
                              FROM      orders O2
                              WHERE     O2.idRecord < O1.idRecord
                                        AND O2.customerID = O1.customerID
                            ), 0) AS qtySum
    FROM    orders O1
    ORDER BY customerID,
            idRecord

    SET @EndDate = getdate()
    SELECT  datediff(ms, @StartDate, @EndDate) AS 'Execution time in ms'
    SET NOCOUNT OFF
GO

CREATE PROCEDURE dbo.up_withCursor
AS

  SET NOCOUNT ON

    DECLARE @StartDate datetime,
        @EndDate DATETIME
    SET @StartDate = getdate()

    DECLARE @myQty INT
    DECLARE @customerID CHAR(1)
    DECLARE @CID CHAR(1)
    DECLARE @sum int
    DECLARE @tableResults TABLE
        (
          qty SMALLINT,
          qtySum INT,
          customerID CHAR(1)
        )

    SET @myQty = 0
    SET @CID = ''

    DECLARE myCursor CURSOR FAST_FORWARD READ_ONLY
        FOR SELECT  qty,
                    customerID
            FROM    orders
            ORDER BY customerID,
                    idRecord

    OPEN myCursor

    FETCH NEXT FROM myCursor INTO @myQty, @customerID

    WHILE @@fetch_status = 0
        BEGIN
            IF @CID <> @customerID
            SET @sum = 0
            SET @CID = @customerID
            SET @sum = ( @sum + @myQty )
            INSERT  @tableResults
            VALUES  (
                      @myQty,
                      @sum,
                      @customerID
                    )

            FETCH NEXT FROM myCursor INTO @myQty, @customerID
        END

    SELECT  [customerID],
            [qty],
            [qtySum]
    FROM    @tableResults

    CLOSE myCursor
    DEALLOCATE myCursor

    SET @EndDate = getdate()
    SELECT  datediff(ms, @StartDate, @EndDate) AS 'Execution time in ms'
    SET NOCOUNT OFF

GO

/* *** FINE CODICE TSQL *** */

Costruito tutto quello che ci serve possiamo passare alle nostre analisi.

Se avete dato un'occhiata al codice vi sarete accorti che la SP che si occupa di inserire ordini inserirà un numero N di righe per tre ipotetici clienti: A,B,C.

Possiamo analizzare cosa succede con un numero molto basso di ordini, ad esempio: 2

EXEC dbo.up_populateOrders 2
DBCC dropcleanbuffers
CHECKPOINT

Quindi:

EXEC dbo.up_withoutCursor
DBCC dropcleanbuffers
EXEC dbo.up_withCursor

Il tempo di esecuzione è praticamente nullo per entrambe le soluzioni.

Alziamo il numero di ordini a 20 (quindi avremo 60 record in tabella), quindi eseguiamo nuovamente le procedure con  e senza cursore.

Quindi alziamo ancora il numero portandolo a 100, 500, 1000.

Noterete come, più alto sarà il numero di righe da analizzare migliore risulterà la soluzione con cursore.

C'è infatti una grande differenza tra soluzioni cursori e soluzioni set-based:

• le soluzioni cursore possono basarsi su dati ordinati
• le soluzioni set-based NON possono basarsi su dati ordinati

Questo significa che le soluzioni cursore, fatto un eventuale table scan possono utilizzare delle operazioni di seek su un resultset già ordinato.

Le soluzioni set-based utilizzeranno, invece, sempre degli scan.

Il piano di esecuzione della procedura senza cursore:

Il piano di esecuzione della procedura con cursore:

La differenza è quindi nella complessità dell'algoritmo di risoluzione.

• le soluzioni cursore hanno una complessità lineare (dove "o" rappresenta l'overhead dovuto ai calcoli richiesti)
• le soluzioni set-based hanno una complessità esponenziale

Quindi: maggiori saranno le righe interessate dalla nostra elaborazione, maggiore sarà la possibilità di preferire una soluzione basata su cursore.

Considerazioni?