Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why SQLite Uses Bytecode

sqlite.org

Post reply on HN
Print view View original

211–220 of 231 posts

Re: Why SQLite Uses Bytecode

#211

Post by TeMPOraL »

thayne wrote: post #62
manx wrote: post #60

I'm wondering if one could write this bytecode directly (or with a higher level imperative language) instead of SQL. Often, the programmer knows exactly which index lookups need to happen in a loop, while it seems like a burden to express that in SQL. This might also be an opportunity to create a different type safe dsl for database access.

I was wondering the same thing. And in particular if a new query language that avoided many of the pitfalls of SQL could compile down to that bytecode and avoid having to deal with SQL as an intermediate representation. Also, if you can compile to bytecode ahead of time, then that could save the time needed to parse the text of a sql query to bytecode at runtime.

> Also, if you can compile to bytecode ahead of time, then that could save the time needed to parse the text of a sql query to bytecode at runtime.

That's exactly how those "prepared statements" work in SQLite - you get a handle to a piece of bytecode, and you can call it with different parameters.

Re: Why SQLite Uses Bytecode

#212

Post by pizlonator »

iainmerrick wrote: post #206
pizlonator wrote: post #134

That’s awesome, I didn’t know SQLite had a bytecode. Based on my experience writing interpreters, I know that bytecode is faster to interpret. (Source: I wrote JavaScriptCore’s interpreter and it’s optimizing JITs. I’ve also worked on other language implementations. I’ve seen the AST vs bytecode thing play out more than once.)

Maybe I'm missing something, but the bytecode approach seems really obviously better, just from a memory usage and locality point of view. Scanning an array of bytes or words is obviously going to be faster than traversing a tree of pointers. So I'd be surprised to find a serious language implementation using a pure AST in its interpreter, without at the very least flattening it to an array! Edit to add: of course th…

It’s fine to use an AST interpreter if you pair it with really great JITs.

That has its own problems though - using an AST as a shared source of truth for your JIT compilers is cumbersome for implementing stuff like OSR. But from a perf standpoint, it’s probably fine.

Also - say you want to optimize just for startup time, like if the code you’re running has minimal looping or reexecution. Then AST is better because you skip a step before first execution.

Re: Why SQLite Uses Bytecode

#213

Post by ngcc_hk »

wglb wrote: post #197
blacklion wrote: post #125

Earlier quoted context omitted.

Oooops, it is IBM RPG, not PRG! My bad! There are some links in Wikipedia. I never used it, but only read big thread about SQL vs RPG on Russian-speaking forum, and there was a ton of examples from person who works with IBM i platform in some big bank. Basic operations look like SQLite bytecodes: open table, move cursor after record with key value "X", get some fields, update some field, plus loops, if's, basic arith…

Ah. I did RPG on a system 33, a precursor to the AS 400.

32, 34 or 36? or 38 which is very different and the real R system that leads to as/400 or I … s/33?

Re: Why SQLite Uses Bytecode

#214

Post by tanelpoder »

lolinder wrote: post #102
tanelpoder wrote: post #54

Earlier quoted context omitted.

