Huh, that's actually kind of a worst case I didn't think about: Since you're doing a reverse table scan my "sequential access" detection doesn't kick in. If you do the same query but with a forward scan it should fetch roughly the same amount of data but only do like 5 HTTP requests since the request size doubles for every sequential access.
e.g.:
select country_code, long_name from wdi_country where rowid >= 164 order by rowid asc limit 100;
I solved a similar problem recently: given a stream of data, how should you choose packet size in an online way to minimize regret (a linear combination of spare capacity of last packet and total packets used).
Turns out doubling isn’t the best strategy. The optimal solution is actually to add a constant increment to packet size. How much depends on relative cost of the terms in the regret function.
> I’ve set the page size to 1 KiB for this database.
> That’s because I implemented a pre-fetching system that tries to detect access patterns through three separate virtual read heads and exponentially increases the request size for sequential reads.
> Since you're doing a reverse table scan my "sequential access" detection doesn't kick in.
You know, starting off with the default 4kB page size naturally adds some resistance to these kinds of failure cases. If the VFS isn't issuing many requests in parallel, I would think that setting up a page size near target_bandwidth * round_trip_time would be a better initial guess. 1kB would be appropriate for a pretty low latency-bandwidth product.
Not easily - Datasette is written in Python, so you could try running it in WebAssembly (like Mozilla did for Jupyter with https://hacks.mozilla.org/2019/03/iodide-an-experimental-too... ) but it would be enough work that it might be easier to reimplement a subset of Datasette directly in JavaScript.
Use Http Range (normally used for pausing and continuing large file downloads) to request specific byte ranges from the file. From there you can pull only what you need. With sql indexes it'll be very tiny since the lookup is optimized. Of course if you select *, you're still going to pull the entire database locally.
TL;DR http, properly implemented, supports a ton more stuff than even many “web developers” are aware of, like… range requests, which are exactly what you’d think they’d be.
So assuming no country has a name longer than 98 characters and that all country codes are 2 characters, that is over 500% overhead? Are you missing a /s in your post?
Since random accesses across the internet are really slow, for this kind of fairly small table (where SQLite stores the row data inline within the B-Tree of the table) it basically fetches the whole content for each row - so even if you query only the long_name and country_code column, it will in fact fetch the data of all 29 columns in that table.
If you want it to fetch less data for querying a subset of columns, you could create create an index on those columns - then SQLite will do an COVERING INDEX scan and thus read only the necessary data (with the B-Tree itself and the start / end page alignment being the only overhead).
Have you actually read the article? SQLite is unmodified, and thinks it runs on a virtual file system, which fetches file chunks via HTTP range headers.
It's REALLY impressive that you only need to read 54 KB out of 700 MB, to fetch the records.
> sql.js only allows you to create and read from databases that are fully in memory though - so I implemented a virtual file system that fetches chunks of the database with HTTP Range requests when SQLite tries to read from the filesystem: sql.js-httpvfs. From SQLite’s perspective, it just looks like it’s living on a normal computer with an empty filesystem except for a file called /wdi.sqlite3 that it can read from.
From this paragraph it should be pretty clear that it's actually a great result. The database will obviously need to read more data than it presents, so more is fetched.
Man you are a frickin genius, seriously. like how you put all this together all the depth of knowledge of different topics this would require the low level and the high level and the way you explain it simply confidently and with impact. Your work is really an inspiration. You computer scienced the sheet out of this thing.
this achievement, and this blog post, to me is on par with blog posts that you would see from a major company where they solve some significant business critical technical challenge in-house. for example: the GitHub blog post about how they created their spinning globe of commits on their homepage, or a Netflix blog post of how they optimized their Network infrastructure to serve so many customers.
your work is truly incredible. You're next level of next level.
Thank you, I really appreciate it. It's pretty fun to do this kind of thing for yourself, but it's really rewarding to be able to share it with other people.
If you're pulling a single TCP stream across a crowded network, you get maybe 1/40th of the available bandwidth. If you do four range requests instead, you might see >3/40th of the bandwidth.
This place we were contracting at, the managers were widely rumored to stream sports games at their desks, and our release cycle happened to fall on a game day. My poor coworker was downloading our installer every week, and the ETA was over 40 minutes. "Are you using DTA?" "No, what's that?" <fiddle fiddle> ETA: 12 minutes.
12 minute pauses in the middle of a manual process are a lot easier to stomach than 40 minutes. Especially if something goes wrong and you have to do it twice.
I remember putting together a sloppy http range implementation that initially only supported single ranges, it had quite the explosive effect on adobe reader when it didn't get the expected response to its multi-range requests :)
nginx enables it by default. Another ingenious use of range request is zsync, it allows you to diff compressed binaries on a remote with local ones, so that you only have to download what has changed on an update. AppImage uses this
This is easily the most clever web programming hack I’ve seen this year. Bravo. I had seen this used for video or audio of course but it never occurred to me you could use it for databases. There are probably a ton of other formats this is good for too.
This is pretty much exactly what we do to serve aerial/satellite imagery maps.
We convert the imagery into Cloud optimised geo tiffs and store them in S3 https://www.cogeo.org/ then the browser can request the tiles directly from S3.
I believe this is protomaps approach: re-encode the mbtiles (sqlite-based ) format in to something that can be requested with a http range request and thus served from a single dumb webserver that doesn't need to understand sqlite or mbtiles parsing
Yeah, that was one of the inspirations for this. That one does not work in the browser though, would be a good project to do that same thing but with sqlite in wasm and integrated with WebTorrent instead of a native torrent program.
I actually did also implement a similar thing fetching data on demand from WebTorrent (and in turn helping to host the data yourself by being on the website): https://phiresky.github.io/tv-show-ratings/ That uses a protobufs split into a hashmap instead of SQLite though.
Sort of. Access had a "Forms" feature that let you create basic GUIs on top of your database. Also, the OP's project is (currently) only providing a read-only view of the SQLite database. Adding write support is possible but will be far less impressive to the HN crowd because SQLITE_BUSY will rear its ugly head ;-)
I'm curious, in what manner could this method speed up Next.js builds? That's all done locally, which negates the effect of HTTP range requests, right?
I'm guessing they mean rather than build a static Next site that generates 10k+ pages (or whatever large means in the given context), it instead creates one page that just queries the data from the client.
I have one Next static site that has about 20k pages and takes about 20 minutes to build and deploy. I think that's an acceptable build time. But I do know of other people around the net who have mentioned having sites with 20k-ish pages taking an hour+ to build. For them I could see the desire to try this sqlite trick.
As everyone else has been saying, this is amazing work. It sounds like the biggest issue with loading the page is the initial sql.js download - it's about 1.2MB, is that right?
Might it be feasible to easily strip down SQLite so that it only compiles the parts for read-only use? The browser version is obviously somewhat read-only but that's because of the sandbox. I'm talking about excluding the code for CREATE, UPDATE, INSERT and everything else which is just for writing. The aim here would be to produce a significantly smaller WASM binary.
I'm guessing that the answer is no, there's no easy way of doing this without significant rewrites of SQLite's core, but... I can't be the only one to think of this, surely?
The actual transferred data for the sqlite code should only be 550kB (gzip compression).
Stripping out the write parts is a good idea. SQLite actually has a set of compile time flags to omit features [1]. I just tried enabling as many of those as possible, but it didn't seem to reduce wasm size much, though I might be doing something wrong. There's also no easy flags to disable CREATE / UPDATE / INSERT .
I'd be curious whether there's any changes which could be made in the file format to optimize for read-only usage. The SQLite format probably has some features which aren't needed in this context -- information about free pages and autoincrement counters isn't relevant in a read-only file, for instance.
I think it wouldn't change much - SQLite is already pretty optimized towards reads, for example a write always replaces a whole page and locks the whole DB. The free pages can easily be removed by doing VACUUM beforehand which should be done anyways to balance the b-trees.
The storage of SQLite is already really efficient, for example integers are always stored as varints so small ones only take a byte. The only thing I think could maybe be improved for this use case is changing the structure of the b-tree to be more columnar - since right now all the data from different columns is intermingled with the btree structure itself, querying a subset of columns has a high overhead.
Sounds feasible to me. Either by replacing all those functions on the C side with empty shells or maybe even with wasm-opt ( but probably the OP has already used it removed all garbage collectible paths.)
This is fantastically creative. And the author does a great job of starting out by describing why this is useful.
And then using SQLite to insert and update DOM elements? Holy cow, icing on the cake. Unlike the first part, there’s no explanation of why you’d want to do that. But by that point I was so drawn in that I didn’t care and was just enjoying the ride.
Yeaah I felt like at that point the article was already long enough so I didn't bother describing the DOM part too much - even though I spent more time implementing that than I did implementing the rest ;)
Basically SQLite has a virtual table mechanism [1] where you have to define a few functions that figure out how to scan your "fake" table / which indices to use and then how to read / write the actual data. I hook into this mechanism and redirect the request to DOM functions like querySelector() etc. Then there's the issue about SQLite being fully synchronous, but I have to run it in a WebWorker - and the WebWorker can't actually access the DOM and it can only communicate asynchronously with the main thread... So I have to do some weird stuff with SharedArrayBuffer and Atomics.wait to make that work [2].
"But by that point I was so drawn in that I didn’t care and was just enjoying the ride."
:-) There a high amount of SQLite content/articles/blogs on the web that can provide this effect. SQLite is to programmers like the stars are to astronomers. A wonder.
Amazing, especially - for me - that the FTS5 full-text search just works. Longer term, I am if it were possible to split the DB code into read and write parts and cross-compile only read part for delivery to the browser.
Lunr needs the full index on client though, right?
Being able to use fts-5 without the penalty of having to pull down the whole index make it work much better at larger scales, even with the penalty of additional network requests.
Time to create the index for lunr limits the size of the data-set that can be used. If you have a lot of tiny documents, then it is more practical to scan the documents directly, rather than using the lunr index.
I wrote a similar thing in Rust for a Factorio mod manager. Mods are hosted on the remote HTTP server as ZIP files, and the mod manager needs a single `info.json` file from the ZIP for the mod metadata. So the mod manager avoids downloading the whole mod and then unpacking it by building a file abstraction that uses HTTP range queries to download just the chunks it needs. For ZIP files the directory is stored at the end at an unknown offset, so the read pattern is to gradually seek backwards from the end until you find the start of the directory, then find the file entry, then seek and read the file.
I didn't fiddle with the window sizes like the submitted article (the chunk is fixed to 8KiB), but I did optimize it so that reading chunk N+1 of the file reused the response reader of chunk N rather than make a new request. Furthermore I keep an LRU cache of only the last three chunks in memory, because the ZIP files are each only read once.
Modeling the DOM in SQL... Further evidence that anything we can imagine has some stable representation in third normal form. Is it fast? Maybe not. But is it correct? Provably.
There was a group that rewrote the Chromium DOM itself in a data oriented design (which learns from database design and sort of applies to cache utilization and locality) and got a 6X speedup in some places:
This paper is basically what we do, except we have a big container type, aptly named "Domain.cs". Inside, you will find a public List<T> of every type. We decided to emulate SQL throughout the vertical (i.e. each List is a table) in order to make mapping to SQL a trivial affair. None of our Domain types contains any complex type as a property. Everything can go 1:1 to SQL. We use LINQ (or SQL) to produce projections as appropriate.
There isn't actually just 1 big domain instance either. It's more like one per user session, and then a global instance.
The impact this had on reducing complexity and bugs is incredible. I haven't seen a null ref exception in a long time. Also, being able to dump your entire universe to disk by serializing a single object is really nice.
In a similar vein, I've mentioned this before, but if you're doing Python stuff, you can use the apsw package (not the one in PyPi, though) to write a VFS layer that SQLite will use to read the database.
I've used this for the same basic idea as this article, only letting me store SQLite databases in AWS's S3 that I can access with AWS APIs so they don't need to be public. It works well, though it's absolutely not for every use case, the overhead is considerable.
I even used it once to read SQLite database files in a zip file stored in S3 without having any local storage to use. Not one of my prouder moments, but hey, I coded my way out of the corner someone else designed for me.
Once you wrap your head around how you need to pass parameters to the helper, it's really straightforward, you just need to implement the xOpen and xRead calls.
In the genomics world, Tabix indices enables similar use cases. An ordered TSV file is compressed in chunks (bgzip) and a Tabix index created to allow range based access by mapping from the index -> chunk. This allows a browser based genome browser zoomed into a section of the genome to fetch information from a multi gigabyte file.
Honestly I think Tabix's bgzipped TSV is one of the less hokey bioinformatics formats, at least compared to the various custom binary formats floating around.
For web browser based genome browsers I suspect this (very cool!) sqlite hack would require many more http requests.
TA was clear - there's no way to write, since static file hosting doesn't support dynamic write to begin with.
However, I imagine a service to support your scenario could be written in a standard back-end server language like Go or JS. The challenges involved would be much greater, however -- how to handle concurrency in particular. I suspect one would do better to just run PostgreSQL behind a web API.
That's basically re-inventing the Database but on the client side. We have gone a long way but we are closer to having the server side just as a data store.
Apart from the genius of the author (conceiving a sequence of relatively understandable steps that unlock a potentially huge area), this highlights how efficient a SQLite can be in terms of slow resource usage.
Over the last few months I tried to think of a clever way to set up a legacy site for a dictionary that I serve on a VM just because I also need to run sqlite. Since I want to make sure it'll run for longer than me paying for the VM this is the best possible solution. At some point no more updates will happen and it's going to be a static website. So bundling it like this is incredible. I can run multiple backups on different hosts with no additional costs.
If you just do an occasional key/value lookup, you don't need 1.2 MiB of WebAssembly. [1] That might already exceed your total database size.
I'd solve it via sharding: divide the database into N pieces via range- or hash-sharding. [1] Choose an N that's large enough for each piece to be reasonably small. When you look up a key, fetch the shard of interest.
You can put each piece into separate files (a little simpler to code, and most static servers will use pre-gzipped files for "Content-Encoding: gzip requests" easily, but you waste more disk space due to internal fragmentation) or one file (with range serving and an index of the byte range offset for each piece).
The format for each piece can be anything, eg json (simple) or an sstable-like format (more efficient). [3]
This is really cool! I wonder what the restrictions are and if we would ever be able to write to a SQLite db like this in the future. This could push more to the front end without needing to write apis.
The main restriction is that the DB really needs well fitting indexes, otherwise querying is really slow and fetches a lot of data.
Regarding writing:
You could of course implement a writing API with POST requests for changing pages of the database - but then you would lose most of the benefits of this (not requiring any special kind of server).
I also thought about implementing a kind of overlay filesystem, where chunks that are written to the file are stored in a local storage so the modified data is available locally while still reading everything else from the remote database.
Interestingly in SQLite that's already exactly what the WAL mode does: It's a second file next to the database that's just a set of pages that are overlaid over the main file when read queries happen - which allows concurrent readers and writers since the database itself isn't in an undefined state even when write transactions are happening.
So you could enable WAL mode and disable WAL auto checkpointing, then you get a downloadable WAL file that can be read by normal SQLite and written back to the main file. It would be neat, but I'm not sure what the actual use case would be ;)
> I also thought about implementing a kind of overlay filesystem, where chunks that are written to the file are stored in a local storage so the modified data is available locally while still reading everything else from the remote database.
If ever the intent were to involve eventually persisting those changes, then it would be worthwhile looking at remoteStorage, which works like this.
> I also thought about implementing a kind of overlay filesystem, where chunks that are written to the file are stored in a local storage so the modified data is available locally while still reading everything else from the remote database.
Perhaps adding IPFS to the mix for persisting data would be interesting, I'm sure there are use cases in peer to peer applications. Anyway, amazing innovation thank you for writing this :)
Seems like it might be possible to add WebRTC(or some other peer-based live system, I don't know the performance characteristics of WebRTC) to get realtime writes. Those edits would then be added to the WAL, and every say, 10 minutes anyone who has been active for 10 minutes could checkpoint and push the changes to github.
It's slightly more centralized than perfect, but man do you get a lot for a little.
Since you can do static hosting from a git repo, I wonder if you could directly push your changes to your git repo and have your CI/CD solution just deploy it instead?
There has to be a git.js implementation out there and you could move the DB to it's own repo and create an https access token (for Github)... the issue there is that someone could use that token to commit whatever to your database repo.
This is both a clever hack and a brilliant solution. But it also worries me a bit. Mostly because I've seen a lot of Visual Basic + MS Access solutions. They work fine on a single computer, but they you put a database on a network share to be able to share it between a few computers and the performance is often horrendous. If you're doing a lot of data processing it's often best to do it as close to the data as possible.
But as always, it's seldom the tools, but the right tool used for the wrong usecase that is the problem.
This is an really awesome idea! I have a plan for a static-ish site (updated daily) that I was going to use sqlite for anyway, but server side. I will definitely look into this approach instead!
>>> From SQLite’s perspective, it just looks like it’s living on a normal computer with an empty filesystem except for a file called /wdi.sqlite3 that it can read from.
Beyond static hosting : Now imagine also implementing a virtual file system that SENDS chunks of the database with HTTP Range requests when SQLite tries to write from the filesystem
Or more generally: I predict a WASI implementation which will treat ANY server resource as a virtual file, replacing REST.
First of all, this is a very cool web hack, I like it very much.
I have a question. It's a 668.8MB database file. What does actually happen if the query has to scan 300 mb before finding the right answer? Wouldn't it be better to do the work up front and deliver the answers as static json files? Sure you loose the flexibility of dynamic queries, but do you really have that flexibility in non trivial cases (e.g. 300 mb search)?
Solution works really well to databases which will not be updated frequently, like a standalone site.
Although one should be aware of one very important git behavior - git does not diff binary files (like SQLite dbs). That means 2 things:
1. Each db update will generate a new file in git, maintaining the whole old file in history, instead of the diff in bytes. This will accumulate a lot of clutter in the repo
2. As git does not diff binaries, there is a very small risk of corruption (especially if you work in multiple OSs, because of CRLF)
Git does actually diff binaries and stores them very efficiently :) If you do a single small UPDATE in your db file git will only store the changed information.
It's just kinda slow, and for most binary files the effort git spends to try and compute deltas for binary files is useless - which is why it has a bad reputation for binary files.
Note that the diffs that git shows you are completely unrelated to the deltas it uses to compress it's database - which are always "binary deltas" and not line-based diffs.
Also I'm not sure why you mean that db corruption possibility has something to do with whether or not it stores diffs?
Minor nitpick: Git does not store diffs for any file format but always the full file for each version.
So it does not really matter that its binary (except for not being able to VIEW the diff, but I guess you could even implement a plugin for that) but just that it's a big file. Even a huge text file would be fully stored per version.
/edit: The sibling comments mentions that git can infact delta compress older commits for storage efficency. But my point was that git commits are not deltas but full snapshots.
I can't figure out exactly how it knows which chunk to download. Does it always download the whole index first? Or does it include it in the built JS file itself?
Both the index and table data are btrees. These are trees - the root node sits in some known location (offset) in the file, referenced by the file header and metadata. As SQLite traverses the tree, it encounters new descendents it would like to visit, presumably identified by their byte offset in the file, which is all needed for this VFS magic to issue a suitable range request.
- SQlite opens the file and reads 4kb worth of header -> range request for byte 0-4096
- headers/metadata refers to index table with root node at 8192kb
- user issues SELECT * from index WHERE name = 'foo'
- SQLite reads root node from the file (range request for 8192kb..)
- Root node indicates left branch covers 'foo'. Left branch node at address 12345kb
- Fetch left branch (range request for 12345kb)
- New node contains an index entry for 'foo', row 55 of data page at 919191kb
- SQLite reads data page (range request for 91919191kb..)
SQLite has runtime-pluggable VFS support, i.e. you give it a struct with functions for opening a file, reading some bytes, writing some bytes, synchronizing file contents, closing a file. This project provides such a VFS module, that, because it actually runs in the browser, performs HTTP requests to read data. Emscripten provides a way to run a mix of C/C++ code in the same environment as some JavaScript code inside the browser. The reason SQLite has this pluggable VFS support is to properly support embedded systems, different locking APIs, and things like database encryption.
That's part of SQLite. It has been optimised to reduce disk reads, because those can be slow on spinning hard drives. Coincidentally, this translates well into an optimised algorithm that minimises the amount of HTTP range requests to make.
The Hacker News demographic, mostly US and EU based, might be under appreciating how impactful this is because of CDNs. For anyone not in the continent of your central database, this means absurdly faster interactions for data visualization.
I moved from US to Brazil 3 years ago, and I still notice the latency when a site runs their backend only in one location. This cleaver solution makes interacting with the graph supper snappy even compared to enterprises that do have database servers in Brazil. Very impressive!
Hmm... Is it possible to use this with two seperate databases, one a remote read only and one a local writable DB that could be re-exported to a static file host? Having just glanced at the code it looks like you would have to load two seperate libraries, one from this project and one from the original sql.js
Super cool. I wonder if an approach like this could ever work for a writable database. I guess the issue is that you couldn't have fine grained access control without a whole lot of server side validation, at which point you might as well just run a regular database server.
This hack reminds me of Godel's hacking of an axiomatic mathematical system, to prove and plant his incompleteness theorem;
This is really a great hack: using a system in a unexpected and creative way for which it wan not originally deigned, but which is also very useful and nice.
Very clever. I wonder if there are databases optimised for this use case. I can imagine something that always requires indexes to do the queries and stores data in disk in ways to make it easy to fetch only the bits you need.
That would be equivalent to always putting your data in b-trees or other structures, according to the request patterns, without keeping the tables themselves. Sort of how you need to do that in Redis for any kind of sane request strategy other than key-value lookups.
Hm, yeah, I think a key-value store would be easier to implement. I haven't looked at redis for some time now, but last time I did, persistence was done through snapshotting and everything would really be loaded into memory at start time. So that wouldn't work for this use case, where all you can do is serve a static file.
But my question revolves around databases assuming that the disk they access is local or at least a fast network storage. I wonder if there are any databases optimized to access slow storage over low bandwidth, where you're really trying to optimize the amount of data read more than anything else.
Very clever! Keep in mind this is a read-only dataset with the really clever bit being the ability to scan through the dataset and support sqlite query syntax.
This certainly does look like an interesting solution, I'd be keen to try it myself. However, just in case you didn't already know about Lunr (https://lunrjs.com/), it is fairly commonly used to implement search on static websites.
yeah I have come across Lunr and maybe a couple of other things in my research and I think for blogging it'll work well. What I'm interested in finding out is what works for a larger static site, that won't require you to load the index up-front. I'm also curious about how this sqlite thing picks the correct range to load (haven't looked at the code) and what the worst case might be.
Yes the web server supports range requests. Yes it only returns 50kb.
But what mechanism is letting it scan to just those ranges in the binary file. Doesn't the file system make you seek to the starting block and then read from there?
The point is, while it looks very efficient, there might be a crap ton of IO going on for your little 50kb response.
EDIT: probably the webserver is doing an fseek(), and performance will vary based on file system impl. This is something I will need to benchmark.
I think you missed the main part: the dataset is not in memory. This is not SQLite-in-the-browser but using a virtual file system over HTTP. Neither of those alternatives do anything similar.
Same with those! They'll just grab the chunks they need (also with range requests) to do what you want from binary ROOT or (presumably, I haven't actually used jsfive) HDF5 files.
What is dangerous here? Wasm is more crippled in access than normal js. And js is simply in every web page these days. You can't make a static site hosting service and tell people not to use js, that would be very lame.
couldn't you just link the source code or show how to reproduce what you did? really? you're just showing everything about your work but NOTHING about how to reproduce your work?? THERE IS NOTHING I HATE MORE THAN THESE KIND OF POSTS!!!
That said, all you need to query an SQLite database on the server side is a simple PHP script (as opposed to a running db server), and most static hosting providers offer PHP support.
This is certainly a clever hack. But it makes things cheaper and easier for the website owner at the expense of the users. This kind of solution will add to the bloat that is making the web unusable enough that people are seriously proposing a remote browser as a solution for desktop users (remember Mighty the other day?). We shouldn't let the cleverness distract us from this drawback.
Over high latency links this would be virtually unusable. Why not just download the entire database into memory over XHR on page load? SQLite databases of pure data usually aren’t over 10MB in size.
This particular demo page actually makes queries against an almost 700 MB large (fills one CD!) SQLite database. Because the amount of data read is almost negligible (few hundred kB), performance is limited by latency (as you say). However, high-latency links also tend to be slower, so downloading the entire database a-priori would almost always be much slower.
For example, on a 1 megabit/s link with 300 ms RTT, one example would take about 2 seconds for the data transfer itself while spending another 3 seconds or so on waiting. Downloading the entire file would take around an hour and a half.
For your 10 MB database, transferring it as a whole would take 80 seconds. Assuming this solution instead needs to read e.g. 250 kB (taking 2 seconds to transfer), it could still bounce around 250 times to the database before those 10 MB are fully downloaded. (This would be a really odd query, since it would only read on average two pages per read request)
Right but that is an artificially created demo by the author to justify the solution being presented (no offense). The question is how common are ~GB large SQLite databases in the real world relative to databases that are ~MB large?
In my experience SQLite databases of millions of rows of raw tabular data tend to compress very well into dozens of megabytes. Indeed SQLite is often touted as a file format for applications.
That is hilariously wrong for a lot of use cases. I will find this very handy for some SQLite databases I have that are several GBs in size. I am looking right now at using this contribution.
It’s not hilariously wrong or wrong at all that over high latency links this would be virtually unusable.
It’s certainly possible that people are using SQLite databases with sizes on the order of gigabytes but in my experience those are the exception not the rule.
And the article starts by mentioning that you can download the entire file if it's not too large. And then goes on to present a solution for larger files. What more answer to "Why not just download the entire database" do you expect?
Pop open the network pane in the browser tools and try running this SQL query for a demo of how clever this is:
It fetches just 54.2KB of new data (across 49 small HTTP requests) to return 100 results - from a statically hosted database file that's 668.8MB!
I have an animated GIF demo of this here: https://twitter.com/simonw/status/1388933800445452290
Huh, that's actually kind of a worst case I didn't think about: Since you're doing a reverse table scan my "sequential access" detection doesn't kick in. If you do the same query but with a forward scan it should fetch roughly the same amount of data but only do like 5 HTTP requests since the request size doubles for every sequential access.
e.g.:
select country_code, long_name from wdi_country where rowid >= 164 order by rowid asc limit 100;
I solved a similar problem recently: given a stream of data, how should you choose packet size in an online way to minimize regret (a linear combination of spare capacity of last packet and total packets used).
Turns out doubling isn’t the best strategy. The optimal solution is actually to add a constant increment to packet size. How much depends on relative cost of the terms in the regret function.
> I’ve set the page size to 1 KiB for this database.
> That’s because I implemented a pre-fetching system that tries to detect access patterns through three separate virtual read heads and exponentially increases the request size for sequential reads.
> Since you're doing a reverse table scan my "sequential access" detection doesn't kick in.
You know, starting off with the default 4kB page size naturally adds some resistance to these kinds of failure cases. If the VFS isn't issuing many requests in parallel, I would think that setting up a page size near target_bandwidth * round_trip_time would be a better initial guess. 1kB would be appropriate for a pretty low latency-bandwidth product.
4 replies →
Hah, I thought "in reverse order by ID" might be a stress test but I was still very impressed by how it performed!
Would it be possible to use a datasette frontend with this as a "backend" and statically host the whole thing?
Not easily - Datasette is written in Python, so you could try running it in WebAssembly (like Mozilla did for Jupyter with https://hacks.mozilla.org/2019/03/iodide-an-experimental-too... ) but it would be enough work that it might be easier to reimplement a subset of Datasette directly in JavaScript.
2 replies →
Amazing use of SQLite! Thanks!
mind blown. how is this possible???
Use Http Range (normally used for pausing and continuing large file downloads) to request specific byte ranges from the file. From there you can pull only what you need. With sql indexes it'll be very tiny since the lookup is optimized. Of course if you select *, you're still going to pull the entire database locally.
TL;DR http, properly implemented, supports a ton more stuff than even many “web developers” are aware of, like… range requests, which are exactly what you’d think they’d be.
8 replies →
So assuming no country has a name longer than 98 characters and that all country codes are 2 characters, that is over 500% overhead? Are you missing a /s in your post?
Since random accesses across the internet are really slow, for this kind of fairly small table (where SQLite stores the row data inline within the B-Tree of the table) it basically fetches the whole content for each row - so even if you query only the long_name and country_code column, it will in fact fetch the data of all 29 columns in that table.
If you want it to fetch less data for querying a subset of columns, you could create create an index on those columns - then SQLite will do an COVERING INDEX scan and thus read only the necessary data (with the B-Tree itself and the start / end page alignment being the only overhead).
1 reply →
Have you actually read the article? SQLite is unmodified, and thinks it runs on a virtual file system, which fetches file chunks via HTTP range headers.
It's REALLY impressive that you only need to read 54 KB out of 700 MB, to fetch the records.
14 replies →
> sql.js only allows you to create and read from databases that are fully in memory though - so I implemented a virtual file system that fetches chunks of the database with HTTP Range requests when SQLite tries to read from the filesystem: sql.js-httpvfs. From SQLite’s perspective, it just looks like it’s living on a normal computer with an empty filesystem except for a file called /wdi.sqlite3 that it can read from.
From this paragraph it should be pretty clear that it's actually a great result. The database will obviously need to read more data than it presents, so more is fetched.
This might be true.
But this approach lets you actually work out what the optimal size is:
gives: 6307
Or on average:
gives: 23
(Note that it doesn't seem possible to use aggregation functions with a limit clause)
The clever part here is only fetching 50KB out of 680MB.
Man you are a frickin genius, seriously. like how you put all this together all the depth of knowledge of different topics this would require the low level and the high level and the way you explain it simply confidently and with impact. Your work is really an inspiration. You computer scienced the sheet out of this thing.
this achievement, and this blog post, to me is on par with blog posts that you would see from a major company where they solve some significant business critical technical challenge in-house. for example: the GitHub blog post about how they created their spinning globe of commits on their homepage, or a Netflix blog post of how they optimized their Network infrastructure to serve so many customers.
your work is truly incredible. You're next level of next level.
Thank you, I really appreciate it. It's pretty fun to do this kind of thing for yourself, but it's really rewarding to be able to share it with other people.
have you thought of getting this to work with network replicated p2p sqlite js library? forgot what it was called.
also does this mean that static sites now can scale without relying on db???
what other implications and application do you see?
wonderful work!!!! please let me know how i can donate
The question I had is answered by this line of code:
I am a little surprised you can just do that. In https://github.com/phiresky/sql.js-httpvfs/blob/master/src/l...
Range headers are a pretty standard tools to e.g. continue interrupted downloads and similar.
Any well designed system, especially if it has static sources and is server cached should support it.
Surprisingly many web-frameworks don't support it out of the box, or don't support it well.
Either way gh-pages are static content and probably with some server side regional caches, so I'm not surprised it works.
Range headers are also how DownloadThemAll works.
If you're pulling a single TCP stream across a crowded network, you get maybe 1/40th of the available bandwidth. If you do four range requests instead, you might see >3/40th of the bandwidth.
This place we were contracting at, the managers were widely rumored to stream sports games at their desks, and our release cycle happened to fall on a game day. My poor coworker was downloading our installer every week, and the ETA was over 40 minutes. "Are you using DTA?" "No, what's that?" <fiddle fiddle> ETA: 12 minutes.
12 minute pauses in the middle of a manual process are a lot easier to stomach than 40 minutes. Especially if something goes wrong and you have to do it twice.
I've learnt about this by using https://www.biodalliance.org
It's an embedded genome viewer, you can just point it at a multigigabyte reference files and .seg files and it loads super quick
Here is direct link to GitHub with the usage: https://github.com/dasmoth/dalliance/search?q=bytes%3D%27&ty...
One of the heaviest users of range requests is (or was) the Adobe Acrobat PDF plugin.
Also .mp4 files. The format is designed for seekability, and browsers take advantage of this.
4 replies →
I remember putting together a sloppy http range implementation that initially only supported single ranges, it had quite the explosive effect on adobe reader when it didn't get the expected response to its multi-range requests :)
I'm surprised that works, iirc pdf isn't defined in order and can't be parsed streaming
5 replies →
Not all webservers support/enable it, so YMMV.
But as long as you're dealing with a known server that does, then gravy!
nginx enables it by default. Another ingenious use of range request is zsync, it allows you to diff compressed binaries on a remote with local ones, so that you only have to download what has changed on an update. AppImage uses this
> Not all webservers support/enable it
Could you provide an example of server that does not?
AFAIK, Range is supported by all major CDNs, so not supporting it in web server would be a death knell for it's real-world adoption.
2 replies →
I guess "all" that's needed for write would be a webdav server with support for PATCH x-update-range? :)
https://tools.ietf.org/html/rfc5789
https://sabre.io/dav/http-patch/
Unfortunately, solid, stand-alone webdav servers are harder to come by than decent http2/1.1 servers.
This is easily the most clever web programming hack I’ve seen this year. Bravo. I had seen this used for video or audio of course but it never occurred to me you could use it for databases. There are probably a ton of other formats this is good for too.
I wonder if this could be used to serve dynamic maps.
This is pretty much exactly what we do to serve aerial/satellite imagery maps.
We convert the imagery into Cloud optimised geo tiffs and store them in S3 https://www.cogeo.org/ then the browser can request the tiles directly from S3.
Even the big imagery providers are now storing their imagery as COGs, eg https://registry.opendata.aws/sentinel-2-l2a-cogs/
I believe this is protomaps approach: re-encode the mbtiles (sqlite-based ) format in to something that can be requested with a http range request and thus served from a single dumb webserver that doesn't need to understand sqlite or mbtiles parsing
2 replies →
The innovation here is getting sql.js to use http and range requests for file access rather than all being in memory.
I wonder when people using next.js will start using this for faster builds for larger static sites?
See also https://github.com/bittorrent/sqltorrent, same trick but using BitTorrent
Yeah, that was one of the inspirations for this. That one does not work in the browser though, would be a good project to do that same thing but with sqlite in wasm and integrated with WebTorrent instead of a native torrent program.
I actually did also implement a similar thing fetching data on demand from WebTorrent (and in turn helping to host the data yourself by being on the website): https://phiresky.github.io/tv-show-ratings/ That uses a protobufs split into a hashmap instead of SQLite though.
2 replies →
Would also be great to add (efficient) search to a static blog.
yea, sqlite FTS5 has been pretty amazing for quick search solutions (but I use english only)
Definitely. Just need to add a layer to the static site generator for it to populate the SQLite DB, right?
2 replies →
Microsoft Access Cloud Edition, basically?
Sort of. Access had a "Forms" feature that let you create basic GUIs on top of your database. Also, the OP's project is (currently) only providing a read-only view of the SQLite database. Adding write support is possible but will be far less impressive to the HN crowd because SQLITE_BUSY will rear its ugly head ;-)
1 reply →
I'm curious, in what manner could this method speed up Next.js builds? That's all done locally, which negates the effect of HTTP range requests, right?
I'm guessing they mean rather than build a static Next site that generates 10k+ pages (or whatever large means in the given context), it instead creates one page that just queries the data from the client.
I have one Next static site that has about 20k pages and takes about 20 minutes to build and deploy. I think that's an acceptable build time. But I do know of other people around the net who have mentioned having sites with 20k-ish pages taking an hour+ to build. For them I could see the desire to try this sqlite trick.
8 replies →
As everyone else has been saying, this is amazing work. It sounds like the biggest issue with loading the page is the initial sql.js download - it's about 1.2MB, is that right?
Might it be feasible to easily strip down SQLite so that it only compiles the parts for read-only use? The browser version is obviously somewhat read-only but that's because of the sandbox. I'm talking about excluding the code for CREATE, UPDATE, INSERT and everything else which is just for writing. The aim here would be to produce a significantly smaller WASM binary.
I'm guessing that the answer is no, there's no easy way of doing this without significant rewrites of SQLite's core, but... I can't be the only one to think of this, surely?
The actual transferred data for the sqlite code should only be 550kB (gzip compression).
Stripping out the write parts is a good idea. SQLite actually has a set of compile time flags to omit features [1]. I just tried enabling as many of those as possible, but it didn't seem to reduce wasm size much, though I might be doing something wrong. There's also no easy flags to disable CREATE / UPDATE / INSERT .
[1] https://www.sqlite.org/compile.html#omitfeatures
I smell a series of pull requests...
I'd be curious whether there's any changes which could be made in the file format to optimize for read-only usage. The SQLite format probably has some features which aren't needed in this context -- information about free pages and autoincrement counters isn't relevant in a read-only file, for instance.
I think it wouldn't change much - SQLite is already pretty optimized towards reads, for example a write always replaces a whole page and locks the whole DB. The free pages can easily be removed by doing VACUUM beforehand which should be done anyways to balance the b-trees.
The storage of SQLite is already really efficient, for example integers are always stored as varints so small ones only take a byte. The only thing I think could maybe be improved for this use case is changing the structure of the b-tree to be more columnar - since right now all the data from different columns is intermingled with the btree structure itself, querying a subset of columns has a high overhead.
Sounds feasible to me. Either by replacing all those functions on the C side with empty shells or maybe even with wasm-opt ( but probably the OP has already used it removed all garbage collectible paths.)
This is fantastically creative. And the author does a great job of starting out by describing why this is useful.
And then using SQLite to insert and update DOM elements? Holy cow, icing on the cake. Unlike the first part, there’s no explanation of why you’d want to do that. But by that point I was so drawn in that I didn’t care and was just enjoying the ride.
Yeaah I felt like at that point the article was already long enough so I didn't bother describing the DOM part too much - even though I spent more time implementing that than I did implementing the rest ;)
Basically SQLite has a virtual table mechanism [1] where you have to define a few functions that figure out how to scan your "fake" table / which indices to use and then how to read / write the actual data. I hook into this mechanism and redirect the request to DOM functions like querySelector() etc. Then there's the issue about SQLite being fully synchronous, but I have to run it in a WebWorker - and the WebWorker can't actually access the DOM and it can only communicate asynchronously with the main thread... So I have to do some weird stuff with SharedArrayBuffer and Atomics.wait to make that work [2].
[1] https://www.sqlite.org/vtab.html [2] https://github.com/phiresky/sql.js-httpvfs/blob/master/src/v...
"But by that point I was so drawn in that I didn’t care and was just enjoying the ride."
:-) There a high amount of SQLite content/articles/blogs on the web that can provide this effect. SQLite is to programmers like the stars are to astronomers. A wonder.
Amazing, especially - for me - that the FTS5 full-text search just works. Longer term, I am if it were possible to split the DB code into read and write parts and cross-compile only read part for delivery to the browser.
If you are interested in full-text search on the client, Lunr is also an option: https://lunrjs.com/docs/index.html
Lunr needs the full index on client though, right?
Being able to use fts-5 without the penalty of having to pull down the whole index make it work much better at larger scales, even with the penalty of additional network requests.
2 replies →
Time to create the index for lunr limits the size of the data-set that can be used. If you have a lot of tiny documents, then it is more practical to scan the documents directly, rather than using the lunr index.
I wrote a similar thing in Rust for a Factorio mod manager. Mods are hosted on the remote HTTP server as ZIP files, and the mod manager needs a single `info.json` file from the ZIP for the mod metadata. So the mod manager avoids downloading the whole mod and then unpacking it by building a file abstraction that uses HTTP range queries to download just the chunks it needs. For ZIP files the directory is stored at the end at an unknown offset, so the read pattern is to gradually seek backwards from the end until you find the start of the directory, then find the file entry, then seek and read the file.
I didn't fiddle with the window sizes like the submitted article (the chunk is fixed to 8KiB), but I did optimize it so that reading chunk N+1 of the file reused the response reader of chunk N rather than make a new request. Furthermore I keep an LRU cache of only the last three chunks in memory, because the ZIP files are each only read once.
[1]: https://github.com/Arnavion/fac-rs/blob/2d2622a1c9934719ce65...
[2]: https://github.com/Arnavion/fac-rs/blob/2d2622a1c9934719ce65...
Modeling the DOM in SQL... Further evidence that anything we can imagine has some stable representation in third normal form. Is it fast? Maybe not. But is it correct? Provably.
There was a group that rewrote the Chromium DOM itself in a data oriented design (which learns from database design and sort of applies to cache utilization and locality) and got a 6X speedup in some places:
https://meetingcpp.com/mcpp/slides/2018/Data-oriented%20desi...
This paper is basically what we do, except we have a big container type, aptly named "Domain.cs". Inside, you will find a public List<T> of every type. We decided to emulate SQL throughout the vertical (i.e. each List is a table) in order to make mapping to SQL a trivial affair. None of our Domain types contains any complex type as a property. Everything can go 1:1 to SQL. We use LINQ (or SQL) to produce projections as appropriate.
There isn't actually just 1 big domain instance either. It's more like one per user session, and then a global instance.
The impact this had on reducing complexity and bugs is incredible. I haven't seen a null ref exception in a long time. Also, being able to dump your entire universe to disk by serializing a single object is really nice.
In a similar vein, I've mentioned this before, but if you're doing Python stuff, you can use the apsw package (not the one in PyPi, though) to write a VFS layer that SQLite will use to read the database.
I've used this for the same basic idea as this article, only letting me store SQLite databases in AWS's S3 that I can access with AWS APIs so they don't need to be public. It works well, though it's absolutely not for every use case, the overhead is considerable.
I even used it once to read SQLite database files in a zip file stored in S3 without having any local storage to use. Not one of my prouder moments, but hey, I coded my way out of the corner someone else designed for me.
This one? https://rogerbinns.github.io/apsw/
Yep, exactly that one. There's a simple example of a VFS implementation on the examples page that's a reasonable starting point:
https://rogerbinns.github.io/apsw/example.html
Once you wrap your head around how you need to pass parameters to the helper, it's really straightforward, you just need to implement the xOpen and xRead calls.
1 reply →
In the genomics world, Tabix indices enables similar use cases. An ordered TSV file is compressed in chunks (bgzip) and a Tabix index created to allow range based access by mapping from the index -> chunk. This allows a browser based genome browser zoomed into a section of the genome to fetch information from a multi gigabyte file.
http://www.htslib.org/doc/tabix.html
now if only tabix and most hokey bioinformatics formats would die and just be replaced with a formal schema spec in SQLite...
Honestly I think Tabix's bgzipped TSV is one of the less hokey bioinformatics formats, at least compared to the various custom binary formats floating around.
For web browser based genome browsers I suspect this (very cool!) sqlite hack would require many more http requests.
This is hilariously clever.
Using the "Range" HTTP header to read chunks of the database file absolutely works!
But to be clear, there's no write equivalent, is there? You can't use "Range" with a PUT request.
The write equivalent would be the PATCH method using a "message/byteranges" body: https://tools.ietf.org/id/draft-wright-http-partial-upload-0...
Wow that's fascinating, thanks. That would actually turn HTTP into a kind of random-access filesystem, if adopted.
It's amazing but also slightly terrifying in the knowledge that then someone's going to write an SMB-over-HTTP connector.
TA was clear - there's no way to write, since static file hosting doesn't support dynamic write to begin with.
However, I imagine a service to support your scenario could be written in a standard back-end server language like Go or JS. The challenges involved would be much greater, however -- how to handle concurrency in particular. I suspect one would do better to just run PostgreSQL behind a web API.
That's basically re-inventing the Database but on the client side. We have gone a long way but we are closer to having the server side just as a data store.
Even if there was, I can't imagine your everyday static host ever supporting it.
Apart from the genius of the author (conceiving a sequence of relatively understandable steps that unlock a potentially huge area), this highlights how efficient a SQLite can be in terms of slow resource usage.
Over the last few months I tried to think of a clever way to set up a legacy site for a dictionary that I serve on a VM just because I also need to run sqlite. Since I want to make sure it'll run for longer than me paying for the VM this is the best possible solution. At some point no more updates will happen and it's going to be a static website. So bundling it like this is incredible. I can run multiple backups on different hosts with no additional costs.
If you just do an occasional key/value lookup, you don't need 1.2 MiB of WebAssembly. [1] That might already exceed your total database size.
I'd solve it via sharding: divide the database into N pieces via range- or hash-sharding. [1] Choose an N that's large enough for each piece to be reasonably small. When you look up a key, fetch the shard of interest.
You can put each piece into separate files (a little simpler to code, and most static servers will use pre-gzipped files for "Content-Encoding: gzip requests" easily, but you waste more disk space due to internal fragmentation) or one file (with range serving and an index of the byte range offset for each piece).
The format for each piece can be anything, eg json (simple) or an sstable-like format (more efficient). [3]
[1] Content-Length of https://phiresky.github.io/youtube-sponsorship-stats/sql-was...
[2] hash-sharding means: piece[i] has all the keys where hash(key) % N = i.
[3] https://github.com/google/leveldb/blob/master/doc/table_form... although they just say "formatted according to the code in block_builder.cc" instead of describing the most relevant part.
This is really cool! I wonder what the restrictions are and if we would ever be able to write to a SQLite db like this in the future. This could push more to the front end without needing to write apis.
The main restriction is that the DB really needs well fitting indexes, otherwise querying is really slow and fetches a lot of data.
Regarding writing:
You could of course implement a writing API with POST requests for changing pages of the database - but then you would lose most of the benefits of this (not requiring any special kind of server).
I also thought about implementing a kind of overlay filesystem, where chunks that are written to the file are stored in a local storage so the modified data is available locally while still reading everything else from the remote database.
Interestingly in SQLite that's already exactly what the WAL mode does: It's a second file next to the database that's just a set of pages that are overlaid over the main file when read queries happen - which allows concurrent readers and writers since the database itself isn't in an undefined state even when write transactions are happening.
So you could enable WAL mode and disable WAL auto checkpointing, then you get a downloadable WAL file that can be read by normal SQLite and written back to the main file. It would be neat, but I'm not sure what the actual use case would be ;)
> I also thought about implementing a kind of overlay filesystem, where chunks that are written to the file are stored in a local storage so the modified data is available locally while still reading everything else from the remote database.
If ever the intent were to involve eventually persisting those changes, then it would be worthwhile looking at remoteStorage, which works like this.
I was thinking you could implement a write API using the GitHub API, every write can be its own commit.
> I also thought about implementing a kind of overlay filesystem, where chunks that are written to the file are stored in a local storage so the modified data is available locally while still reading everything else from the remote database.
Perhaps adding IPFS to the mix for persisting data would be interesting, I'm sure there are use cases in peer to peer applications. Anyway, amazing innovation thank you for writing this :)
Seems like it might be possible to add WebRTC(or some other peer-based live system, I don't know the performance characteristics of WebRTC) to get realtime writes. Those edits would then be added to the WAL, and every say, 10 minutes anyone who has been active for 10 minutes could checkpoint and push the changes to github.
It's slightly more centralized than perfect, but man do you get a lot for a little.
Since you can do static hosting from a git repo, I wonder if you could directly push your changes to your git repo and have your CI/CD solution just deploy it instead?
There has to be a git.js implementation out there and you could move the DB to it's own repo and create an https access token (for Github)... the issue there is that someone could use that token to commit whatever to your database repo.
1 reply →
This is both a clever hack and a brilliant solution. But it also worries me a bit. Mostly because I've seen a lot of Visual Basic + MS Access solutions. They work fine on a single computer, but they you put a database on a network share to be able to share it between a few computers and the performance is often horrendous. If you're doing a lot of data processing it's often best to do it as close to the data as possible.
But as always, it's seldom the tools, but the right tool used for the wrong usecase that is the problem.
I have the feeling I'm watching some semi-major new web tech being born... out of the blue, in a blog post.
Fucking amazing, mad props. Beautiful work!
This is an really awesome idea! I have a plan for a static-ish site (updated daily) that I was going to use sqlite for anyway, but server side. I will definitely look into this approach instead!
Beyond static hosting : Now imagine also implementing a virtual file system that SENDS chunks of the database with HTTP Range requests when SQLite tries to write from the filesystem
Or more generally: I predict a WASI implementation which will treat ANY server resource as a virtual file, replacing REST.
First of all, this is a very cool web hack, I like it very much.
I have a question. It's a 668.8MB database file. What does actually happen if the query has to scan 300 mb before finding the right answer? Wouldn't it be better to do the work up front and deliver the answers as static json files? Sure you loose the flexibility of dynamic queries, but do you really have that flexibility in non trivial cases (e.g. 300 mb search)?
If your statistic or whatever can be precomputed, you can precompute it and put it in db table rather than compute it each time by reading the 300MB.
Using HTTP range requests like this is just SO clever.
I'm also impressed with the implementation for the blog itself. I love this sort of clean, version-tracked sort of implementation.
works on ObservableHQ
https://observablehq.com/@tomlarkworthy/phiresky-sqlite-quer...
Solution works really well to databases which will not be updated frequently, like a standalone site.
Although one should be aware of one very important git behavior - git does not diff binary files (like SQLite dbs). That means 2 things:
1. Each db update will generate a new file in git, maintaining the whole old file in history, instead of the diff in bytes. This will accumulate a lot of clutter in the repo
2. As git does not diff binaries, there is a very small risk of corruption (especially if you work in multiple OSs, because of CRLF)
Ref - https://robinwinslow.uk/dont-ever-commit-binary-files-to-git
Git does actually diff binaries and stores them very efficiently :) If you do a single small UPDATE in your db file git will only store the changed information. It's just kinda slow, and for most binary files the effort git spends to try and compute deltas for binary files is useless - which is why it has a bad reputation for binary files.
Note that the diffs that git shows you are completely unrelated to the deltas it uses to compress it's database - which are always "binary deltas" and not line-based diffs.
Also I'm not sure why you mean that db corruption possibility has something to do with whether or not it stores diffs?
You can just store the database in text format (e.g. csv) in the git and turn it to SQLite db when building the website.
Minor nitpick: Git does not store diffs for any file format but always the full file for each version. So it does not really matter that its binary (except for not being able to VIEW the diff, but I guess you could even implement a plugin for that) but just that it's a big file. Even a huge text file would be fully stored per version.
/edit: The sibling comments mentions that git can infact delta compress older commits for storage efficency. But my point was that git commits are not deltas but full snapshots.
This is mostly correct. Git's core object model is snapshots, which can then optionally be compressed. That should be transparent though.
You are only gonna encounter corruption if u either a) messed up the gitconfig for line endings or b) named the database mydbfile.txt
TL;DR: Compile SQLite to JS with emscripten, implement a virtual fs in JS to stream chunks of a statically hosted (readonly) SQL database.
If queries make use of indices, only a fraction of the database needs to be downloaded.
Also, you can use SQLite to query the DOM.
I can't figure out exactly how it knows which chunk to download. Does it always download the whole index first? Or does it include it in the built JS file itself?
Both the index and table data are btrees. These are trees - the root node sits in some known location (offset) in the file, referenced by the file header and metadata. As SQLite traverses the tree, it encounters new descendents it would like to visit, presumably identified by their byte offset in the file, which is all needed for this VFS magic to issue a suitable range request.
- SQlite opens the file and reads 4kb worth of header -> range request for byte 0-4096
- headers/metadata refers to index table with root node at 8192kb
- user issues SELECT * from index WHERE name = 'foo'
- SQLite reads root node from the file (range request for 8192kb..)
- Root node indicates left branch covers 'foo'. Left branch node at address 12345kb
- Fetch left branch (range request for 12345kb)
- New node contains an index entry for 'foo', row 55 of data page at 919191kb
- SQLite reads data page (range request for 91919191kb..)
etc etc etc
1 reply →
SQLite has runtime-pluggable VFS support, i.e. you give it a struct with functions for opening a file, reading some bytes, writing some bytes, synchronizing file contents, closing a file. This project provides such a VFS module, that, because it actually runs in the browser, performs HTTP requests to read data. Emscripten provides a way to run a mix of C/C++ code in the same environment as some JavaScript code inside the browser. The reason SQLite has this pluggable VFS support is to properly support embedded systems, different locking APIs, and things like database encryption.
https://www.sqlite.org/vfs.html
That's part of SQLite. It has been optimised to reduce disk reads, because those can be slow on spinning hard drives. Coincidentally, this translates well into an optimised algorithm that minimises the amount of HTTP range requests to make.
B-Tree indexes are designed to work like this, to require a low number of IO operations. The index contains pointers to other places in the index.
6 replies →
Nice. Reminds me of Bellard’s https://vfsync.org/ . It’s file system pages served over http, to back his jslinux browser VMs
The Hacker News demographic, mostly US and EU based, might be under appreciating how impactful this is because of CDNs. For anyone not in the continent of your central database, this means absurdly faster interactions for data visualization.
I moved from US to Brazil 3 years ago, and I still notice the latency when a site runs their backend only in one location. This cleaver solution makes interacting with the graph supper snappy even compared to enterprises that do have database servers in Brazil. Very impressive!
How close are we to hosting searchable torrent indices on IPFS?
I wonder sometimes, what if we focus on producing native JS VM hardware, would it perform same as or better than WASM? Let's run everything on JS.
Wicket stuff, loved it. Not sure if this will ever be “production ready” or merged by sql.JS-like projects but cool proof of concept.
Searching the Common Crawl does similar byte level access to S3 based on a smaller index of indexes. Really great, actually.
Hmm... Is it possible to use this with two seperate databases, one a remote read only and one a local writable DB that could be re-exported to a static file host? Having just glanced at the code it looks like you would have to load two seperate libraries, one from this project and one from the original sql.js
This is awesome. Got my wheels turning :)
Super cool. I wonder if an approach like this could ever work for a writable database. I guess the issue is that you couldn't have fine grained access control without a whole lot of server side validation, at which point you might as well just run a regular database server.
This hack reminds me of Godel's hacking of an axiomatic mathematical system, to prove and plant his incompleteness theorem;
This is really a great hack: using a system in a unexpected and creative way for which it wan not originally deigned, but which is also very useful and nice.
Very clever. I wonder if there are databases optimised for this use case. I can imagine something that always requires indexes to do the queries and stores data in disk in ways to make it easy to fetch only the bits you need.
That would be equivalent to always putting your data in b-trees or other structures, according to the request patterns, without keeping the tables themselves. Sort of how you need to do that in Redis for any kind of sane request strategy other than key-value lookups.
Hm, yeah, I think a key-value store would be easier to implement. I haven't looked at redis for some time now, but last time I did, persistence was done through snapshotting and everything would really be loaded into memory at start time. So that wouldn't work for this use case, where all you can do is serve a static file.
But my question revolves around databases assuming that the disk they access is local or at least a fast network storage. I wonder if there are any databases optimized to access slow storage over low bandwidth, where you're really trying to optimize the amount of data read more than anything else.
1 reply →
For similar results, you can use SQL with IndexedDB running fully client-side: https://github.com/agershun/alasql
Hi, I'm working on SkySQL, maybe it's useful for you: https://github.com/upshot-tech/SkySQL
stahp, you gonna get gh pages shut down
Very clever! Keep in mind this is a read-only dataset with the really clever bit being the ability to scan through the dataset and support sqlite query syntax.
This is perfect for my need, been looking for a way to add search to my static site completely free of server. Now I can use sqlite as index.
This certainly does look like an interesting solution, I'd be keen to try it myself. However, just in case you didn't already know about Lunr (https://lunrjs.com/), it is fairly commonly used to implement search on static websites.
e.g. https://squidfunk.github.io/mkdocs-material/
There are of course other similar libraries too.
EDIT: Whoops, just saw a few comments below Lunr is already mentioned.
yeah I have come across Lunr and maybe a couple of other things in my research and I think for blogging it'll work well. What I'm interested in finding out is what works for a larger static site, that won't require you to load the index up-front. I'm also curious about how this sqlite thing picks the correct range to load (haven't looked at the code) and what the worst case might be.
1 reply →
This is super clever. If you add handling POST somehow as random access writes, you could have a read-write DB hosted pretty much anywhere
Doesn't the webserver have to seek from the beginning of the ~600mb file to the range you want, unless the file is in memory?
No, see here, for example
https://news.ycombinator.com/item?id=27018194
That doesn't answer the question.
Yes the web server supports range requests. Yes it only returns 50kb.
But what mechanism is letting it scan to just those ranges in the binary file. Doesn't the file system make you seek to the starting block and then read from there?
The point is, while it looks very efficient, there might be a crap ton of IO going on for your little 50kb response.
EDIT: probably the webserver is doing an fseek(), and performance will vary based on file system impl. This is something I will need to benchmark.
1 reply →
>Of course it can’t write to this file, but a read-only database is still very useful.
perhaps read-only should be added to the title
I thought the "static" part of "static file hoster" was clear enough.
This is incredible ! Don't have a use case for this right now but am certainly saving this for later.
This is truly awesome. Very clever.
If you just want static data, using jsroot or jsfive might be a better option.
I think you missed the main part: the dataset is not in memory. This is not SQLite-in-the-browser but using a virtual file system over HTTP. Neither of those alternatives do anything similar.
Same with those! They'll just grab the chunks they need (also with range requests) to do what you want from binary ROOT or (presumably, I haven't actually used jsfive) HDF5 files.
This is pretty awesome. Now if only GitHub Pages did IPv6 as well... :)
Incredibly clever use of paging and http range queries! Well done.
This is great but wish it had write ability, not just read only.
Hello new paradigm.
This is amazing!
I'm also surprised that Github Pages lets you present arbitrary JS to the point where you can upload SQLite as WebAssembly. Isn't this dangerous?
What is dangerous here? Wasm is more crippled in access than normal js. And js is simply in every web page these days. You can't make a static site hosting service and tell people not to use js, that would be very lame.
this is genius. I love it.
This is pretty brilliant.
I am a huge fan of sqlite and will definitely be giving this a shot in the near future.
Incredible work.
I see myself using this in conjunction with a conventionally hosted pg db for dynamic content.
Watch dragon ball season 1 full https://animated2021.blogspot.com/2021/05/dragon-ball-season...
health tips for men and women. We all should know about these things http://healthwithbeauty.xyz/2021/04/20/health-tips-for-men/
watch best funny peter rabbit movie online https://animated2021.blogspot.com/2021/05/watch-peter-rabbit...
Virginia Girls Scouts making cookie deliveries via drone https://www.interestingnews.club/2021/05/virginia-girls-scou...
couldn't you just link the source code or show how to reproduce what you did? really? you're just showing everything about your work but NOTHING about how to reproduce your work?? THERE IS NOTHING I HATE MORE THAN THESE KIND OF POSTS!!!
This is incredibly clever and fun.
That said, all you need to query an SQLite database on the server side is a simple PHP script (as opposed to a running db server), and most static hosting providers offer PHP support.
This seems cool, but doesn't Fossil (from the SQLite author) already do it "out of the box" ?
https://www.fossil-scm.org/home/doc/trunk/www/index.wiki
Fossil runs a server application.
This is certainly a clever hack. But it makes things cheaper and easier for the website owner at the expense of the users. This kind of solution will add to the bloat that is making the web unusable enough that people are seriously proposing a remote browser as a solution for desktop users (remember Mighty the other day?). We shouldn't let the cleverness distract us from this drawback.
Over high latency links this would be virtually unusable. Why not just download the entire database into memory over XHR on page load? SQLite databases of pure data usually aren’t over 10MB in size.
This particular demo page actually makes queries against an almost 700 MB large (fills one CD!) SQLite database. Because the amount of data read is almost negligible (few hundred kB), performance is limited by latency (as you say). However, high-latency links also tend to be slower, so downloading the entire database a-priori would almost always be much slower.
For example, on a 1 megabit/s link with 300 ms RTT, one example would take about 2 seconds for the data transfer itself while spending another 3 seconds or so on waiting. Downloading the entire file would take around an hour and a half.
For your 10 MB database, transferring it as a whole would take 80 seconds. Assuming this solution instead needs to read e.g. 250 kB (taking 2 seconds to transfer), it could still bounce around 250 times to the database before those 10 MB are fully downloaded. (This would be a really odd query, since it would only read on average two pages per read request)
Right but that is an artificially created demo by the author to justify the solution being presented (no offense). The question is how common are ~GB large SQLite databases in the real world relative to databases that are ~MB large?
In my experience SQLite databases of millions of rows of raw tabular data tend to compress very well into dozens of megabytes. Indeed SQLite is often touted as a file format for applications.
11 replies →
That is hilariously wrong for a lot of use cases. I will find this very handy for some SQLite databases I have that are several GBs in size. I am looking right now at using this contribution.
It’s not hilariously wrong or wrong at all that over high latency links this would be virtually unusable.
It’s certainly possible that people are using SQLite databases with sizes on the order of gigabytes but in my experience those are the exception not the rule.
1 reply →
And the article starts by mentioning that you can download the entire file if it's not too large. And then goes on to present a solution for larger files. What more answer to "Why not just download the entire database" do you expect?
I have been using SQLite databases for a few user application that has been running for close to a decade now. They are usually about 1.5GB.
BTW, SQLite has a (theoretical?) max size of 140TB! (or so I've read)
What do you think is the size of the average SQLite database?
2 replies →
> SQLite databases of pure data usually aren’t over 10MB in size
Why do you think this?
The demo here uses a 670MB database file.