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

41–50 of 231 posts

Re: Why SQLite Uses Bytecode

#41

Post by branko_d »

paulddraper wrote: post #34
wolf550e wrote: post #29

The page is the result of this exchange on Twitter: https://twitter.com/gorilla0513/status/1784756577465200740 I was surprised to receive a reply from you, the author. Thank you :) Since I'm a novice with both compilers and databases, could you tell me what the advantages and disadvantages are of using a VM with SQLite? https://twitter.com/DRichardHipp/status/1784783482788413491 It is difficult to summarize the advan…

There are three approaches: 1. interpreted code 2. compiled then interpreted bytecode 3. compiled machine code The further up, the simpler. The further down, the faster.

> 2. compiled then interpreted bytecode

You can also compile to bytecode (when building), and then compile that bytecode to the machine code (when running). That way, you can take advantage of the exact processor that is running your program.

This is the approach taken by .NET and Java, and I presume most other runtime environments that use bytecode.

Re: Why SQLite Uses Bytecode

#42

Post by slaymaker1907 »

userbinator wrote: post #8

The problem of rendering a tree-of-objects as a table is sufficiently difficult that nobody does it, as far as I know. Hence, no tree-of-objects database engine provides the level of detail in their "EXPLAIN" output that SQLite provides. I believe Microsoft SQL Server uses an object tree internally, and yet its query plan output is a table: https://learn.microsoft.com/en-us/sql/t-sql/statements/set-s...

It can also execute a query incrementally. In fact, certain features rely on this behavior. “Watch live data” (in SSMS) for extended events is actually an infinite table-valued function. It’s not exactly rocket science to do in a database, you just need to model data sources and operators as iterators.

Re: Why SQLite Uses Bytecode

#43

Post by kragen »

pjmlp wrote: post #39
runlaszlorun wrote: post #25

Earlier quoted context omitted.

And Pascal p-code! Not the first, I’ve heard, but I believe it’s close to being the first.

One of the first was Burroughs B5000, https://en.wikipedia.org/wiki/Burroughs_Large_Systems It used an almost memory safe systems language, ESPOL, zero Assembly, all CPU capabilities are exposed via intrisics, one of the first recoded uses of unsafe code blocks, there was tagging and capabilities support, the CPUs were microcoded. All of this in 1961, a decade before C came to be. ESPOL was quickly replaced by NEWP,…

the b5000 was one of the first non-virtual stack machines, but its instruction set isn't any more of a virtual machine than the 8088's or the pdp-10's. there were a number of interpreted stack languages in the 50s, though not nearly as many as there would be later

Re: Why SQLite Uses Bytecode

#44

Post by thewakalix »

megadal wrote: post #28
lifthrasiir wrote: post #23

Earlier quoted context omitted.

You don't need one, Lua is another example where no AST is ever generated. In some sense the resulting bytecode closely corresponds to the AST that would have been generated though.

Genuinely asking as parsing without an AST is something I've never seen explained: How do you go from source code to bytecode without an AST? Isn't the bytecode just a flattened representation of an AST obtained by some sort of tree traversal? This seems to imply an AST is involved in the generation of the bytecode

See also: DOM versus streaming.

Re: Why SQLite Uses Bytecode

#46

Post by coolandsmartrr »

wolf550e wrote: post #29

The page is the result of this exchange on Twitter: https://twitter.com/gorilla0513/status/1784756577465200740 I was surprised to receive a reply from you, the author. Thank you :) Since I'm a novice with both compilers and databases, could you tell me what the advantages and disadvantages are of using a VM with SQLite? https://twitter.com/DRichardHipp/status/1784783482788413491 It is difficult to summarize the advan…

I am amazed that the author (D Richard Hipp) made an effort to find and respond to a tweet that was (1) not directed/"@tted" at him or (2) written in his native language of English (original tweet is in Japanese[1]).

[1] https://twitter.com/gorilla0513/status/1784623660193677762

Re: Why SQLite Uses Bytecode

#47

Post by masklinn »

_flux wrote: post #37
winrid wrote: post #17

Earlier quoted context omitted.

Yeah, but nobody is seriously considering that unless maybe for huge prepared statements. The argument is usually bytecode vs parser and associated data structures.

PostgreSQL is not only considering it, they're doing it! https://www.postgresql.org/docs/current/jit-reason.html I don't have personal experience on it, but I've read that in practice it's not worth the effort—at least not yet. Apparently there are some issues with it and it barely speeds up queries (except perhaps certain ones?). I imagine this could be in big part because LLVM is not really a good fit for JIT where…

Yeah my experience of the pg jit is mostly negative, it’s quite slow and it has a hard time estimating the cost of interpreted v compilation + compiled execution so more often than not it’s actively detrimental. It might fare better if you make heavy use of a limited number of prepared statements.

Re: Why SQLite Uses Bytecode

#48

Post by pjmlp »

kragen wrote: post #43
pjmlp wrote: post #39

Earlier quoted context omitted.

One of the first was Burroughs B5000, https://en.wikipedia.org/wiki/Burroughs_Large_Systems It used an almost memory safe systems language, ESPOL, zero Assembly, all CPU capabilities are exposed via intrisics, one of the first recoded uses of unsafe code blocks, there was tagging and capabilities support, the CPUs were microcoded. All of this in 1961, a decade before C came to be. ESPOL was quickly replaced by NEWP,…

the b5000 was one of the first non -virtual stack machines, but its instruction set isn't any more of a virtual machine than the 8088's or the pdp-10's. there were a number of interpreted stack languages in the 50s, though not nearly as many as there would be later

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.

Re: Why SQLite Uses Bytecode

#49

Post by ojosilva »

Scaevolus wrote: post #27
anon291 wrote: post #20

Earlier quoted context omitted.

Stack-based VMs, like SQLite's (I think), ARE trees. A stack based VM's bytecode (without DUP and POP) is just the post-order depth-first traversal of the corresponding expression tree. With DUP you have a connected acyclic DAG. With POP you have an acyclic DAG with one or more components. With loops you have a full graph. When looked at this way, a VM makes the most sense actually because a pointer-heavy tree implem…

SQLite's VM is register-based, not stack-based.

Does SQLite's VM have an API? I mean, one where I can build and issue opcodes into directly.

Re: Why SQLite Uses Bytecode

#50

Post by eklavya »

alex_smart wrote: post #35

I recently implemented my own expression evaluator in java for in-memory data frames, and once you think about doing that deeply, you very quickly understand the need for bytecode. If you directly evaluate the expression using a tree representation, you basically have to do a whole lot of branching (either via switch statements or polymorphism) for every single line of useful operation. Yes, the branch predictor kick…

Bytecode will only impact packing, so more efficient ram, cache and cpu wise. But I don't understand how it would help with branching? You still have to make the same decisions? As in the bytecode executor still needs to do differnt things based on the op code, its not in hardware.
Post reply on HN