Data structure for multi key range queries

Question

I need a data structure that gives the best performance for multi-key range lookups. I do not need to update/insert/delete. This will be immutable. The use case is in-memory filtering of values over multiple dimensions. Research suggests k-d trees and BitMap indexes (specifically Roaring Bitmaps). It seems that k-d trees perform poorly. I am dealing with 1 to 6 dimensions for the key. I have not found a truly adequate solution. Ultimately I need to filter two different data sets, join them, and then reduce the values.

The closest analogy is a SQL inner join on multiple columns, multiplying the values from the two different tables, then summing the results. This is similar to Tensor Algebra with Tensor slicing. I have not found consensus on what the best data structure is for this.

Example

Here is an example of what I would like to support using SQL to illustrate the operation. I am working in .NET. SQL is just to illustrate the problem.

Note: I am not looking for answers which are "Just use SQL". I don't need the overhead of a full RDBMS. I'm looking for the best data structure to support these use cases.

Let's say we have two tables: Table1 and Table2. Table1 has a an index on IndexColumn and values in ValueColumn. Table2 is indexed by two different columns: IndexColumn1 and IndexColumn2. It has values in ValueColumn2. I want a data structure which makes the following fast:

SELECT
    SUM(Table1.ValueColumn * Table2.ValueColumn2)
FROM Table1
JOIN Table2
ON Table1.IndexColumn = Table2.IndexColumn1
WHERE
    Table1.IndexColumn < "Chicken"
    AND
    Table2.IndexColumn2 > 10

I am wanting to join these data sets on one of the index columns and perform range queries on the index columns as well. Right now I am doing this type of thing using a Map<'Key,'Value> but I have to enumerate the keys to perform the filtering. This does not scale. It is straightforward to use a more efficient filtering if the index is one dimension. Use a sorted array and binary search to find the values of interest and then take subsets of the array.

I am having trouble scaling this up to higher dimensions. Ideally I could support up to 6 dimensions for the keys. There is only ever 1 value column. My research suggests a k-d tree but even that seems like it may not perform well.

I need to join and filter data sets quickly. The size of data fits in memory. Largest data set I am working with would be 1M rows.

Answer 1

Indecies

If you have time to pre-build the in memory structure then lookup can be made very efficient if its all in memory.

First we need to create a few trees.

• Each lookup field gets a tree per sort operator mapping key value -> record id, permitting multiple keys
• Each collection of records gets a tree mapping record id -> record

Iterate each record in each collection and insert them into each tree relevant to that record.

Then create an array per tree over the same Key Value pair.

• Best if these arrays are memory page aligned
• Extra points if they are also file system page aligned (for the system paging the vram)

Transcribe each element in order from the trees into the arrays. Delete the trees.

Good now the filterable fields can be analysed for their record ids in log(N) time by using a binary search, and records can be looked up in log(N) time.

Now to deal with Join conditions. Hopefully one of the fields participating in joinable records was created above as a filterable field. If not, pick one set of records to create a lookup for that field in the form key value -> record id.

Create a two trees over the join:

• Record Type 1 ID -> Record Type 2 ID
• Record Type 2 ID -> Record Type 1 ID

Iterate through the collection of records that doesn't have the lookup on the joining field (or either if both are available) - Lookup the field value in the lookup to identify the joinable record ids and insert them into the trees.

Create arrays for each join tree and transcribe the elements into the array. Again kudos for alignment to memory and filesystem pages.

Good now the joins can be analysed for their record ids in log(N) time by using a binary search.

---

Now for the payoff of all that work. Here is a Naïve algorithm that presumes that all conditions are conjunctions (and). If a disjunction (or) is in the logic, you can rewrite the query to join together the results of two or more conjunction based queries, or you can handle the nuanced logic directly.

Lookup using the lower-upper bound search to list all candidate records per filtered field. If the candidate list is large, it may pay to pre-sort it.

Group these candidate lists per record collection type. Within each collection pick the smallest list and iterate over it. Keep only those ids found in every other candidate list. (if implementing or, you will need to be more selective about how you filter here).

Now you should have a list of valid record ids per collection.

Pick the smallest list and pick a join partner. Using their cross walk array iterate the picked candidate list and find the joinable record ids. Keep only those pairings whose second id appears in that second collections short-list. This should create a list of pairs (record type 1 id, record type 2 id).

Reiterate this paired candidate list picking another join partner on either record type. This will create a new list of candidates (record type 1 id, record type 2 id, record type 3 id).

Repeat until you have a list of record id tuples (record type 1 id, record type 2 id, ... , record type K id) and no other collections to join in.

Now it is simple to take these candidate tuples and lookup their records to project off the fields you want to select.

Answer 2

You can achieve such requirements using in-memory OLAP/BI solutions.

Also, some advanced caching technologies like Hazelcast are providing rich in-memory operations that can be used to achieve similar requirements.

On the other hand, if your data set is a result of an events stream, some stream processing technologies like Kafka provide SQL-like operations over in-memory tables known as Ktable.