How can billion integer ids be stored and specific ones checked for existence most efficiently? (persistent solution, not just in-memory)

Question

Let me preface this by saying that I am familiar with RDBMS. I have a solution using mysql/mariadb but I am not happy with the efficiency of the solution so I'm looking for alternatives.

I'm trying to find the most efficient way to store large amount of integers and be able to retrieve specific subset if it exists. Let me give you example:

Let's say we have a billion records of integers: 1, 3, 12, 74, 233, 235 ... Anywhere from 1 to 100 billion.

Now say someone gave me a list of 1000 integers 6, 12, 105, 233, 306...

How would I compare those 1000 against my billion records and only return those of the 1000 that exist in the billion?

In RDBMS/SQL solution, if ids in the billion rows are indexed, I can do:

SELECT
    *
FROM
    table
WHERE
    id IN (6, 12, 105, 233, 306...)

But this method is not as fast as I would like it to be.

Is there a better, faster way to do this with any database, software, specialized tool or programming method?

Answer 1

Scan through both lists in lockstep

Given two sorted lists, you can find their intersection by scanning through the lists, increasing the index of the lesser item. It looks something like this:

var i = 0, j = 0;
var intersection = [];
while (i < a.length && j < b.length) {
    if (a[i] == b[j]) {
        intersection.push(a[i]);
        i += 1;
        j += 1;
    } else if (a[i] < b[j]) {
        i += 1;
    } else {
        j += 1;
    }
}

Now, this runs in O(n+m) time where n and m is the length of each list, which is likely too slow as m is very large.

However, instead of increasing the index in the large list by 1 in each iteration, you can search forward by adding 1, then 2, then 4, then 8, and once you overshoot, you can use binary search to find the next index in the long list.

To compute the complexity of this, note that is just the cost of n binary searches. Let a₁, a₂, ..., a_n be the size of each search. Since the intervals overlap by at most the overshoot, we have a₁ + a₂ + ... + a_n ≤ 2m where m is the length of the larger list.

The complexity is now log(a₁) + log(a₂) + ... + log(a_n), which is maximized when the full sum is evenly distributed between the summands a_i. This gives a worst case complexity of n*log(2m / n), which is either the better or the same as the n*log(m) complexity of n ordinary binary searches depending on how n and m grow in proportion to each other.

Answer 2

I'll start off by saying I think the RDBMS can do this as well if not better than a custom solution but here are some ways you can do this.

Bloom Filter

The problem that a Bloom filter is designed to help solve is exactly the one you are working on: determining whether a number is part of a set. A bloom filter doesn't tell you for sure that a number is part of a set but it can tell you (very quickly) for sure that if it is not. Given 99% of the values in the range you have specified are not in the set, if you are checking numbers that are distributed across the range, this can greatly improve your average lookup times.

Clustering

If your values are distributed evenly across the range, this might not help but if you have 'clusters' of values you can improve performance by managing smaller datasets the contain those clusters. Again, there's an opportunity to quickly determine if a value is not in the DB: if it doesn't fall within one of the cluster ranges, you know it's not a value. If you have clusters but also values that are 'stand alone' you can maintain a smaller set of individual values.

By clustering you also have the opportunity to index in a way that is optimal for each subset. For example if you have a really tight cluster, you could invert the set to get a small negative list to check. If you've got a relatively small set of outliers, a tree might be a good option.

Answer 3

Per the question, the operation has two parts:

1. Determining if a record for a value exists.
2. Returning the record if the value exists.

Part 1: Existence

Per the question:

1. There are 100 billion possible values
2. 1 billion of those values actually exist.

Since these are integers and computers typically come in 32 bit and 64 bit flavors, they must be 64 bit integers to allow 100 billion possible values. Therefore a strategy that stores all the actual values uses approximately 8GB of space (one billion * 8 bytes).

However, existence (or presence in the database) is binary and can be represented by a single bit. An alternative approach is a bitmap of all possible values. 100 billion bits is approximately 12GB. This will fit in memory of a modestly specified computer with room to spare.

The Bitmap Datastructure

It is possible, but neither necessary or sufficient, to think of a 100 billion bit bitmap as a database with 100 billion rows. The utility of this abstraction is that all the gory database details of managing heap files, disk paging and caching strategies can be applied if one chooses. Or to put it another way, you can have databases all the way down.

Persisting the bitmap to disk and loading it into memory is also amenable to all the standard database mechanisms of working with blocks. But potentially easier because the bitmap is always sorted on key values and is fixed size so the block in which a "record" will be found can be calculated directly. For example with a 1MB page size, the bitmap exists across 12k pages. The location of an ID's status can be page ID modulo 12k and location ID modulo 1MB or more generically ID modulo numberOfPages : ID modulo blockSize.

Efficiency

If it's data and not just random numbers, efficiency is a function of implementation details. And determining what's efficient is a matter of measuring and determining what is inefficient in actual use. In other words, database tuning.

For some implementations, 12GB for a bitmap might be nothing more than throwing up another machine to a cluster. For other implementations, 12GB might be a non-starter for financial or bureaucratic reasons. That's just the nature of engineering as opposed to mathematics. But, at 12GB the operation can be done in memory and that means I/O can be avoided and I/O operations are the traditional measure of efficiency for databases...with the caveat that relative performance of in memory operations is just as dependent on caching and paging as on disk operations. The latencies are simply different magnitudes.

Underspecification

There's no way to know whether or not a bitmap is an appropriate engineering approach because engineering is the process of dealing with all the messy details and expectations of actual systems. The question does not describe these details and expectations.

Part 2: Record Retrieval

Performance is a matter of tuning the database for the actual workload. Standard methods will go a long way.

Answer 4

Divide and conquer.

Spread the billion integers across buckets based on what range they fall into, and store them in key-value format with key = bucket number and value = integers that fall in that range. Say each bucket covers a range of one million integers (you can adjust this based on your needs). Then you will have 100,000 buckets:

Bucket 1 = 1 - 1,000,000
Bucket 2 = 1,000,001 - 2,000,000
...

Indexing these buckets (100,000 keys) is much more efficient than indexing each individual record (a billion keys).

Now given a list of 1000 integers:

1. Find the buckets that they fall into (at most 1000 buckets)
2. Query each bucket to get the actual integers (can be parallelized)
3. Compare numbers in each bucket (can be parallelized)

You can also pre-compute and cache the list of non-empty buckets in memory to further reduce the number of queries you need to run. This cache will contain at most 100,000 entries but potentially much less based on the distribution of integers.

Answer 5

Binary search on an ordinary data file

If the only data that you need to store are the integers themselves, then you could simply store them as 64 bit integers in a data file, sorted in ascending order. Then with a binary search of at most 30 comparisons, you can find whether any integer is in your data set.