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

191–200 of 231 posts

Re: Why SQLite Uses Bytecode

#191

Post by [deleted] »

asimpletune wrote: post #128
beeboobaa3 wrote: post #116

Earlier quoted context omitted.

> Bytecode dispatch is using less than 3% of the total CPU time, according to my measurements > compiling all the way down to machine code might provide a performance boost 3% or less This logic doesn't seem sound? Because the application now spends 3% on bytecode dispatch doesn't tell us anything about how long it would instead spend on e.g. interpreting SQL.

He’s saying in the best case scenario that 3% would go to 0. Therefore the reality would probably be even less.

[deleted]

Re: Why SQLite Uses Bytecode

#192

Post by AnthonyMouse »

cryptonector wrote: post #178
immibis wrote: post #156

Earlier quoted context omitted.

I stopped using Twitter because "Space Man" banned most of one political side. Maybe if you didn't notice that, you're in a bubble?

I've not been following this stuff. Whom did Musk ban?

Like most large social media sites, pre-Musk Twitter had some combination of algorithms and bureaucracy that act as a chaos monkey to shadowban and suspend accounts apparently at random, often with an inability to comprehend satire or under incoherent or undisclosed pretexts. The site's users and staff were predominantly left-leaning, so right-leaning accounts were disproportionately the victims of these false positives because of human bias in which posts are flagged and how they're subsequently moderated.

Musk bought the site under a claim of doing something about the bias after Twitter suspended the account of a right-leaning satire site. Many of the existing users were displeased by this, because they liked having a site whose moderation system was biased in their favor, so some of them left. Meanwhile new right-leaning accounts were created as you might expect. This affected the ideological balance of the site, so even though it's still somewhat left-leaning it's less than before. And now when the drunk chaos monkey suspends an account on the left, people are finding new satisfaction in their ability to blame Musk in particular.

Re: Why SQLite Uses Bytecode

#193

Post by dagss »

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.

1) I think a simple new kind of query hint could go a long way: Declare a table as being "infinitely large" from the perspective of the query planner.

So, if a query caused a full table scan or similar against the table, it's an error, regardless of the actual content.

A lot of "typical" backend code would then simply require you to make the right indices you need to support your queries, and the query planner would be forced to use those indices in all situations.

2) You can already sort of do what you say; that "higher level imperative language" is available simply by breaking your query up into smaller chunks.

At least in MS-SQL (which is what I know), simply do

    declare @tmp1 as table (...)
    insert into @tmp1 ...
    declare @tmp2 as table (...)
    insert into @tmp2 ... from @tmp1 join ...
and so on; if you make each of those steps small enough you pretty much have the imperative language.

3) That said, I think SQL is a wonderful idea, I am also super-productive in implementing business logic in it; but it is a horrible language; the learning curve is so much higher than it needs to be and so many silly pitfalls. So fully support pushes for better languages.

Re: Why SQLite Uses Bytecode

#194

Post by tristor »

galaxyLogic wrote: post #157
fancyfredbot wrote: post #79

Earlier quoted context omitted.

For simple functions which are not called repeatedly you have to invert this list - interpreted code is fastest and compiling the code is slowest. The complied code would still be faster if you excluded the compilation time. It's just that the overhead of compiling it is sometimes higher than the benefit.

I wonder in actual business scenarios isn't the SQL fully known before an app goes into production? So couldn't it make sense to compile it all the way down? There are situations where the analyst enters SQL into the computer interactively. But in those cases the overhead of compiling does not really matter since this is infrequently done, and there is only a single user asking for the operation of running the SQL.

> I wonder in actual business scenarios isn't the SQL fully known before an app goes into production? So couldn't it make sense to compile it all the way down?

You would hope, but no that's not reality. In reality most of the people "writing SQL" in a business scenario don't even know SQL, they're using an ORM like Hibernate, SQLAlchemy, or similar which is dynamically generating queries that likely subtly change every time the application on top changes.

Re: Why SQLite Uses Bytecode

#195

Post by fancyfredbot »

galaxyLogic wrote: post #157
fancyfredbot wrote: post #79

Earlier quoted context omitted.

For simple functions which are not called repeatedly you have to invert this list - interpreted code is fastest and compiling the code is slowest. The complied code would still be faster if you excluded the compilation time. It's just that the overhead of compiling it is sometimes higher than the benefit.

I wonder in actual business scenarios isn't the SQL fully known before an app goes into production? So couldn't it make sense to compile it all the way down? There are situations where the analyst enters SQL into the computer interactively. But in those cases the overhead of compiling does not really matter since this is infrequently done, and there is only a single user asking for the operation of running the SQL.

