4

I'm going to run a bunch of simulations using an application I wrote in the near future, and I'm having trouble designing my database around this.

Here's how it works. Each simulation has 6 parameters that can vary, and each parameter has ~10 options. So we have about 1 million permutations of this to somehow store in the DB. The simplest way I can think is to have a column for each parameter, with an additional column for my primary key (ExperimentID). I could then access the parameters for a given experiment directly by doing a simple

SELECT * FROM Parameters WHERE ExperimentID = (givenID)

Each parameter will be stored in the DB as an int, which will be interpreted by my application as the necessary parameters at runtime.

A more complex, but I think faster, way to do it is to take advantage of the speed of binary shifting. Instead of storing the parameters directly, I'd store the information about each parameter in 4 bits of an unsigned int. I don't actually know how ints are stored (binary wise) in the DB, so that's the major hold up.

Any advice on what to do in this situation? Also, I don't yet have these columns, so if I decided to go with the first option, how would I fill a table with all of the permutations of a set of parameters?

4
  • what is the range of values for each of the 6 parameters? – Hannah Vernon Oct 2 '15 at 1:27
  • They go from 0 to 4, 0 to 7, and 0 to 9. – ijustlovemath Oct 2 '15 at 1:30
  • I'm attempting to setup a test bed - which sets are 0-4, which 0-7, and which are 0-9? – Hannah Vernon Oct 2 '15 at 1:41
  • The order doesn't really matter. Let's call A and B 0-4, C and D 0-7, E and F 0-9. – ijustlovemath Oct 2 '15 at 1:43
8

Why do you think that obscuring real data into a bit-masked field will be faster? You are only talking about 1 million rows and 24 bytes per row. That really isn't much, especially since you are only doing singleton / seek operations.

A better optimization would be to use TINYINT fields (range of 0 - 255 ; byte in .NET). Using TINYINT instead of INT (and assuming a FILLFACTOR** of 100) would result in:

  • the table would effectively be 10 MB instead of 28 MB (1 byte per each of 6 fields + 4 bytes for the INT [ID] field = 10 bytes per row).
  • you would get 806 rows per 8060-byte data page instead of 287 with six INT fields

The main efficiencies gained here are:

  • quicker initial lookup time for 2244 records. How so? With 1 million rows, 287 rows per 8k data page equates to 3484 pages, while 806 rows per 8k data page equates to only 1240 pages. Once a page is read to get the first row's values, it should stay in the buffer pool (i.e. memory) for subsequent lookups (i.e. the other rows on that same data page). More rows per page means fewer pages to read from disk--2244 fewer pages in this case. But once all of the pages are in the buffer pool, the lookups should be the same speed whether it was 806 rows or 287 rows per page. So, 2244 lookup operations out of the 1 million are slightly faster. Certainly not bad since there was no cost associated with this optimization, but just wanted it to be put into perspective.

  • less memory required to hold the entire table in memory. this will make it more likely to remain in memory.

Lastly, it is definitely possible to squeeze this data into an even smaller representation. But at this point it is 10 bytes per row with no complication added to the processing / coding and all of the values are human readable. There isn't a lot of room to go below 10 bytes per row, but even if it got down to 7 bytes per row (INT IDENTITY + 3 bytes for Parameters, which should be the minimum required to handle these ranges), I am not sure the added complexity would be worth it (i.e. diseconomies of scale).


CREATE TABLE dbo.Experiment
(
  ExperimentID INT NOT NULL IDENTITY(1, 1),
  Parameter1  TINYINT NOT NULL,
  Parameter2  TINYINT NOT NULL,
  Parameter3  TINYINT NOT NULL,
  Parameter4  TINYINT NOT NULL,
  Parameter5  TINYINT NOT NULL,
  Parameter6  TINYINT NOT NULL,
  CONSTRAINT [PK_Experiment] PRIMARY KEY (ExperimentID) WITH (FILLFACTOR = 100) ON [Tables]
)
ON [Tables];

