3

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?

  • Why am I being downvoted? Did I break some rule? – Jimbotron Jun 14 at 23:14
  • Is there a structure to the subset you are selecting? Is it a range? Every 2nd entry? Anything about the subsets that can be quantified? – Polygnome Jun 14 at 23:37
  • 2
    Assuming the ids are indexed, you might want to try id = 1 or id = 2 etc - in checks can be slow on certain platforms. There are other things to try/do, but cost they more time to implement, have bigger trade-offs, and/or depend on your usage patterns, – Telastyn Jun 14 at 23:38
  • 1
    Also, 100 billion ints times 4 byte per int is 400 GB. That is going to be slow unless you plan on beefing your server immensely with RAM. – Polygnome Jun 14 at 23:39
  • @Polygnome There is no structure to it. I'm simply exploring to see if there is a faster way to do this than indexing in RDBMS. Also let me clarify, there are roughly 1 billion ints, which can range from 1 to 100B not total of 100B ints. Could you comment of what options would be if there was some sort of range to the subset? – Jimbotron Jun 14 at 23:50
2

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 a1, a2, ..., an be the size of each search. Since the intervals overlap by at most the overshoot, we have a1 + a2 + ... + an ≤ 2m where m is the length of the larger list.

The complexity is now log(a1) + log(a2) + ... + log(an), which is maximized when the full sum is evenly distributed between the summands ai. 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.

| improve this answer | |
1

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.

| improve this answer | |
1

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.

| improve this answer | |
0

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.

| improve this answer | |
  • I cant imagine this being faster than RDBMS index. Is it? – Jimbotron Jun 15 at 5:43
  • 1
    @jimbotron - no, but it is easier to distribute across a cluster, which may be helpful at the kind of scale described in the question. – occipita Jun 15 at 22:27
0

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.

| improve this answer | |
  • 30 comparisons per integer being searched? So 30000 comparisons total? Would this be even close to indexed RDBMS speeds? – Jimbotron Jun 15 at 5:44
  • 1
    @Jimbotron Databases often use binary tree indexes, so this would be comparable. Of course, creating that index takes substantial effort because the set needs to be sorted first. If you're only querying the set a couple of times, a linear scan might still be faster, and is easily parallelizable. – amon Jun 15 at 5:59
  • 2
    @Jimbotron Database indexes are based on binary searches most of the time. Because the disk seek time dwarfs the time doing the actual comparisons, most use B-trees to localise a lot of the reads to a single block, but at the cost of much more disk usage. So what solution is best depends on how many times you need to look for 1000 IDs. And amon could be right, a linear scan might be fine if you only need to do it once. But if your list is already in order, then binary searches are a safe simple choice. – curiousdannii Jun 15 at 6:03
  • Database indexes are typically broad trees. B+ trees typically because values are all stored in the leaves so searches take constant time or IO is involved (e.g. record retrieval) and so saving a comparison half the time isn't worth the complexity of updating. Anyway, databases do use trees for indexing but they are almost always broad trees not binary trees. – ben rudgers Jun 16 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.