DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports
Events Video Library
Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
View Events Video Library
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks

Integrating PostgreSQL Databases with ANF: Join this workshop to learn how to create a PostgreSQL server using Instaclustr’s managed service

Mobile Database Essentials: Assess data needs, storage requirements, and more when leveraging databases for cloud and edge applications.

Monitoring and Observability for LLMs: Datadog and Google Cloud discuss how to achieve optimal AI model performance.

Automated Testing: The latest on architecture, TDD, and the benefits of AI and low-code tools.

Related

  • Enhancing Hyperparameter Tuning With Tree-Structured Parzen Estimator (Hyperopt)
  • Crafting Mazes
  • Solving Unique Search Requirements Using TreeMap Data Structure
  • The Equivalence Rationale of Neural Networks and Decision Trees: Towards Improving the Explainability and Transparency of Neural Networks

Trending

  • The Power of Visualization in Exploratory Data Analysis (EDA)
  • The Convergence of Testing and Observability
  • Log Analysis: How to Digest 15 Billion Logs Per Day and Keep Big Queries Within 1 Second
  • The Agile Architect: Mastering Architectural Observability To Slay Technical Debt

Optimizing Voron and the Cost of Multi Trees

Oren Eini user avatar by
Oren Eini
·
May. 07, 14 · Interview
Like (0)
Save
Tweet
Share
2.71K Views

Join the DZone community and get the full member experience.

Join For Free

One of the nice features that Voron got from LMDB is the notion of multi trees. If I recall correctly, LMDB calls them duplicate items, or something like that. Basically, it is the ability to store multiple values for a single key.

Update: The behavior described in this post has been in LMDB for the over 3 years. It is just something that Voron didn't have. Please note that this post discuss the Voron's limitation and its solution, not LMDB, which has had the solution for a long time.

Those items are actually stored as a nested tree, which effectively gives us a great way to handle duplicates. From an API standpoint, this looks like this:

    // store
    tree.MultiAdd(tx, "Eini", "users/1");
    tree.MultiAdd(tx, "Eini", "users/3");
    tree.MultiAdd(tx, "Eini", "users/5");


    //read 
    using(var it = tree.MultiRead(tx, "Eini"))
    {
        if(it.Seek(Slice.BeforeAllKeys) == false)
            yield break;
        do
        {
            yield return it.CurrentKey; // "users/1", "users/3", "users/5"
        }while(it.MoveNext());
    }

Internally, we handle this in the following fashion:

  • If a multi add operation is the very first such operation, we’ll add it as a simple key/value pair in the tree.
  • If a multi add operation is the 2nd such operation, we’ll create a new tree, and add both operations to the new tree. The original tree will have the key/nested tree reference stored.

That lead to a very easy to use API, which is quite useful in many cases. However, it also have space usage implication. In particular, a tree means that we have to allocate at least one page to it. And that means that we have to allocate 4KB to hold any multi tree with more than a single value. Since there are actually a lot of scenarios where we would want to store a small number of small values, that can often lead to a lot of waste on our part. We use 4KB to store data that we could have stored in just 64 bytes, for example. That means that when we want to actually store things that might be duplicated, we actually need to consider the taken space consideration as well.

I think that this is a pretty bad idea, because it leads us to do things with composite keys under some scenarios. That is something that Voron should be able to just handle for me.  So we changed that, in fact, what we did was changed the way we approach multi trees in general. Now, for every multi value, we can store up to 1KB of items in the same page as the key, before we devolve into a full blown multi tree.

The idea is that we can use the same Page mechanism we use elsewhere, and just have a nested page inside the parent page. As long as the nested page is small enough, we can just store it embedded. That result in some nice space saving. Since usually we have items in the following counts: zero, one, few, lots.

We need this to help with Corax, and in general, that would reduce the amount of space we need to use in many cases.


Tree (data structure)

Published at DZone with permission of Oren Eini, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Related

  • Enhancing Hyperparameter Tuning With Tree-Structured Parzen Estimator (Hyperopt)
  • Crafting Mazes
  • Solving Unique Search Requirements Using TreeMap Data Structure
  • The Equivalence Rationale of Neural Networks and Decision Trees: Towards Improving the Explainability and Transparency of Neural Networks

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 3343 Perimeter Hill Drive
  • Suite 100
  • Nashville, TN 37211
  • support@dzone.com

Let's be friends: