20 ms·

Hosting SQLite databases on GitHub Pages or any static file hoster

1812 points by phiresky 5y ago

bilater 5y ago
This is awesome. Got my wheels turning :)
Gehinnn 5y ago
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.
- deleted 5y ago
  [deleted]
- pudmaidai 5y ago
  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?
  - mvanaltvorst 5y ago
    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.
  - formerly_proven 5y ago
    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 https://www.sqlite.org/vfs.html
  - fulafel 5y ago
    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.
    - pudmaidai 5y ago
      So the answer is “yes, it has to download the index first”? None of these comments answer my question.
      - detaro 5y ago
        At least the information describing what tables and indices there are and where to find them - and then it gets what it needs once a query is run. Just like sqlite would if running from a local file on disk.
      - phiresky 5y ago
        The B-Tree is a tree that in this case is perfectly balanced. So if you do a query with an index in a database it will fetch an logarithmic amount of data from the index and then a constant amount of data from the table. For the example the wdi_data table is 300MB and an index on it is 100MB in size. This index has a tree depth of 4 - which means SQLite has to read exactly 4 pages (4KiB) to get to the bottom of it and find the exact position of the actual row data. you can check the depth of the b-trees with `sqlite3_analyzer`.
      - rakoo 5y ago
        Everything in SQLite is stored in B-Trees. Data or indexes. So you don't need to download the whole index first; you only need to download the necessary pages of the trees to access data, whether it's part of an index or actual data
      - tehbeard 5y ago
        It just needs to download the pages (x KB chunks) to traverse from the header to the particular index and table schema, a fraction of the whole data.
      - fulafel 5y ago
  - cookguyruffles 5y ago
    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
    - jaza 5y ago
      Thanks, I too was struggling to understand how it's able to do such efficient targeted range requests, you explained it nicely.
spamalot159 5y ago
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.
- phiresky 5y ago
  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 ;)
  - WrtCdEvrydy 5y ago
    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.
    - wh33zle 5y ago
      Maybe forcing the user to login with GitHub would be an option? And the changes to the database could be modelled as pull requests?
sroussey 5y ago
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?
- jhgb 5y ago
  Microsoft Access Cloud Edition, basically?
  - nbevans 5y ago
    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 ;-)
    - jhgb 5y ago
      I was mostly referring to the shared file access approach.
- misterdata 5y ago
  See also https://github.com/bittorrent/sqltorrent https://github.com/bittorrent/sqltorrent, same trick but using BitTorrent
  - phiresky 5y ago
    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/ https://phiresky.github.io/tv-show-ratings/ That uses a protobufs split into a hashmap instead of SQLite though.
BlueTemplar 5y ago
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 https://www.fossil-scm.org/home/doc/trunk/www/index.wiki
- detaro 5y ago
  Fossil runs a server application.
claytongulick 5y ago
Incredibly clever use of paging and http range queries! Well done.
CyberRabbi 5y ago
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.
- petters 5y ago
  > SQLite databases of pure data usually aren’t over 10MB in size Why do you think this?
  - deleted 5y ago
    [deleted]
- mcculley 5y ago
  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.
  - CyberRabbi 5y ago
    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.
    - tehbeard 5y ago
      Over high latency links most anything interesting is virtually unusable, so stop using it as a high horse to stand upon.
- simonw 5y ago
  The demo here uses a 670MB database file.
- formerly_proven 5y ago
bob1029 5y ago
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.
- cma 5y ago
  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%20design%20in%20practice_Nikolov_MeetingCpp18.pdf https://meetingcpp.com/mcpp/slides/2018/Data-oriented%20desi...
  - bob1029 5y ago
    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.
ianlevesque 5y ago
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.
- Valgrim 5y ago
  I wonder if this could be used to serve dynamic maps.
  - durkie 5y ago
    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
    - bdon 5y ago
      This is the approach I took with http://github.com/protomaps/pmtiles http://github.com/protomaps/pmtiles , though it's optimized for the very specific use case of going from Z/X/Y integer coordinates to binary blobs, and takes shortcuts to accomplish that (fixed-width keys and root index page)
      - config_yml 5y ago
        Funny enough I was looking into mbtiles serverless solutions before I went to bed, now I start my day browsing HN and I find this clever solution. Love HN for this type of stuff :)
  - blacha 5y ago
    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/ 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/ https://registry.opendata.aws/sentinel-2-l2a-cogs/
arafalov 5y ago
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.
- rzzzt 5y ago
  If you are interested in full-text search on the client, Lunr is also an option: https://lunrjs.com/docs/index.html https://lunrjs.com/docs/index.html
  - tehbeard 5y ago
    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.
    - formerly_proven 5y ago
      This could be genuinely interesting for tools like e.g. sphinx-doc, which currently has a client-side search that does indeed ship the entire index to the client.
      - tehbeard 5y ago
        There's probably a dataset size tradeoff with small enough number of documents, but even then this could have the option of if db is < x MB total, fetch all in async task and then use that.
  - joshuanapoli 5y ago
    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.
laurencerowe 5y ago
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 http://www.htslib.org/doc/tabix.html
- Ultimatt 5y ago
  now if only tabix and most hokey bioinformatics formats would die and just be replaced with a formal schema spec in SQLite...
  - laurencerowe 5y ago
    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.
villasv 5y ago
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.
- deleted 5y ago
  [deleted]
rjeli 5y ago
Nice. Reminds me of Bellard’s https://vfsync.org/ https://vfsync.org/ . It’s file system pages served over http, to back his jslinux browser VMs
- deleted 5y ago
  [deleted]
simonw 5y ago
Using HTTP range requests like this is just SO clever.
simonw 5y ago
Pop open the network pane in the browser tools and try running this SQL query for a demo of how clever this is: select country_code, long_name from wdi_country order by rowid desc limit 100 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 https://twitter.com/simonw/status/1388933800445452290
- WJW 5y ago
  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?
  - simonw 5y ago
    The clever part here is only fetching 50KB out of 680MB.
  - ajfjrbfbf 5y ago
    > 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.
  - watermelon0 5y ago
    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.
    - 5y ago
drtournier 5y ago
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 https://robinwinslow.uk/dont-ever-commit-binary-files-to-git
- phiresky 5y ago
  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?
- laszlokorte 5y ago
  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.
  - iudqnolq 5y ago
    This is mostly correct. Git's core object model is snapshots, which can then optionally be compressed. That should be transparent though.
cozzyd 5y ago
If you just want static data, using jsroot or jsfive might be a better option.
- jiofih 5y ago
  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.
  - cozzyd 5y ago
    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.
BMorearty 5y ago
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.
- phiresky 5y ago
  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 https://www.sqlite.org/vtab.html [2] https://github.com/phiresky/sql.js-httpvfs/blob/master/src/vtab.ts https://github.com/phiresky/sql.js-httpvfs/blob/master/src/v...
  - deleted 5y ago
    [deleted]
- nbevans 5y ago
  "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.
diveanon 5y ago
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.
dreix 5y ago
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.
- scottlamb 5y ago
  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-wasm-dd22a976e2e149886e6e.wasm 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_format.md 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.
wheybags 5y ago
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!
cryptonector 5y ago
This is pretty brilliant.
tlb 5y ago
The question I had is answered by this line of code: xhr.setRequestHeader("Range", "bytes=" + from + "-" + to); I am a little surprised you can just do that. In https://github.com/phiresky/sql.js-httpvfs/blob/master/src/lazyFile.ts https://github.com/phiresky/sql.js-httpvfs/blob/master/src/l...
- crazygringo 5y ago
  Not all webservers support/enable it, so YMMV. But as long as you're dealing with a known server that does, then gravy!
  - altfredd 5y ago
    > 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.
    - enneff 5y ago
      Depends on what’s being served. Any decent static file server should support it, but if the content is at all dynamically produced then the authors would have to think to implement it and rarely do.
    - crazygringo 5y ago
      I can't think of a specific one, but a decent proportion (maybe a quarter?) of HTTP downloads I attempt don't support resuming a partial download, therefore don't support Range. (I.e. resuming always starts from the beginning.) I would assume this is often because the site in question isn't using Apache etc. to serve a file directly, but is either essentially proxying it to some custom-built file serving service, or a script that processes/authenticates the file in some way, and they just never bothered to implement Range.
  - stabbles 5y ago
    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
modeless 5y ago
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.
ponytech 5y ago
This is truly awesome. Very clever.
crazygringo 5y ago
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.
- TimTheTinker 5y ago
  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.
  - csomar 5y ago
    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.
- anonydsfsfs 5y ago
  The write equivalent would be the PATCH method using a "message/byteranges" body: https://tools.ietf.org/id/draft-wright-http-partial-upload-01.html https://tools.ietf.org/id/draft-wright-http-partial-upload-0...
  - crazygringo 5y ago
    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.
- NoInkling 5y ago
  Even if there was, I can't imagine your everyday static host ever supporting it.
banana_giraffe 5y ago
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.
- killingtime74 5y ago
  This one? https://rogerbinns.github.io/apsw/ https://rogerbinns.github.io/apsw/
  - banana_giraffe 5y ago
    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 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.
    - killingtime74 5y ago
      Thank you!
tedk-42 5y ago
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.
th0ma5 5y ago
Searching the Common Crawl does similar byte level access to S3 based on a smaller index of indexes. Really great, actually.
Procrastes 5y ago
I'm also impressed with the implementation for the blog itself. I love this sort of clean, version-tracked sort of implementation.
867-5309 5y ago
>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
- roddds 5y ago
  I thought the "static" part of "static file hoster" was clear enough.
sarak12070 5y ago
Watch dragon ball season 1 full https://animated2021.blogspot.com/2021/05/dragon-ball-season-1-full.html 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/ 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-movie-australia.html 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-scouts-making-cookie.html https://www.interestingnews.club/2021/05/virginia-girls-scou...
nsonha 5y ago
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.
- Benjamin_Dobell 5y ago
  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/ https://lunrjs.com/), it is fairly commonly used to implement search on static websites. e.g. https://squidfunk.github.io/mkdocs-material/ 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.
  - nsonha 5y ago
    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.
    - masklinn 5y ago
      > I'm also curious about how this sqlite thing picks the correct range to load Indexes are usually btree, it finds what and where the relevant index is (probably from the schema queries), then goes trawling through the b-tree. That’s how db engines normally work, they don’t liberally go through the entire db contents. If there’s no index then it finds the start of the table and scans it sequentially (which is exactly what it sounds like).
mwcampbell 5y ago
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.
justinclift 5y ago
This is pretty awesome. Now if only GitHub Pages did IPv6 as well... :)
Seattle3503 5y ago
How close are we to hosting searchable torrent indices on IPFS?
bruhhh 5y ago
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!!!
IceWreck 5y ago
This is incredible ! Don't have a use case for this right now but am certainly saving this for later.
yoz 5y ago
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?
- duskwuff 5y ago
  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.
  - phiresky 5y ago
    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.
- singularity2001 5y ago
  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.)
- 5y ago
graderjs 5y ago
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.
- phiresky 5y ago
  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.
  - f430 5y ago
    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
hutrdvnj 5y ago
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)?
- willvarfar 5y ago
  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.
winrid 5y ago
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?
- philshem 5y ago
  No, see here, for example https://news.ycombinator.com/item?id=27018194 https://news.ycombinator.com/item?id=27018194
  - winrid 5y ago
    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.
    - ric2b 5y ago
      For most filesystems it should be no issue to seek directly to a specific offset on a file, it's just like accessing an array, if you know where it starts and the offset you just need to add them and tell the disk to read that address.
iveqy 5y ago
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.
TedDoesntTalk 5y ago
This is great but wish it had write ability, not just read only.
isoprophlex 5y ago
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!
slver 5y ago
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.
dawe35 5y ago
Hi, I'm working on SkySQL, maybe it's useful for you: https://github.com/upshot-tech/SkySQL https://github.com/upshot-tech/SkySQL
singularity2001 5y ago
>>> 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.
bambax 5y ago
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.
mFixman 5y ago
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?
- nsonha 5y ago
  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.
tlarkworthy 5y ago
works on ObservableHQ https://observablehq.com/@tomlarkworthy/phiresky-sqlite-query https://observablehq.com/@tomlarkworthy/phiresky-sqlite-quer...
irae 5y ago
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!
sztanko 5y ago
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.
aflag 5y ago
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.
- aasasd 5y ago
  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.
  - aflag 5y ago
    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.
    - aasasd 5y ago
      Well, every database already optimizes disk access (at least until the recent years with the ‘just add SSDs’ attitude). However, they tend to assume that indexes should be loaded into memory. For this use-case, you'd want a database that can use indexes themselves from disk and treat them like partitioned storage: e.g. when reading data for years 2019 to 2021, only request parts corresponding to that, and not previous years. Dunno whether SQLite can have indexes partially in memory—with its niche of low-end devices and apps, it's quite possible that it can. Actually, this sort of partial access (i.e. partitioning) is rather easy to implement by addressing separate data files by name, instead of using numeric ranges into a database. Basically just put the data into files named by the years (in my example); or bucket the data into chunks of arbitrary size and use the chunks as files. Elementary to extend this to multiple fields in the index. In short, partitioning based on actual field values can be much easier in the static-http approach than using opaque ranges. Probably also more effective if something like http2 allows requesting several files in one request—since you can avoid requesting too little or too much.
nanna 5y ago
Hello new paradigm.
whoomp12342 5y ago
stahp, you gonna get gh pages shut down
shkkmo 5y ago
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
Arnavion 5y ago
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/2d2622a1c9934719ce65b1fc61503e32b36eea02/src/solve/web_reader.rs https://github.com/Arnavion/fac-rs/blob/2d2622a1c9934719ce65... [2]: https://github.com/Arnavion/fac-rs/blob/2d2622a1c9934719ce65b1fc61503e32b36eea02/src/solve/zip.rs https://github.com/Arnavion/fac-rs/blob/2d2622a1c9934719ce65...
pmarreck 5y ago
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
skyde 5y ago
this is genius. I love it.
diedyesterday 5y ago
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.
niutech 5y ago
For similar results, you can use SQL with IndexedDB running fully client-side: https://github.com/agershun/alasql https://github.com/agershun/alasql

1812 points by phiresky 5y ago

This is awesome. Got my wheels turning :)

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.

deleted 5y ago
[deleted]
pudmaidai 5y ago
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?
- mvanaltvorst 5y ago
  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.
- formerly_proven 5y ago
  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 https://www.sqlite.org/vfs.html
- fulafel 5y ago
  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.
  - pudmaidai 5y ago
    So the answer is “yes, it has to download the index first”? None of these comments answer my question.
    - detaro 5y ago
      At least the information describing what tables and indices there are and where to find them - and then it gets what it needs once a query is run. Just like sqlite would if running from a local file on disk.
    - phiresky 5y ago
      The B-Tree is a tree that in this case is perfectly balanced. So if you do a query with an index in a database it will fetch an logarithmic amount of data from the index and then a constant amount of data from the table. For the example the wdi_data table is 300MB and an index on it is 100MB in size. This index has a tree depth of 4 - which means SQLite has to read exactly 4 pages (4KiB) to get to the bottom of it and find the exact position of the actual row data. you can check the depth of the b-trees with `sqlite3_analyzer`.
    - rakoo 5y ago
      Everything in SQLite is stored in B-Trees. Data or indexes. So you don't need to download the whole index first; you only need to download the necessary pages of the trees to access data, whether it's part of an index or actual data
    - tehbeard 5y ago
      It just needs to download the pages (x KB chunks) to traverse from the header to the particular index and table schema, a fraction of the whole data.
    - fulafel 5y ago
- cookguyruffles 5y ago
  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
  - jaza 5y ago
    Thanks, I too was struggling to understand how it's able to do such efficient targeted range requests, you explained it nicely.

spamalot159 5y ago

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.

phiresky 5y ago
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 ;)
- WrtCdEvrydy 5y ago
  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.
  - wh33zle 5y ago
    Maybe forcing the user to login with GitHub would be an option? And the changes to the database could be modelled as pull requests?

sroussey 5y ago

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?

jhgb 5y ago
Microsoft Access Cloud Edition, basically?
- nbevans 5y ago
  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 ;-)
  - jhgb 5y ago
    I was mostly referring to the shared file access approach.
misterdata 5y ago
See also https://github.com/bittorrent/sqltorrent https://github.com/bittorrent/sqltorrent, same trick but using BitTorrent
- phiresky 5y ago
  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/ https://phiresky.github.io/tv-show-ratings/ That uses a protobufs split into a hashmap instead of SQLite though.

BlueTemplar 5y ago

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 https://www.fossil-scm.org/home/doc/trunk/www/index.wiki

detaro 5y ago
Fossil runs a server application.

claytongulick 5y ago

Incredibly clever use of paging and http range queries! Well done.

CyberRabbi 5y ago

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.

petters 5y ago
> SQLite databases of pure data usually aren’t over 10MB in size Why do you think this?
- deleted 5y ago
  [deleted]
mcculley 5y ago
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.
- CyberRabbi 5y ago
  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.
  - tehbeard 5y ago
    Over high latency links most anything interesting is virtually unusable, so stop using it as a high horse to stand upon.
simonw 5y ago
The demo here uses a 670MB database file.
formerly_proven 5y ago

bob1029 5y ago

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.

cma 5y ago
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%20design%20in%20practice_Nikolov_MeetingCpp18.pdf https://meetingcpp.com/mcpp/slides/2018/Data-oriented%20desi...
- bob1029 5y ago
  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.

ianlevesque 5y ago

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.

Valgrim 5y ago
I wonder if this could be used to serve dynamic maps.
- durkie 5y ago
  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
  - bdon 5y ago
    This is the approach I took with http://github.com/protomaps/pmtiles http://github.com/protomaps/pmtiles , though it's optimized for the very specific use case of going from Z/X/Y integer coordinates to binary blobs, and takes shortcuts to accomplish that (fixed-width keys and root index page)
    - config_yml 5y ago
      Funny enough I was looking into mbtiles serverless solutions before I went to bed, now I start my day browsing HN and I find this clever solution. Love HN for this type of stuff :)
- blacha 5y ago
  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/ 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/ https://registry.opendata.aws/sentinel-2-l2a-cogs/

arafalov 5y ago

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.

rzzzt 5y ago
If you are interested in full-text search on the client, Lunr is also an option: https://lunrjs.com/docs/index.html https://lunrjs.com/docs/index.html
- tehbeard 5y ago
  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.
  - formerly_proven 5y ago
    This could be genuinely interesting for tools like e.g. sphinx-doc, which currently has a client-side search that does indeed ship the entire index to the client.
    - tehbeard 5y ago
      There's probably a dataset size tradeoff with small enough number of documents, but even then this could have the option of if db is < x MB total, fetch all in async task and then use that.
- joshuanapoli 5y ago
  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.

laurencerowe 5y ago

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 http://www.htslib.org/doc/tabix.html

Ultimatt 5y ago
now if only tabix and most hokey bioinformatics formats would die and just be replaced with a formal schema spec in SQLite...
- laurencerowe 5y ago
  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.

villasv 5y ago

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.

deleted 5y ago
[deleted]

rjeli 5y ago

Nice. Reminds me of Bellard’s https://vfsync.org/ https://vfsync.org/ . It’s file system pages served over http, to back his jslinux browser VMs

deleted 5y ago
[deleted]

simonw 5y ago

Using HTTP range requests like this is just SO clever.

simonw 5y ago

Pop open the network pane in the browser tools and try running this SQL query for a demo of how clever this is: select country_code, long_name from wdi_country order by rowid desc limit 100 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 https://twitter.com/simonw/status/1388933800445452290

WJW 5y ago
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?
- simonw 5y ago
  The clever part here is only fetching 50KB out of 680MB.
- ajfjrbfbf 5y ago
  > 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.
- watermelon0 5y ago
  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.
  - 5y ago

drtournier 5y ago

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 https://robinwinslow.uk/dont-ever-commit-binary-files-to-git

phiresky 5y ago
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?
laszlokorte 5y ago
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.
- iudqnolq 5y ago
  This is mostly correct. Git's core object model is snapshots, which can then optionally be compressed. That should be transparent though.

cozzyd 5y ago

If you just want static data, using jsroot or jsfive might be a better option.

jiofih 5y ago
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.
- cozzyd 5y ago
  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.

BMorearty 5y ago

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.

phiresky 5y ago
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 https://www.sqlite.org/vtab.html [2] https://github.com/phiresky/sql.js-httpvfs/blob/master/src/vtab.ts https://github.com/phiresky/sql.js-httpvfs/blob/master/src/v...
- deleted 5y ago
  [deleted]
nbevans 5y ago
"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.

diveanon 5y ago

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.

dreix 5y ago

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.

scottlamb 5y ago
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-wasm-dd22a976e2e149886e6e.wasm 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_format.md 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.

wheybags 5y ago

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!

cryptonector 5y ago

This is pretty brilliant.

tlb 5y ago

The question I had is answered by this line of code: xhr.setRequestHeader("Range", "bytes=" + from + "-" + to); I am a little surprised you can just do that. In https://github.com/phiresky/sql.js-httpvfs/blob/master/src/lazyFile.ts https://github.com/phiresky/sql.js-httpvfs/blob/master/src/l...

crazygringo 5y ago
Not all webservers support/enable it, so YMMV. But as long as you're dealing with a known server that does, then gravy!
- altfredd 5y ago
  > 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.
  - enneff 5y ago
    Depends on what’s being served. Any decent static file server should support it, but if the content is at all dynamically produced then the authors would have to think to implement it and rarely do.
  - crazygringo 5y ago
    I can't think of a specific one, but a decent proportion (maybe a quarter?) of HTTP downloads I attempt don't support resuming a partial download, therefore don't support Range. (I.e. resuming always starts from the beginning.) I would assume this is often because the site in question isn't using Apache etc. to serve a file directly, but is either essentially proxying it to some custom-built file serving service, or a script that processes/authenticates the file in some way, and they just never bothered to implement Range.
- stabbles 5y ago
  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

modeless 5y ago

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.

ponytech 5y ago

This is truly awesome. Very clever.

crazygringo 5y ago

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.

TimTheTinker 5y ago
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.
- csomar 5y ago
  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.
anonydsfsfs 5y ago
The write equivalent would be the PATCH method using a "message/byteranges" body: https://tools.ietf.org/id/draft-wright-http-partial-upload-01.html https://tools.ietf.org/id/draft-wright-http-partial-upload-0...
- crazygringo 5y ago
  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.
NoInkling 5y ago
Even if there was, I can't imagine your everyday static host ever supporting it.

banana_giraffe 5y ago

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.

killingtime74 5y ago
This one? https://rogerbinns.github.io/apsw/ https://rogerbinns.github.io/apsw/
- banana_giraffe 5y ago
  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 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.
  - killingtime74 5y ago
    Thank you!

tedk-42 5y ago

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.

th0ma5 5y ago

Searching the Common Crawl does similar byte level access to S3 based on a smaller index of indexes. Really great, actually.

Procrastes 5y ago

I'm also impressed with the implementation for the blog itself. I love this sort of clean, version-tracked sort of implementation.

867-5309 5y ago

>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

roddds 5y ago
I thought the "static" part of "static file hoster" was clear enough.

sarak12070 5y ago

Watch dragon ball season 1 full https://animated2021.blogspot.com/2021/05/dragon-ball-season-1-full.html 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/ 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-movie-australia.html 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-scouts-making-cookie.html https://www.interestingnews.club/2021/05/virginia-girls-scou...

nsonha 5y ago

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.

Benjamin_Dobell 5y ago
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/ https://lunrjs.com/), it is fairly commonly used to implement search on static websites. e.g. https://squidfunk.github.io/mkdocs-material/ 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.
- nsonha 5y ago
  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.
  - masklinn 5y ago
    > I'm also curious about how this sqlite thing picks the correct range to load Indexes are usually btree, it finds what and where the relevant index is (probably from the schema queries), then goes trawling through the b-tree. That’s how db engines normally work, they don’t liberally go through the entire db contents. If there’s no index then it finds the start of the table and scans it sequentially (which is exactly what it sounds like).

mwcampbell 5y ago

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.

justinclift 5y ago

This is pretty awesome. Now if only GitHub Pages did IPv6 as well... :)

Seattle3503 5y ago

How close are we to hosting searchable torrent indices on IPFS?

bruhhh 5y ago

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!!!

IceWreck 5y ago

This is incredible ! Don't have a use case for this right now but am certainly saving this for later.

yoz 5y ago

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?

duskwuff 5y ago
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.
- phiresky 5y ago
  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.
singularity2001 5y ago
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.)
5y ago

graderjs 5y ago

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.

phiresky 5y ago
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.
- f430 5y ago
  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

hutrdvnj 5y ago

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)?

willvarfar 5y ago
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.

winrid 5y ago

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?

philshem 5y ago
No, see here, for example https://news.ycombinator.com/item?id=27018194 https://news.ycombinator.com/item?id=27018194
- winrid 5y ago
  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.
  - ric2b 5y ago
    For most filesystems it should be no issue to seek directly to a specific offset on a file, it's just like accessing an array, if you know where it starts and the offset you just need to add them and tell the disk to read that address.

iveqy 5y ago

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.

TedDoesntTalk 5y ago

This is great but wish it had write ability, not just read only.

isoprophlex 5y ago

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!

slver 5y ago

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.

dawe35 5y ago

Hi, I'm working on SkySQL, maybe it's useful for you: https://github.com/upshot-tech/SkySQL https://github.com/upshot-tech/SkySQL

singularity2001 5y ago

>>> 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.

bambax 5y ago

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.

mFixman 5y ago

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?

nsonha 5y ago
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.

tlarkworthy 5y ago

works on ObservableHQ https://observablehq.com/@tomlarkworthy/phiresky-sqlite-query https://observablehq.com/@tomlarkworthy/phiresky-sqlite-quer...

irae 5y ago

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!

sztanko 5y ago

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.

aflag 5y ago

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.

aasasd 5y ago
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.
- aflag 5y ago
  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.
  - aasasd 5y ago
    Well, every database already optimizes disk access (at least until the recent years with the ‘just add SSDs’ attitude). However, they tend to assume that indexes should be loaded into memory. For this use-case, you'd want a database that can use indexes themselves from disk and treat them like partitioned storage: e.g. when reading data for years 2019 to 2021, only request parts corresponding to that, and not previous years. Dunno whether SQLite can have indexes partially in memory—with its niche of low-end devices and apps, it's quite possible that it can. Actually, this sort of partial access (i.e. partitioning) is rather easy to implement by addressing separate data files by name, instead of using numeric ranges into a database. Basically just put the data into files named by the years (in my example); or bucket the data into chunks of arbitrary size and use the chunks as files. Elementary to extend this to multiple fields in the index. In short, partitioning based on actual field values can be much easier in the static-http approach than using opaque ranges. Probably also more effective if something like http2 allows requesting several files in one request—since you can avoid requesting too little or too much.

nanna 5y ago

Hello new paradigm.

whoomp12342 5y ago

stahp, you gonna get gh pages shut down

shkkmo 5y ago

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

Arnavion 5y ago

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/2d2622a1c9934719ce65b1fc61503e32b36eea02/src/solve/web_reader.rs https://github.com/Arnavion/fac-rs/blob/2d2622a1c9934719ce65... [2]: https://github.com/Arnavion/fac-rs/blob/2d2622a1c9934719ce65b1fc61503e32b36eea02/src/solve/zip.rs https://github.com/Arnavion/fac-rs/blob/2d2622a1c9934719ce65...

pmarreck 5y ago

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

skyde 5y ago

this is genius. I love it.

diedyesterday 5y ago

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.

niutech 5y ago

For similar results, you can use SQL with IndexedDB running fully client-side: https://github.com/agershun/alasql https://github.com/agershun/alasql