algoritmi di JOIN: l'eredità dei DBMS ai tempi dei key-value store.

portate pazienza, si tratta di un post concettuale. abbiamo appena o stiamo per sostituire o affiancare, nei nostri programmini, agli ormai tradizionali DBMS (postgresql, mysql, sqlite - tanto per esemplificare) un qualche brillante key-value store (redis, riak, o il velocissimo lmdb - anche qui per esemplificare).

il key-value store si presenta logicamente come una pseudotabella di soli due campi (chiave, valore) dove la chiave indicizza il valore permettendone il ritrovamento all'interno della tabella. un altro modello logico di comprensione del key-value store è quello dell'array associativo - un vettore di valori indicizzati per chiave (di solito una stringa) - reso persistente su disco.

va tutto bene, anzi una meraviglia - solo che prima o poi mi accorgo che devo mettere in una qualche relazione dati immagazzinati in due pseudotabelle diverse. oops, ma per queste cose con il DBMS avrei fatto una bella JOIN mentre, sorpresa, i key-value store non implementano l'algebra relazionale. 

ah ok è un classico caso del principio detto di faenza - si fa senza; andiamo solo a vedere come fanno i DBMS ad implementare le join, poi le riproporremo funzionalmente nel nostro codice applicativo.

per fortuna qualcuno su wikipedia si è preso il disturbo di tramandare ai posteri tutta questa scienza: ecco infatti come funzionano, in linea di principio, le nested loop join, le hash join, le sort-merge join: buona lettura.

ora, qualcuno potrebbe pensare, e non avrebbe tutti i torti, che stiamo facendo un gigantesco passo all'indietro se dopo quarant'anni circa di database relazionale ci tocca reimplementare le join a manina: è un'opinione legittima.

lmdb (e py-lmdb): dentro OpenLDAP si nasconde la nuova lepre dei database key/value store

sembra che ci sia un nuovo sceriffo in città. il suo nome è Lightning MDB (lmdb): è un key/value store (logicamente si presenta come un semplice tabellone con due campi, una chiave ed un valore) ai benchmark fa faville (batte anche levelDb di google). ah, in giro non si trova facilmente - è però a disposizione con la distribuzione di OpenLDAP.

ovviamente c'è l'interfaccia per python, py-lmdb, eccola qui.

fosse tutto qui non sarebbe davvero male, ma non molto interessante. quando ho provato ad usarlo però - su un esempietto facile facile (trovare le righe doppie in un file da 7M di righe circa) - ho mandato in vacca il programma per aver provato a fare tutto in un'unica transazione: la bestiaccia mi ha dato MDB_TXN_FULL (errore -30788) cioè "Txn has too many dirty pages".

uh-uh, sembra ci sia un limite hard-coded (cioè "inchiodato" nel codice) alla dimensione max di una transazione, così almeno riporta la mailing list di openLDAP assieme alla (consueta) promessa che il limite verrà tosto eliminato.

già, ma nel frattempo? beh, visto che py-lmdb si porta appreso una copia dei sorgenti di lmdb si può provare ad inchiodarci un valore più elevato (non risolverò del tutto ma almeno sposto il confine più avanti). cerca cerca (mi piace vincere facile, lmdb sono in tutto quattro soli file) ecco finalmente in midl.h la riga responsabile (la riga 60)

#define MDB_IDL_LOGN    16  /* DB_SIZE is 2^16, UM_SIZE is 2^17 */

è stato sufficiente impostare il valore a 24 e ricompilare il module. per comodità mia ho fatto una copia del modulo con il (nuovo) nome lmbdXXL (extra-large) in modo da poter tenere a disposizione anche l'originale e fare così tutti i confronti del caso. l'interfaccia tramite cpython funziona (la cffi no, boh devo ancora capire).

astenersi perditempo seriali

esempio banale che illustra come poter dormire per più di un secondo al secondo.

#! /usr/bin/env python

import multiprocessing
from time import time, sleep
import random
import sys, os