4. lots of small building blocks of static machine code precompiled/shipped with DB software binary, later iterated & looped through based on the query plan the optimizer came up with. Oracle does this with their columnar/vector/SIMD processing In-Memory Database option (it's not like LLVM as it doesn't compile/link/rearrange the existing binary building blocks, just jumps & loops through the existing ones in the req…

Isn't what you're describing just an interpreter, bytecode or otherwise? An interpreter walks through a data structure in order to determine which bits of precompiled code to execute in which order and with which arguments. In a bytecode interpreter the data structure is a sequential array, in a plain interpreter it's something more complicated like an AST. Is this just the same as "interpret the query plan" or am I…

It interprets where it needs to jump and then jumps to the precompiled binary machine code locations that are executed natively on the CPU, no interpretation going on (I guess it's conceptually something like instruction traces inside the CPU trace cache, but done at higher level). These precompiled building blocks are shipped in separate libraries, one library for each CPU architecture on a platform (SSE4.2, AVX, AVX2, AVX-521 on AMD64 and other SIMD architectures on other platforms that Oracle supports). Oracle dynamically loads the correct library matching the CPUs capability during the startup and starts jumping there as needed.

So this is not bytecode interpretation, it's native machine code executed directly on CPU whenever the SQL exec engine decides to jump there. This is different from, say Apache Impala that compiles new LLVM machine code for each query execution for the query's scanning tight loops.

Edit: I guess why I see this as not just not regular bytecode interpretation (I don't actually know that much about it in general), is that these building blocks can include various loops (and can do their thing on entire vectors of data), so looks like they can push quite a bit of complexity into the machine code sections, before returning back to the normal interpreted AST/opcode land.

Re: Why SQLite Uses Bytecode

#215

Post by chuckadams »

whartung wrote: post #172
pjmlp wrote: post #48

Earlier quoted context omitted.

When one does digital archeology is it quite common to see Assembly referred to as bytecode, when the CPUs are actually interpreters written in microcode. Another example, all the Xerox PARC workstations, which loaded the respective interpreter (Smalltalk, Interlisp, Mesa, Mesa/Cedar) into the CPU as first step during the boot process.

According to 5s on Google, the x86 has always been microcoded. I guess the argument is that “machine language” is the public API of the CPU, and “assembly language” is the higher level script used to, mostly, directly create machine language. Is Intel microcode able to be changed by anyone? I understand that even CPUs get field updates nowadays.

Microcode updates are encrypted, and only Intel has the key. There are exploits to extract the key, but otherwise you're pretty much locked out.

I don't know a whole lot about microarchitecture, but from my understanding, it's not possible to modify microcode's actual uOps in software, it's the translation from assembly to microcode that's being patched in updates.

Re: Why SQLite Uses Bytecode

#216

Post by nraynaud »

TachyonicBytes wrote: post #110
nraynaud wrote: post #72

Earlier quoted context omitted.

I'm puttig my wish list here: - be able to put the projection in a varable and reuse it (and I think orm people might love it) - have a quick way to forward the the non-aggregated fields of projection to a group by (maybe with the aforementionned variables)

The DuckDB API I was talking above seem to already meet your use-cases? - Does this[1] solve the group by wish? - Depending on what you mean by projection, maybe this[2] or this[3]? [1] https://duckdb.org/docs/api/python/relational_api#aggregatee... [2] https://duckdb.org/docs/api/python/relational_api#projectexp... [3] https://duckdb.org/docs/api/python/expression#column-express...

that's really great!

Re: Why SQLite Uses Bytecode

#217

Post by mharig »

deanishe wrote: post #184
yayr wrote: post #118

Earlier quoted context omitted.

yeah, these accounting table field names have not changed since around 30 years, which is not necessarily a bad thing... for a human readable view of this you can look e.g. here https://docsfortec.com/sap/S4/tables/ACDOCA

They're a bit of a bilingual mess. Did they start out with German table names and decide to give new tables English names at some point?

Out of the guts, the only maybe english abbrev is docln = document line (?). Referring to the example, not the link.

Re: Why SQLite Uses Bytecode

#218

Post by HanyouHottie »

TeMPOraL wrote: post #210
wruza wrote: post #81

Earlier quoted context omitted.

I was advocating for it for decades, but everyone dismisses it with “you don’t know better than rdbms”. That’s almost a religion. Despite the fact that most of the tables most people have are never any big (except for a few oltps that you ought to leave to specific sql server wizards anyway) and you usually do have the idea how it should work. SQL is a cool solution for a set of problems that has a very non-zero xor…

I'm wondering the opposite - could RDBMS know better than programmer how to structure the program ? The other day I had this realization, that if I squint, quite a lot of code I see and write could be seen as database tables, prepared statements, and specialized indexes. In particular, every time I use an associative table (or several) to speed up access to data along particular dimension (like X/Y coordinates in the…

You might find SpacetimeDB interesting.

https://spacetimedb.com/

Re: Why SQLite Uses Bytecode

#219

Post by xymostech »

atombender wrote: post #187
xymostech wrote: post #152

Earlier quoted context omitted.

The original TeX Fonts stored their metrics in TFM (short for TeX font metrics) files, which contains a bytecode interpreter for calculating ligatures and kerning between characters. I learned about that when I tried reading the files myself. From what I can tell, modern fonts using OpenType just have tables to accomplish something similar now, in the form of the GSUB and GPOS tables? Documentation for the TFM format…

TrueType (and OpenType, which is an evolution of TT) absolutely includes a bytecode instruction set: https://developer.apple.com/fonts/TrueType-Reference-Manual/...

Oh yes, thank you for the link to that! Looks like that is an instruction set for representing the font glyphs themselves? I was talking about the instruction set in TFM which is for representing meta information, like ligatures and kerning between glyphs, and not for the actual glyphs. The glpyhs for the original TeX fonts are described using Metafont which is an interpreted language.

Re: Why SQLite Uses Bytecode

#220

Post by nurple »

manx wrote: post #60

I'm wondering if one could write this bytecode directly (or with a higher level imperative language) instead of SQL. Often, the programmer knows exactly which index lookups need to happen in a loop, while it seems like a burden to express that in SQL. This might also be an opportunity to create a different type safe dsl for database access.

You should watch this asianometry video on the birth of SQL, very interesting, and in fact a functional approach, based on relational algebra and tuple relational calculus, was originally what the father of the concept intended for interacting with the db. Other IBM engineers formulated the SQL language over that.

The precursors to sql rdbms, and the war over competing concepts, were also quite thought provoking.

https://www.youtube.com/watch?v=z8L202FlmD4

Post reply on HN