Need some input related to SQLite or alternative methods.

Hi all,

This is not urgent, but, I am looking for ideas. So I was basically writing a table [ID as rowID, K as integer (4B uint, although that's not defined in SQLite) ] with like One billion rows in SQLite. The ID is sparse and inserted in increasing order. K is simply incremented by one per row insert.

Now I am running into delima. Writing one billion rows is slow when I already used their recommended Prepare one time, and then, Bind-Step-Reset routine.

I need rowID index for fast Min, Max, and access.

============

So, I was thinking just write 4bytes per row into a flat file instead since it is faster this way. I would just write junk for the ID that is not interesting. However, that would use tons of HDD space as ID is sparse. We are looking at ID ranged from 0 to 40Billion where there are One Billion of them are inserted into the table. If I just waste spaces, for uncessacry IDs, I would be writing a 40Billion * 4B Uint file. That's just insane.

Is there any alternatives? I liked the SQLite rowID performance, but, insertion is too slow. Any thought?

 Thank you.

1) Store your IDs sequentially in a flat file as 64-bit ints.

2) ??? (something invoving a search/index algorithm)

3) calculate the result's offset from the start of the file to get K

@magicalclick:

Can you preinsert the rows ahead of time? If so, when you actually get the data you intend to store, do an update instead of insert.

@magicalclick:

ID, K, 4B - why would writing that to a flat file be larger that what SQLite would use?  It can't be.  Your not having to store any of the overhead related to the engine.

Since your records are inserted in order by both ID and K you could store in a flat file and be able to read back fairly well, although you didn't mention much about the requirements of who/what needs to get this data that has been stored.  If there is a need to retrieve data records out in relation to other data then taking the flat file route will tend to force the other data being related to be in a similar storage mechanism (i.e. less friction in the relation).  We need to know more ...

What will the 1 billion records be used for once they are stored, regardless of SQLite or flat file?  Fast Min/Max for what (the first record is the min, the last record is the max, so there must be more to this).

What time duration targets for storing the 1 billion records must you beat?

Have you considered a binary NTFS Sparse File?

That way you could store your data at a calculated offset [ID] into a file that you could quickly seek to to read back, but would not need to consume all the disk space for the IDs that do not have any associated data [K].

Using a database engine to store such massive quantities of basic integers seems to be the wrong tool for the job.

21 hours ago, magicalclick wrote

Hi all,

This is not urgent, but, I am looking for ideas. So I was basically writing a table [ID as rowID, K as integer (4B uint, although that's not defined in SQLite) ] with like One billion rows in SQLite. The ID is sparse and inserted in increasing order. K is simply incremented by one per row insert.

Now I am running into delima. Writing one billion rows is slow when I already used their recommended Prepare one time, and then, Bind-Step-Reset routine.

I need rowID index for fast Min, Max, and access.

============

So, I was thinking just write 4bytes per row into a flat file instead since it is faster this way. I would just write junk for the ID that is not interesting. However, that would use tons of HDD space as ID is sparse. We are looking at ID ranged from 0 to 40Billion where there are One Billion of them are inserted into the table. If I just waste spaces, for uncessacry IDs, I would be writing a 40Billion * 4B Uint file. That's just insane.

Is there any alternatives? I liked the SQLite rowID performance, but, insertion is too slow. Any thought?

 Thank you.

write the values as binary to a binary file,  size of the file / 4 gives the total number of values in the file and the max row #

seek() and tell() to do random access to an y value by doing a bit of math to find the start location of a number in the file (again using the size of 4 bytes to compute that)

you can if needed create a file with empty data to make "adding" data faster, if so you need a small tracker file that stores the location of the last valid item.

21 hours ago, magicalclick wrote

 So, I was thinking just write 4bytes per row into a flat file instead since it is faster this way. I would just write junk for the ID that is not interesting. However, that would use tons of HDD space as ID is sparse. We are looking at ID ranged from 0 to 40Billion where there are One Billion of them are inserted into the table. If I just waste spaces, for uncessacry IDs, I would be writing a 40Billion * 4B Uint file. That's just insane.

This part I don't understand. Why have the ID in the first place then? And what is the point of "K"? Are you storing it simply to flag whether or not the number was used?.

Hi all, sorry for the confusion.

Basically I wanted a simular table [ID as ulong rowID, K as uint]. And I would perform queries like. SELECT MIN(ID) FROM TALBE1 WHERE ID >= A AND ID <=B. I would do the another query of MAX(ID).

If I didn't index the ID row, I would ended up doing table scan or flat file scan to find the first ID that is >= A and still <= B.

I wouldn't do update way because the ID to be inserted is considering random sampling from 40Billion IDs, except the ID are inserted monotomically increasing. So, writing them into flat file is pretty easy and fast.

SQLite/TAble approach has good lookup performance for my select query and didn't waste a lot of HDD. But, the insert is slow.

=========================================

The NTFS Sparse File seems to be be good idea, but, how would I know which is the first larger ID possition inside real data areas when A is in the holes? Basically I want to find the first larger data area from the holes. Can that be done?

=========================================

Or is there also other ways as well?

I probably can remove K later, but, please assume I need K for now.

Thank you.

If you're just checking to see of some integer value is being used or not, you can create a bit mask file. For 40 billion possibilities, you would need only 5 GB of disk space.

You can find the max by reading backwards from the end of the file until you read a non-zero bit.

@cbae:

thank you, what about the K value? I kind of need to know how many 1s accumulatively at that index. I already spend a lot of time reading backwards doing scan, so, it is best if I can compute K right away.

=======

BTW, I think the same can be avhived by NTFS Sparse File suggested by eddwo?

I am just afraid I would spend too much time on scaning the index. Although it is probably not bad either.

16 minutes ago, magicalclick wrote

@cbae:

thank you, what about the K value? I kind of need to know how many 1s accumulatively at that index. I already spend a lot of time reading backwards doing scan, so, it is best if I can compute K right away.

=======

BTW, I think the same can be avhived by NTFS Sparse File suggested by eddwo?

I am just afraid I would spend too much time on scaning the index. Although it is probably not bad either.

What purpose does the K value serve? If I'm reading your original post correctly, it's just an incrementing number from 1 to 1 billion that gives a sequence number to the ID as it's flagged as "used". Is that correct?

If so then you can create 2nd file that's sizeof(ID) * 1 billion in size. As the value of ID is flagged in the bit map, you write out the ID in the position corresponding to the value of K in the 2nd file. (Maybe call it an "index" file?)

IOW, if the ID = 403, and K = 1, you write "403" in the first position in the "index" file. If ID = 239 and K = 2, you write "239" in the second position in the index file. If ID = 1949 and K=1,000,000,000, you write out "1949" in the 1 billionth (last) position in the file.

The total size of all the data will be:

bitmap file: 40 billion / 8 bytes

"index" file: sizeof(ID) * 1 billion

@cbae:

Hello, thanks for the suggestion. The problem would be once you get the ID, you have to search ID in your index file, and finally return the indexFile.indexOf(ID), which is a linear operation.

Hi all, I think I have a fairly clear picture of what to do now.

I would use a bit string as cbae and other suggested. While I need to do linear search to get the next largest ID that has value of 1, I imagine the 1s are fairly uniformally distributed, so this linear operation is not too unstable.

Then, I would just count the 1s backward until I reach a check point. Probably like a runningTotal check point per 100 id values (for both flag as 1 and 0).

Thanks for the inputs. It is very helpful.