lichtenberger

Regarding XQuery we just added JSON querying on top in Brackit[1] / SirixDB[2].

Brackit is a retargetable query compiler and does a lot of optimizations at compile time as for instance optimizing joins and aggregations. It is useable as an in-memory processor or as a query processor of a database system.

The Ph.D. thesis of Sebastian:

Separating Key Concerns in Query Processing - Set Orientation, Physical Data Independence, and Parallelism

http://wwwlgis.informatik.uni-kl.de/cms/fileadmin/publicatio...

[1] http://brackit.io

[2] https://sirix.io

Of course you can simply create a module with something like the above snippet as a function for reuse. Or I can add a built-in function for flattening like this or as in pandas.

Something like this (very simplified):

  let $array := [{"foo":0,"bar":"tztz"},{"foo":"hello","bar":null},{"foo":true,"bar":"yes"}]
  let $value := for $object in $array
                return
                  let $fields := bit:fields($object)
                  let $len := bit:len($fields)
  
                  for $field at $pos in $fields
                  return if ($pos < $len) then (
                    $object=>$field || ","
                  ) else (
                    $object=>$field || "\n"
                  )
  return string-join($value,"")

will output:

  0,tztz
  hello,null
  true,yes

Of course you can do it with http://brackit.io.

What exactly is the "transformation" you envision?

Hi all,

Brackit[1] is a flexible JSON query processor developed during Dr. Sebastian Bächles time as a PhD student at the TU Kaiserslautern in the context of their research in the field of query processing for semi-structured data. The system features a fast runtime and a flexible compiler backend, which is, e.g., able to rewrite queries for optimized join processing and efficient aggregation operations. It's either usable as an in-memory ad-hoc query engine or as the query engine of a data store. The data store itself can add sophisticated optimizations in different stages of the query processor. Thus, Brackit already bundles common optimizations and a data store can add further optimizations for instance for index matching.

Sebastian did his research for his Ph.D. at the TU-Kaiserslautern at the database systems group of Theo Härder. Theo Härder coined the well-known acronym ACID with Andreas Reuter, the desired properties of transactions.

As he's currently not maintaining the project anymore, I stepped up and forked the project a couple of years ago. I'm using it for my evolutionary, immutable data store SirixDB[2], which stores the entire history of your JSON data in small-sized snapshots in an append-only file (tailored binary format similar to BSON). It's exceptionally well suited for audits, undo operations, and sophisticated analytical time travel queries.

I've changed a lot of stuff, such that Brackit is getting more and more compatible with the JSONiq query language standard, added JSONiq update primitives, array slices as known from Python and fixed several bugs. Furthermore, I've added interfaces for temporal data stores, temporal XPath axis to navigate not only in space, but also in time and temporal extension functions in SirixDB, index rewrite rules, etc. pp.

As Brackit can query XML, you're of course able to transform XML data to JSON and vice versa.

Moshe and I are working on a Jupyter Notebook / Tutorial[3] for interactive queries.

We're looking forward to your bug reports, issues, and questions. Contributions are, of course, highly welcome. Maybe even implementations for other data stores or common query optimizations.

Furthermore, we'd gladly see further (university-based?) research.

It should, for instance, be possible to add vector instructions for SIMD instructions in the future, as the query engine is already set-oriented and processes sets of tuples for the so-called FLWOR expressions (see JSONiq). Brackit rewrites FLWOR expression trees in the AST to a pipeline of operations to port optimizations from relational query engines for efficient join processing and aggregate expressions. Furthermore, certain parts of the queries are parallelizable, as detailed in Sebastian's thesis. We also envision a stage for the compiler to use distributed processing (first research used MapReduce, but we can now use better-suited approaches, of course).

Kind regards

Johannes

[1] http://brackit.io

[2] https://sirix.io | https://github.com/sirixdb/sirix

[3] https://colab.research.google.com/drive/19eC-UfJVm_gCjY--koO...

Hi all,

Sebastian and his students did a tremendous job creating Brackit[1] in the first place as a retargetable query engine for different data stores. They worked hard to optimize aggregations and joins. Despite its clear database query engine routes, it's furthermore useable as a standalone ad-hoc in-memory query engine using a CLI or embedding it in other Java/Kotlin projects.

Sebastian did his research for his Ph.D. at the TU-Kaiserslautern at the database systems group of Theo Härder. Theo Härder coined the well-known acronym ACID with Andreas Reuter, the desired properties of transactions.

As he's currently not maintaining the project anymore, I stepped up and forked the project a couple of years ago. I'm using it for my evolutionary, immutable data store SirixDB[2], which stores the entire history of your JSON data in small-sized snapshots in an append-only file (tailored binary format similar to BSON). It's exceptionally well suited for audits, undo operations, and sophisticated analytical time travel queries.

I've changed a lot of stuff, such that Brackit is getting more and more compatible with the JSONiq query language standard, added JSONiq update primitives, array slices as known from Python and fixed several bugs. Furthermore, I've added interfaces for temporal data stores, temporal XPath axis to navigate not only in space, but also in time and temporal extension functions in SirixDB, index rewrite rules, etc. pp.

As Brackit can query XML, you're of course able to transform XML data to JSON and vice versa.

Moshe and I are working on a Jupyter Notebook / Tutorial[3] for interactive queries.

We're looking forward to your bug reports, issues, and questions. Contributions are, of course, highly welcome. Maybe even implementations for other data stores or common query optimizations.

Furthermore, we'd gladly see further (university-based?) research.

It should, for instance, be possible to add vector instructions for SIMD instructions in the future, as the query engine is already set-oriented and processes sets of tuples for the so-called FLWOR expressions (see JSONiq). Brackit rewrites FLWOR expression trees in the AST to a pipeline of operations to port optimizations from relational query engines for efficient join processing and aggregate expressions. Furthermore, certain parts of the queries are parallelizable, as detailed in Sebastian's thesis. We also envision a stage for the compiler to use distributed processing (first research used MapReduce, but we can now use better-suited approaches, of course).

Kind regards

Johannes

[1] http://brackit.io

[2] https://sirix.io | https://github.com/sirixdb/sirix

[3] https://colab.research.google.com/drive/19eC-UfJVm_gCjY--koO...

Hi all,

Sebastian and his students did a tremendous job creating Brackit[1] in the first place as a retargetable query engine for different data stores. They worked hard to optimize aggregations and joins. Despite its clear database query engine routes, it's furthermore useable as a standalone ad-hoc in-memory query engine.

Sebastian did his research for his Ph.D. at the TU-Kaiserslautern at the database systems group of Theo Härder. Theo Härder coined the well-known acronym ACID with Andreas Reuter, the desired properties of transactions.

As he's currently not maintaining the project anymore, I stepped up and forked the project a couple of years ago. I'm using it for my evolutionary, immutable data store SirixDB[2], which stores the entire history of your JSON data in small-sized snapshots in an append-only file (tailored binary format similar to BSON). It's exceptionally well suited for audits, undo operations, and sophisticated analytical time travel queries.

I've changed a lot of stuff, such that Brackit is getting more and more compatible with the JSONiq query language standard, added JSONiq update primitives, array slices as known from Python and fixed several bugs. Furthermore, I've added interfaces for temporal data stores, temporal XPath axis to navigate not only in space, but also in time and temporal extension functions in SirixDB, index rewrite rules, etc. pp.

As Brackit can query XML, you're of course able to transform XML data to JSON and vice versa.

Moshe and I are working on a Jupyter Notebook / Tutorial[3] for interactive queries.

We're looking forward to your bug reports, issues, and questions. Contributions are, of course, highly welcome. Maybe even implementations for other data stores or common query optimizations.

Furthermore, we'd gladly see further (university-based?) research.

It should, for instance, be possible to add vector instructions for SIMD instructions in the future, as the query engine is already set-oriented and processes sets of tuples for the so-called FLWOR expressions (see JSONiq). Brackit rewrites FLWOR expression trees in the AST to a pipeline of operations to port optimizations from relational query engines for efficient join processing and aggregate expressions. Furthermore, certain parts of the queries are parallelizable, as detailed in Sebastian's thesis. We also envision a stage for the compiler to use distributed processing (first research used MapReduce, but we can now use better-suited approaches, of course).

Kind regards

Johannes

[1] https://github.com/sirixdb/brackit

[2] https://sirix.io | https://github.com/sirixdb/sirix

[3] https://colab.research.google.com/drive/19eC-UfJVm_gCjY--koO...

I guess for static data a carefully crafted trie would probably be even faster as it just has to compare a byte or more in each node and thus is O(K) whereas K is the key length instead of O(n) where n is the number of keys.

If it isn't static the height optimized trie by Robert Binna is the most advanced trie, I guess. It might also be a good fit for a static trie as it keeps the height to a minimum.

Another comment already mentions this, but I guess a functional data structure would be easiest to maintain, even though there's stuff like this for PMEM such that any data structure would work essentially: https://pmem.io/

