How to design a table that each rows have 5K boolean attributes?

Question

I have about 2M rows and each row looks like the following.

244 true false ... true

-> One integer column(V) and about 5K boolean columns(B1, B2, ..., B5K) associated to the integer.

Due to the limitation of the maximum number of columns that I can have for a row, I have separated the boolean columns(attributes) in a separate table.

Table V:

idx_V value_V
--------------
1     244  

...

Table B:

idx_V idx_B value_B
--------------------
1     1     true
1     2     false
...
1     5K    true
...

This design works alright when I try to find V's that match one boolean column. For example, finding V's where the 2nd boolean attribute is true:

select value_V 
where VT.idx_A = BT.idx_A 
    and idx_B = 2 
    and value_B = true 
from V_Table as VT 
    and B_Table as BT

But the query becomes awful when I have to find V's that match a multiple boolean columns, sometimes even for all 5K columns, like finding V's with B1=true, B2=false, B3=true, ... and B5K=false.

My primary use of the tables would be the following 2:

1. Find V's that x1th, x2th and xnth boolean columns are false/true (n can be anything between 1 and 5K)
2. Sublists:
   • Find the sequence of the boolean columns for a specific V: T F T T F F ...
   • Find other V's that match the sequence found in 2-A

I'm thinking about constructing a varchar[5K] field to store the boolean sequence to do 2 but it seems like there's just too much waste in space since each boolean only requires just 1 bit but I'm allocating a byte.

What would be the best way to go about this?

Answer 1

Combine the binary values into one or more integers and use binary arithmetic when computing the actual values. This will generate some decent cpu overhead, but the complexity of the data is massively reduced. i.e.

True True True True = 8+4+2+1 = 15
True False False True = 8+0+0+1 = 9
False True True False = 0+4+2+0 = 6

Answer 2

So are you concerned more about the space usage or the query complexity?

The query is a type of relational-division query, for example to find values for which 6 or more booleans are true:

SELECT value_V
FROM V_Table AS V
JOIN B_TABLE AS B USING (idx_A)
GROUP BY idx_A
HAVING SUM(value_B=true) >= 6;

As for storage, even with the BIT datatype, MySQL uses a minimum of 1 byte per column. To store any more compactly, you'd have to store a bitfield like @AndrewBrennan suggests. But you can't use BIT anyway, because it has a maximum length of 64.

You'd have to use a BINARY(625) to store 5000 bits, and SQL queries to find out many bits were set, or whether a specific Nth bit is set, would be even more difficult. For example, bitwise operators like |, & and ^ only work on 64-bit integers, not on binary strings of arbitrary length.

So I'd recommend sticking with the two-table design you have now. You have some storage overhead, but you have more flexibility for queries. You can save on storage by not storing rows for **false* values (assuming these are more common).

Answer 3

Might be worth considering a non-RDBMS solution, MongoDb for example. The querying would be pretty simple at the cost of a few MB. For example:

db.values.insert({value : "244", b1 : true, ..., b5000 : true, tfString : "TFFFFFFF...FFT"})

Could then query 1 simply with:

db.values.find({b1 : true, b5000 : true}, {value : 1})

And 2 using regex pattern matching:

db.values.find({tfString : /TFTTFFF/}, {value : 1})

Or positionally (find all the values with the string TFTTFFF at position 2023):

db.values.find({tfString: {$regex : "^.{2023}TFTTFFF"}}, {value : 1} )

Could use $substring and aggregations as well for grouping results I'd think.

Insert speed should be great in comparison to mySql innoDB (2M documents vs 2M * 5001 records), and you could query against a secondary if you setup a replicaset.

I can't see a way to index it other that the value, so you might have to contend with pretty slow queries.

I did some playing on my macbook air with an SSD and 4GB, running a bunch of stuff like Chrome with about 16 tabs open, gotomypc, etc, so it isn't really performant currently. Used mongo 2.2.2 (need to upgrade!).

From mongo shell I inserted 100K docs with a value field (in practice you'd prob put that to _id) and then queried and did .explain() to show perf.

var values = db.values;
for (var docNo = 0; docNo<100000;docNo++) {
    var newdoc = {};
    newdoc.value = docNo;
    var tfStr = "";
    for (var colNo = 0; colNo<5000;colNo++){
        var tOrF = Math.floor(Math.random() * (2 - 1 + 1)) + 1 == 1 ? "T" : "F";
        newdoc[colNo] = (tOrF == ("T"));
        tfStr = tfStr + tOrF;
    }
    newdoc.tfString = tfStr;
    values.insert(newdoc);
}

> db.values.count()
100000
> db.values.find({tfString : {$regex : "^.{4356}TFTFTFTF"}}, {value : 1}).explain()
{
    "cursor" : "BasicCursor",
    "isMultiKey" : false,
    "n" : 423,
    "nscannedObjects" : 100000,
    "nscanned" : 100000,
    "nscannedObjectsAllPlans" : 100000,
    "nscannedAllPlans" : 100000,
    "scanAndOrder" : false,
    "indexOnly" : false,
    "nYields" : 3,
    "nChunkSkips" : 0,
    "millis" : 49667,
    "indexBounds" : {

    },
    "server" : "NsAir.local:27017"
}

50 odd seconds for 423 matches. But check the query, nice and easy to query any combo at any position.

Would you get better/same perf and less hassle using mySQL binary field and working out a regex for that? Possibly. However, I think the querying in MongoDb might be significantly easier, the inserting if the dataset is live will be simpler and easier to handle, and you do not have a limitation on the no of columns/fields up to 16MB per doc.

Answer 4

We have in production Firebird database with table:

~560K rows 
with ~20600 bool parameters stored in 321 bigint columns.

Where the logic is Bitnumber/64 gives you coulmn while bitnumber (remainder) 64 gives you bitnumber in the current column(bigint).

I`ve just ran the query agaist this table

select id form ourtable
where  bin_and(N125,2048)!=0 and bin_and(N125,1024)=0 and bin_and(N125,512)=0;

It took ~120 seconds for first time execution. Since firebird caches the database pages the subsequent queries with (N200,N20 and so on) took several seconds. I` dont know how MySql would perform with large number of columns but you can give a try.