Parallel query evaluation using operator precedence anguages

Operator Precedence Languages are a language family which extend the notion of operator precedence from primitive algebraic operations to all of the language operators and terminal symbols. These languages enjoy the local parsability property, which allows implementation of parallel parsing algorithms. An example application of parallel parsing is evaluation of an XPath query, while the input XML document syntax tree is being assembled by parallel workers. The purpose of the thesis is to optimize the performance of a parallel query evaluator implementation for the XPath querying language. The evaluator is built with the GOPAPAGENO toolchain for parallel parser generation, which uses the Operator Precedence Parallel Parsing algorithm. Performance optimization techniques such as memory preallocation, structure alignment, data structure optimization were applied in order to reduce the number of memory allocations made by the parser in runtime, and reduce the execution time. A significant speedup across all test queries both in sequential and in parallel performance was obtained.

I linguaggi di precedenza degli operatori sono una famiglia di linguaggi che estendono la nozione di precedenza degli operatori dalle operazioni algebriche primitive a tutti gli operatori di linguaggio e simboli terminali. Questi linguaggi godono della proprietà di parsabilità locale, che consente l'implementazione di algoritmi di parsing paralleli. Un esempio di applicazione del parsing parallelo è la valutazione di una query XPath, mentre l'albero sintattico del documento XML di input viene assemblato da worker paralleli. Lo scopo della tesi è ottimizzare le prestazioni di un'implementazione di un valutatore di query parallele per il linguaggio di query XPath. Il valutatore è costruito con la toolchain GOPAPAGENO per la generazione di parser paralleli, che utilizza l'algoritmo di parsing parallelo di precedenza degli operatori. Sono state applicate tecniche di ottimizzazione delle prestazioni come preallocazione della memoria, allineamento della struttura, ottimizzazione della struttura dei dati per ridurre il numero di allocazioni di memoria effettuate dal parser in fase di esecuzione e ridurre il tempo di esecuzione. È stata ottenuta una significativa accelerazione in tutte le query di test sia in sequenziale che in parallelo.