And you can populate it using the following (which assumes two parameters of 0 - 4, two parameters of 0 - 7, and two parameters of 0 - 9 ; based on comments on the Question):

;WITH Five(num) AS
(
  SELECT 0 UNION ALL SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4
), Eight(num) AS
(
  SELECT 0 UNION ALL SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4
  UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7
), Ten(num) AS
(
  SELECT 0 UNION ALL SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4
  UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL SELECT 8
  UNION ALL SELECT 9
)
--INSERT INTO dbo.Experiment
--     (Parameter1, Parameter2, Parameter3, Parameter4, Parameter5, Parameter6)
SELECT f1.[num] AS [Parameter1],
       f2.[num] AS [Parameter2],
       e1.[num] AS [Parameter3],
       e2.[num] AS [Parameter4],
       t1.[num] AS [Parameter5],
       t2.[num] AS [Parameter6]
FROM   Five f1
CROSS JOIN Five f2
CROSS JOIN Eight e1
CROSS JOIN Eight e2
CROSS JOIN Ten t1
CROSS JOIN Ten t2;

The query above only generates 160k permutations, not 1 million, again based on comments on the Question. But it should be should be fairly easy to figure out how to adjust it for different ranges of values for any combination of the six parameters.


** FILLFACTOR: Rows are stored on data pages that are roughly 8060 bytes. Smaller rows = more rows that fit into that fixed size container. FILLFACTOR is how much space to reserve (when creating / rebuilding an index) for new rows or updates that take up more space due to variable length fields requiring more bytes for the new version of the row. A value of 100 means that there is no reserved space, that 100% of the 8060 should be taken up by current rows. In this scenario there are only fixed length fields and no out of sequence inserts.

3
  • srutzky, I have one final question for you. How do I enforce an order in which these records increment? I want them to increment in this order: First Parameter1, then Parameter2, Parameter3, etc. such that ID 1 is (0,0,0,0,0,0), ID 2 is (1,0,0,0,0,0), ID 6 is (0,1,0,0,0,0), etc. I've tried using ORDER BY after doing the cross Join, but this doesn't seem to enforce any kind of order – ijustlovemath Oct 2 '15 at 17:03
  • I am not sure about that. You would have to find a way to combine them into a single unit. I am not sure if a bit-wise type approach would work, though, for that particular ordering. – Solomon Rutzky Oct 2 '15 at 17:46
  • 1
    Thanks, I'm going to post my queries + that question into a new question on this forum to see if it's possible. – ijustlovemath Oct 2 '15 at 17:57
1

I like the idea of storing the test parameters in a single INT column. With that in mind, I've created the following test-bed which may help explain how to create the table with the test parameters, and how to extract those values later.

First we create 3 tables we'll use to construct the 0-4, 0-7, and 0-9 sets.

CREATE TABLE dbo.numbers4 
(
    num INT NOT NULL
);
CREATE TABLE dbo.numbers7 
(
    num INT NOT NULL
);
CREATE TABLE dbo.numbers9 
(
    num INT NOT NULL
);

Here, we populate the tables:

INSERT INTO dbo.numbers4 (num)
SELECT TOP(5) (ROW_NUMBER() OVER (ORDER BY o.name)) - 1
FROM syscolumns o;

INSERT INTO dbo.numbers7 (num)
SELECT TOP(8) (ROW_NUMBER() OVER (ORDER BY o.name)) - 1
FROM syscolumns o;

INSERT INTO dbo.numbers9 (num)
SELECT TOP(10) (ROW_NUMBER() OVER (ORDER BY o.name)) - 1
FROM syscolumns o;

This is the table we'll use to store the bit-shifted INT values combining the 6-sets of numbers:

CREATE TABLE dbo.t
(
    TestID INT NOT NULL
        CONSTRAINT PK_t
        PRIMARY KEY CLUSTERED
        IDENTITY(1,1)
    , TestParms INT NOT NULL
);

And here we populate that table from the 3 temporary tables above:

DECLARE @p1 INT;
DECLARE @p2 INT;
DECLARE @p3 INT;
DECLARE @p4 INT;
DECLARE @p5 INT;
DECLARE @p6 INT;

SET @p1 = 0x1;
SET @p2 = 0x10;
SET @p3 = 0x100;
SET @p4 = 0x1000;
SET @p5 = 0x10000;
SET @p6 = 0x100000;

TRUNCATE TABLE dbo.t;

INSERT INTO dbo.t (TestParms)
SELECT (n1.num
    + n2.num * @p2
    + n3.num * @p3
    + n4.num * @p4
    + n5.num * @p5
    + n6.num * @p6)
FROM dbo.numbers4 n1 
    , dbo.numbers4 n2
    , dbo.numbers7 n3
    , dbo.numbers7 n4
    , dbo.numbers9 n5
    , dbo.numbers9 n6;

This next part shows how to extract the numbers into 6 different sets from the single INT column:

DECLARE @p1 INT;
DECLARE @p2 INT;
DECLARE @p3 INT;
DECLARE @p4 INT;
DECLARE @p5 INT;
DECLARE @p6 INT;

SET @p1 = 0xF;
SET @p2 = 0xFF;
SET @p3 = 0xFFF;
SET @p4 = 0xFFFF;
SET @p5 = 0xFFFFF;
SET @p6 = 0xFFFFFF;

DECLARE @p1_shift INT;
DECLARE @p2_shift INT;
DECLARE @p3_shift INT;
DECLARE @p4_shift INT;
DECLARE @p5_shift INT;
DECLARE @p6_shift INT;

SET @p1_shift = 0x1;
SET @p2_shift = 0x10;
SET @p3_shift = 0x100;
SET @p4_shift = 0x1000;
SET @p5_shift = 0x10000;
SET @p6_shift = 0x100000;

SELECT t.TestID
    , Param1 = (t.TestParms & @p1)
    , Param2 = (t.TestParms & @p2) / @p2_shift
    , Param3 = (t.TestParms & @p3) / @p3_shift
    , Param4 = (t.TestParms & @p4) / @p4_shift
    , Param5 = (t.TestParms & @p5) / @p5_shift
    , Param6 = (t.TestParms & @p6) / @p6_shift
FROM dbo.t t;

Since there are only 160,000 rows (the number of permutations you suggest), this table requires only 2.6MB of storage space (approximately 330 data-pages), including the IDENTITY column, which may or may not be required.

A sample of the results of the select above are:

enter image description here

7
  • You could further reduce the size by storing the values in 3 TINYINT fields since you are only using 3 of the 4 bytes of the INT. Each TINYINT would represent 2 of the parameters (1 and 2, 3 and 4, and 5 and 6). And each value only needs the no-shift and 0x10 shift. Also, the ID field is needed since if there was no need to reference the values again, then no table was needed in the first place and the query to generate the values to populate the table would have sufficed. Right? – Solomon Rutzky Oct 2 '15 at 14:54
  • Agreed, @srutzky - you could use TINYINT fields, as you've said. However, the design I've proposed allows the OP to easily increase the range of values for each of the 6 sets. Also, agreed about the need for the ID field; unless you were using the entire set each time you access the table. – Hannah Vernon Oct 2 '15 at 15:07
  • You could increase beyond 0 - 15 by adjusting the shifts to 0x20, 0x200, etc? – Solomon Rutzky Oct 2 '15 at 15:22
  • I'm not certain I follow you, but if you wanted to have values up to 255, I would do it by making the multipliers like 0x1, 0x100, 0x10000, etc. The logical AND values (the &) would be 0xFF, 0xFF00, 0xFF0000, etc. – Hannah Vernon Oct 2 '15 at 15:38
  • 1
    For 0-64, you could multiply by 0x100 to store, then & with 0x3F00, and divide by 0x100 to retrieve. – Hannah Vernon Oct 2 '15 at 16:21

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.