Sparse Linear Algebra in Column-Oriented In-Memory Database

摘要

Embodiments relate to storing sparse matrices in an in-memory column-oriented database system. Specifically, recent hardware shifts of primary storage from disc into memory, allow execution of linear algebra queries directly in the database engine. Dynamic matrix manipulation operations (like online insertion or deletion of elements) are not covered by most linear algebra frameworks. Therefore a hybrid architecture comprises a read-optimized main structure, and a write-optimized delta structure. The resulting system layout derived from the Compressed Sparse Row (CSR) representation, integrates well with a columnar database design. Moreover, the resulting architecture is amenable to a wide range of non-numerical use cases when dictionary encoding is used. Performance in specific examples is evaluated for dynamic sparse matrix workloads, by applying work flows of nuclear science and network graphs. Embodiments allow performing linear algebra operations on large, sparse matrices commonly associated with scientific computations and analytical business applications.

主权项

1. A computer-implemented method comprising:
causing an engine to store an updatable column representation of data including a row column in a main structure and in a delta structure of an in-memory database; causing the engine to merge the delta structure into the main structure when a delta exceeds a threshold; causing the engine to sort columns of the updatable column representation according to values of the row column; causing the engine to derive an index according to the sorted columns; causing the engine to reference the index to perform an algebraic operation; and causing the engine to store a result of the algebraic operation.