This[1] Open Source data store I'm maintaining is storing a huge tree of tries eventually on durable storage, but it's essentially a huge persistent index stored in an append-only file. The last layer of "indirect index pages" stores list of pointers to page fragments, which store the actual records (the list however is bound to a predefinded size). A single read-write trx per resource syncs the new page fragments, which mainly only include the updated or new records plus the paths to the root page to a durable device during a postorder traversal of the in-memory log. The last thing is an atomic update, which sets a new offset to point to the new UberPage, the root of the storage. All pages are only word aligned except for RevisionRootPages, which are aligned to a multiple of 256 bytes. All pages are compressed and might in the future optionally be encrypted.

I guess these byte addressable persistent memory devices are an ideal fit for small sized parallel random reads of potentially tiny page fragments to reconstruct a full page in-memory.

However, I hope they'll eventually achieve a better price in comparison to DRAM and SSDs than Intel Optane DC PMEM current price range.

[1] https://github.com/sirixdb/sirix

Why not using DAX FS mode for Optane DC memory for instance and serialize the data structure by hand? I'm not sure how much performance you lose. That said the data store I'm working on serializes the huge persistent in-memory index to durable storage in a postorder traversal (mainly changed records in a data page Plus path copies) and atomically sets an offset to the main root, the UberPage to the new revision in a file. So, I'd say it's precisely what you describe :-)

For servers there's already Intel Optane DC Memory and it's not fast enough to replace volatile memory in most cases, but way faster than flash drives. Thus, UltraRAM might have no real benefit? Maybe we'll have to wait, also regarding the cost factor.

BTW: if someone is interested to contribute or use the project... my open source project, an evolutionary, immutable JSON data store will benefit from fast random, fine granular access to durable storage as it has to read scattered word aligned page fragments from random locations in an append-only file in parallel to reconstruct a full page in-memory. The crux is that SirixDB is storing a huge persistent tree of tries index over revisions plus user defined indexes, a path summary and shared object fields in one log-structured appended only file. It does not simply copy whole database pages, but mainly stores only changed records/nodes.

So it mainly stores the whole index in one file (append-only) plus an offset file to map timestamps to revision offsets (besides the 32bit revision numbers / revisions stored in the main file). This means that we can store checksums of the child db pages in parent pages as in ZFS and to store the checksum of the UberPage in the page itself to validate the whole resource and we don't need a seperate transaction log despite an in memory cache for the single read-write trx.

https://github.com/sirixdb/sirix and a query processor called Brackit for document stores based on a JSONiq like query language: https://github.com/sirixdb/brackit

I wonder if it's faster than Intel Optane DC Memory and if that's the deciding advantage, such that no additional volatile DRAM is needed:

https://news.ycombinator.com/item?id=29906049

This might be too restricting regarding the storage.

But we have a function: https://github.com/sirixdb/brackit

If you don't want both, then use

https://github.com/sirixdb/brackit

for instance :)

We're working on an implementation for SirixDB with currently a slightly different syntax (for instance "=>" to dereference object fields). We're also supporting all kinds of temporal query enhancements (point in time queries, time travel queries...):

https://github.com/sirixdb/sirix

The query engine used is developed here (core implemented by Sebastian Bächle and his tudents). Ideally the backend can be any other data store as well.

https://github.com/sirixdb/brackit

That's so true. I still work and put a lot of energy and work into a project I began to love during my time at the university: https://github.com/sirixdb/sirix

I've spent so much of my spare time working on the project with some gaps since 2012 (and before under a different name at the university since 2006 or 2007). Last year during Hacktoberfest I got first contributions and since then at least another guy, Moshe works constantly on clients for Python and TypeScript and a frontend using Svelte: https://github.com/sirixdb/sirix-svelte-front-end

I've got a lot of great contributions since october last year and it's such a good feeling, despite spending money for the domain https://sirix.io and stuff like a logo and so on :-)

If you encounter spelling errors or grammatical issues, please help fixing on https://github.com/sirixdb/sirix and https://sirix.io :-) I'm no native english speaker, so I'd be very happy if people fix stuff.

Yes, that's great, but I think in the long-term it would be super awesome to not have to spend so many extra hours, but to somehow get sponsored and to be able to reduce the "normal" work time for the company I'm working to for instance 60 or 70%. I guess that would be a huge win, as I also want to spend more time with my girlfriend and for other hobbies.