I didn't mean to imply that compilation never makes sense, I'm only pointing out that it isn't always the fastest way of executing a query

In situations where you have a limited number of queries and these are used repeatedly then some kind of cache for the complied code will be able to amortise the cost of compilation.

I certainly agree that a situation where an analyst enters SQL manually is a weird niche and not common. However most applications can dynamically construct queries on behalf of users and so getting a good hit rate on your cache of precompiled queries isn't a certainty.

Re: Why SQLite Uses Bytecode

#196

Post by wglb »

kayodelycaon wrote: post #129
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…

For those that aren’t familiar, IBM i is ye olde A/S 400. To be fair, RPG has been continuously updated and the version I’ve seen has Java integration. It’s somewhat amusing that a single developer using Python can run circles around entire teams of RPG programmers. Technology marches on. :)

Well, having programmed RPG professionally, there is no question that a python programmer would clock any RPG programmer. RPG is a terrible way to program.

Re: Why SQLite Uses Bytecode

#197

Post by wglb »

blacklion wrote: post #125
wglb wrote: post #120

Earlier quoted context omitted.

I'm curious. Would you have a pointer to the documentation of PRG language?

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.

Re: Why SQLite Uses Bytecode

#198

Post by euroderf »

zadokshi wrote: post #92
euroderf wrote: post #82

Doesn't the Go language also execute bytecode ? There's gotta be a hyperefficient hybrid lurking in there somewhere.

go compiles to binary files and libraries. it’s more like c than Java

But it has an intermediate stage of "Go assembler", which is what I misremembered.

Re: Why SQLite Uses Bytecode

#199

Post by JonChesterfield »

temporarely wrote: post #119
SQLite wrote: post #96

Earlier quoted context omitted.

Performance analysis indicates that SQLite spends very little time doing bytecode decoding and dispatch. Most CPU cycles are consumed in walking B-Trees, doing value comparisons, and decoding records - all of which happens in compiled C code. Bytecode dispatch is using less than 3% of the total CPU time, according to my measurements. So at least in the case of SQLite, compiling all the way down to machine code might…

A while back was musing if it was possible to come up with something resembling the instruction set for a CPU for an abstract relational-engine. Is this basically what SQLite is doing with bytecodes?

I think yes, essentially. Bytecode running on a software interpreter is the same thing as machine code running on a silicon interpreter. Probably slower, probably a different ISA, but very much the same idea.

The OP suggests the sqlite bytecode also has arithmetic & control flow in it which you might want to exclude in other settings. There's a parallel with cisc vs risc instruction sets here, and to calls into a compiler runtime vs expanding instructions into larger numbers of more primitive ones in place.

@rkrzr there's a circular definition in your "no" - if "CPU" means "an interpreter that executes instructions simpler than SQL" then this is indeed not an instruction set. If "CPU" means "interpreter of a given ISA" then it could be. The virtual machine in the sqlite codebase is the definition of the CPU for this instruction set. Unless you want to define CPU as exclusive of software implementations of interpreters.

Re: Why SQLite Uses Bytecode

#200

Post by JonChesterfield »

titzer wrote: post #130
SQLite wrote: post #96

Earlier quoted context omitted.

Performance analysis indicates that SQLite spends very little time doing bytecode decoding and dispatch. Most CPU cycles are consumed in walking B-Trees, doing value comparisons, and decoding records - all of which happens in compiled C code. Bytecode dispatch is using less than 3% of the total CPU time, according to my measurements. So at least in the case of SQLite, compiling all the way down to machine code might…

Part of the benefit of compiling bytecode (or anything) is specializing code to the context (types, values, etc) in which it appears. While I don't doubt your analysis, it could be the case that compiled C code in question is full of branches that can be folded away when specialized to the context of the query, such as the structure of the rows, the type and values of columns, etc. Basically all of what you are sayin…

There's usually a cost to shuttling data between bytecodes too. When two are fused together the second can lift the data from wherever the first wanted to leave it, as opposed to routing through a fixed location. Might be what you mean by shortcutting dataflow?

Also doing control flow in bytecode is usually slower than doing it in the native code.

I wonder if the context in which the instructions occur is sufficiently finite in sqlite for ahead of specialisation of the bytecode to be better. That is, the program you're operating on isn't known until JIT time, but the bytecode implementations are. SQL should correspond to an unusually specific set of operations relative to a general purpose language implementation.

The compiler will notice some values are constant when working with the bytecode. It can know ahead of time which arguments correspond to folding branches within the bytecode instructions and specialise correspondingly. If that works, you've emitted a sequence of calls into opcodes which are less branchy than they would otherwise be, at which point the opcode implementations start to look like basic blocks and a template JIT to machine code beckons.

Post reply on HN