# how big is the process pool

POOLSIZE = 5

# how many (named) works to process

BEDS = ["b0", "b1", "b2", "b3", "b4", "b5", "b6", "b7", "b8", "b9"]
sleepList = BEDS[0:POOLSIZE] * 10

    
def PerdiTempo(aSleepName):
    currtime = time()
    name = multiprocessing.current_process().name
    rc = random.randint(1,10)
    sleep(rc)
    sys.stderr.write("name %s, pid: %d - (bed %s) - sleep %d. time elapsed %f\n" % (name, os.getpid(), aSleepName, rc, time() - currtime))
    return rc

if __name__ == "__main__":
    currtime = time()
    print "%s started, pid: %d, pool size: %d" % (sys.argv[0], os.getpid(), POOLSIZE)
    print "to sleep:", sleepList
    po = multiprocessing.Pool(POOLSIZE)
    res = po.map_async(PerdiTempo,(i for i in sleepList))
    w = sum(res.get())
    print "total time lost: %d (sec.)" % (w,)
    elap = time() - currtime
    print 'pid: %d ended, pool size of %d workers. time elapsed: %f (sec.). speedup: %5.2fx' % (os.getpid(), POOLSIZE, elap, w/elap)

dalla khan academy, un altro mooc: tutorial sulle liste in python

questo tutorial sulle liste in python è carino.


Python Lists: Understanding the basics of lists in Python

primavera: è tempo per i massive open online courses

sono stato distratto da qualche altra attività nell'ultimo mese, ma cmq tutto bene. l'ultima mia passione compulsiva - fresca fresca di stamane, sono i MOOC (massive open online courses), corsi online aperti per formazione a distanza. mi sono pure iscritto al mio primo mooc, Introduction to Data Science, che guarda caso utilizza i miei stessi building blocks (python, sql, R in misura minore) preferiti.

un tutorial sul sistema di controllo versione Git

continuo a mettere insieme i materiali per il mio prossimo corso Metodi ed applicazioni di informatica per l'analisi di dati biologici. questo tutorial su Git, il sistema di controllo versione del nuovo millennio, mi sembra abbastanza indicato. Citando l'autore "This is a tutorial is targeted at users who are new to version control systems, or just new to git. It goes over the basics of how to save and share your work in git, and give a conceptual explanation of branching".

per iniziare, non serve di più.

per gli aspiranti cultori della materia invece, la pagina (inglese) di wikipedia a riguardo è un passaggio obbligato.

le date in formato ISO8601, please

avviso ai naviganti: per passarsi le date, nulla di meglio del formato standard ISO8601 (ad esempio "oggi" si scrive 2013-03-01). e quando il valore è mancante? si può usare sempre il vecchio valore-tappo "0000-00-00". his fretus, ecco qui una stupidissima funzione che valida un campo data sì congegnato (ovviamente valida date nel range di funzionamento della funzione datetime.strptime()):



DATEFMTIN = "%Y-%m-%d"
DATEFMTOUT = '%04d-%02d-%02d'
MISSINGDATE = "0000-00-00"

def isValidDate(aString):
    # la stringa "0000-00-00" è il valore missing
    if aString == MISSINGDATE:
        return True
    try:
        #leggo la stringa AAAA-MM-DD in una data
        aDate = datetime.strptime(aString, DATEFMTIN)
        #converto la data letta in un'altra stringa
        anotherString = DATEFMTOUT % (aDate.year, aDate.month, aDate.day)
        #verifico che l'operazione sia idempotente
        assert aString == anotherString
        return True

    except ValueError, e:
        print "Date not Valid (value):", aString.__repr__()
        return False
          
    except AssertionError, e:
        print "Date not Valid (not idempot.)", aString.__repr__()
        return False


tribute: questo post non sarebbe mai esistito senza la pazienza, cura et abnegazione dell'ottimo M.Piccoli - non mi ha mandato a stendere, assieme a tutte le mie insopportabili saccenze. grazie 1K.