I'm doing it like you mentioned, that is spending at least 2 hours 4 to 5 days a week (or sometimes more if time permits) since the last 1,5 years and 5,5 years with breaks in-between. However, last year was pretty awesome, as the project now get's contributions at least weekly and I've found at least one member, who is consistently pushing the project :-)

Yes, I mean Optance DC Persistent Memory. It's hard because they seems to market three different product categories under almost the same name (Optane Memory, Optane DC Persistent Memory and SSDs).

It might add some overhead, but I guess it depends on the page implementation, but 16 bytes seems to be the minimum (and Optane Memory might , I agree. That said if someone changes only one record the best thing is to write in the smallest granularity possible on the storage medium.

So, it might well be that someone is only interested in only one or a few records. Why then fetch and cache a whole 4Kb page if latency is good in both cases (4kb and 256 bytes)? On the other hand I agree that you should probably cache more data from a hot page.

I think along those lines, reading and writing fine granular data, especially when storing the full history of the data is the way to go (in addition to path copying and a log-structured storage). Furthermore pointer swizzling might be needed to get almost in-memory database performance.

I'm trying to address this with my versioned Open Source DBMS project, where only page-fragments are stored and bunch of them is read in-parallel to reconstruct a full page in-memory. Adding mini-page ps plus a simple cache at some point with hot data from several page fragments at least is orthogonal:

https://github.com/sirixdb/sirix | https://sirix.io

You can efficiently read 256 Byte granular data (4 cache lines) with Optane Memory (due to checksums). I think it makes much more sense to read/write fine granular changes for instance at least align pages to 64 or 256 Bytes instead of 4kb pages, where you often times first of all write too much data and secondly you pollute the caches with probably unnecessary data. There's a paper about how to add cache line aligned mini-pages (16 cache-lines): https://db.in.tum.de/~leis/papers/nvm.pdf

Great questions/discussions in the end as well :-)

In case anyone watches this: The Q/A In the end is also very interesting :-)

Great to see the advances made in Crux :-)

I'm working on a versioned database system[1] in my spare time which offers similar features and benefits. The core is Java based, whereas the Server is written in Kotlin using Vert.x. A Python client as well as currently a TypeScript based client for a non-blocking, asynchronous HTTP-Server exists.

The data store can easily be embedded into other Java/Kotlin based projects without having to use the Server indirection.

Lately I changed a lot of stuff regarding the set-oriented query engine which uses an XQuery derivate to process both XML and JSON as well as structured data. For now I've integrated rule based index rewriting stuff to answer path queries and path queries with one predicate through the index, filtering false positives if necessary. Next, I'll add a twig based operator and AST rewrite rules to answer multiple path queries with a single scan over smaller subtrees.

Furthermore, I want to use the new Java Foreign Memory API to memory map the storage file and change the tuple-at-a time iterator model to fetch batches of tuples at once for better SIMD support through the JVM.

I've also thought about replacing the Kafka backend with SirixDB itself, as SirixDB doesn't need a WAL for consistency... so SirixDB can hopefully horizontally scale at some point in the future.

Some of the futures so far:

    - storage engine written from scratch
    - completely isolated read-only transactions and one read/write transaction concurrently with a single lock to guard the writer. Readers will never be blocked by the single read/write transaction and execute without any latches/locks.
    - variable sized pages
    - lightweight buffer management with a "kind of" pointer swizzling
    - dropping the need for a write ahead log due to atomic switching of an UberPage
    - rolling merkle hash tree of all nodes built during updates optionally
    - ID-based diff-algorithm to determine differences between revisions taking the (secure) hashes optionally into account
    - serialization of edit operations for changed subtree roots to make comparisons between consecutive revisions or subtrees thereof incredibly fast (no-diff computation needed at all)
    - non-blocking REST-API, which also takes the hashes into account to throw an error if a subtree has been modified in the meantime concurrently during updates
    - versioning through a huge persistent and durable, variable sized page tree using copy-on-write
    - storing delta page-fragments using a patented sliding snapshot algorithm
    - using a special trie, which is especially good for storing records sith numerical dense, monotonically increasing 64 Bit integer IDs. We make heavy use of bit shifting to calculate the path to fetch a record
    - time or modification counter based auto commit
    - versioned, user-defined secondary index structures
    - a versioned path summary
    - indexing every revision, such that a timestamp is only stored once in a RevisionRootPage. The resources stored in SirixDB are based on a huge, persistent (functional) and durable tree 
    - sophisticated time travel queries

As I'm spending a lot of my spare time on the project and would love to spend even more time, give it a try :-) Any help is more than welcome.

Kind regards Johannes

[1] https://sirix.io and https://github.com/sirixdb/sirix

Brackit seems to be similar to OctoSQL in some ways, but probably more for semi-structured data as for instance XML and JSON, while querying with XQuery instead of SQL:

http://wwwlgis.informatik.uni-kl.de/cms/dbis/projects/bracki...

The project itself (http://brackit.org) might not be further developed by Dr. Sebastian Baechle and his students under supervision from Dr. Dr. Theo Härder (invented transactions / ACID semantics), but I'm maintaining a fork with a lot of JSON processing enhancements and time travel query additions:

https://github.com/sirixdb/brackit

I'd love to refactor main parts of the query processor and to port it to Kotlin. However, as always it would be amazing to get help :-)

Research possibilities are almost endless of course, especially regarding distributed query processing with Fink or Kafka, looking into how best to support concurrent operations...

Publications:

Separating Key Concerns in Query Processing - Set Orientation, Physical Data Independence, and Parallelism:

http://wwwlgis.informatik.uni-kl.de/cms/fileadmin/publicatio...

XQuery Processing over NoSQL Stores:

http://wwwlgis.informatik.uni-kl.de/cms/fileadmin/publicatio...

BrackitMR: Flexible XQuery Processing in MapReduce:

http://wwwlgis.informatik.uni-kl.de/cms/fileadmin/publicatio...

Unleashing XQuery for Data-independent Programming:

http://wwwlgis.informatik.uni-kl.de/cms/fileadmin/publicatio...

Versatile XQuery Processing in MapReduce:

http://wwwlgis.informatik.uni-kl.de/cms/fileadmin/publicatio...

I'm working on a versioned, temporal DBMS[1] called SirixDB in my spare time, which is the most exciting thing :-)

It's based on a university project on which I was working basically since day one in 2006.

I know it's crazy to work on such a large project initially alone. Lately, however, I'm getting the first contributions, and maybe I should start collaborating with the university or with the company of my former supervisor (who began the project for his Ph.D.).

I'm now more than convinced that the ideas are worth to work on, especially in the advent of modern hardware as byte-addressable NVM :-)

Currently, I'm working on the storage engine itself, to reduce storage space consumption further and to make the system stable. I'm experimenting with larger data sets to import (JSON and XML currently up to 5GB) with and without auto-commits, enabling/disabling different features, for instance, storing a rolling merkle hash for each node, storing the number of descendants, a path summary and so on.

Some of the features:

    - the storage engine is written from scratch
    - completely isolated read-only transactions and one read/write transaction concurrently with a single lock to guard the writer. Readers will never be blocked by the single read/write transaction and execute without any latches/locks.
    - variable-sized pages
    - lightweight buffer management with a "kind of" pointer swizzling
    - dropping the need for a write-ahead log due to atomic switching of an UberPage
    - rolling merkle hash tree of all nodes built during updates optionally
    - ID-based diff-algorithm to determine differences between revisions taking the (secure) hashes optionally into account
    - non-blocking REST-API, which also takes the hashes into account to throw an error if a subtree has been modified in the meantime concurrently during updates
    - versioning through a huge persistent and durable, variable-sized page tree using copy-on-write
    - storing delta page-fragments using a patented sliding snapshot algorithm
    - using a special trie, which is especially good for storing records sith numerical dense, monotonically increasing 64 Bit integer IDs. We make heavy use of bit shifting to calculate the path to fetch a record
    - time or modification counter-based auto-commit
    - versioned, user-defined secondary index structures
    - a versioned path summary
    - indexing every revision, such that a timestamp is only stored once in a RevisionRootPage. The resources stored in SirixDB are based on a huge, persistent (functional) and durable tree 
    - sophisticated time travel queries

Besides the storage engine challenges, the project has so many possibilities for further research and work:

    - How to shard databases
    - Query compiler rewrite rules and cost-based optimization
    - A brand new front-end
    - Other secondary index-structures besides AVL trees stored in data nodes
    - Storing graphs and other data types
    - How to best make use of modern hardware as byte-addressable NVM

[1] https://sirix.io or https://github.com/sirixdb/sirix

I think with modern hardware as for instance the now available first byte-addressable NVM variable sized pages and buffers should in theory get more widespread use and the reading/writing granularity gets more fine granular in the next years. I think as of now the Intel Optane memory however still has to fetch 256 Bytes at the minimum.

However, variable sized pages also allow page compression.

Can you give us some links to the mentioned issues and techniques that achieve high cache and storage bandwith efficiency without VSBs?