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

161–170 of 231 posts

Re: Why SQLite Uses Bytecode

#161

Post by galaxyLogic »

mfoc wrote: post #151
bryancoxwell wrote: post #77

Earlier quoted context omitted.

I don’t doubt the author, but what is it that makes rendering a tree of objects to a table a difficult problem? Is that not what browsers do when they render a table element?

Quote from the article: "A tree-of-objects representation is more difficult to publish in a human-readable form. The objects that comprise the tree tend to all be very different, and thus it is tricky to come up with a consistent and simple table representation with which to display the objects. Any any such table representation that you do come up with would almost certainly have more than six columns, probably many…

Congratulations for your first comment!

What I want to do is represent my tree-structure as a table in a relational database and then be able to efficiently get the tree structure back by transforming the table-representation back into a tree.

Further I would like to do that in plain standard SQL. This must be a common problem, any documented solutions out there?

Re: Why SQLite Uses Bytecode

#162

Post by jjice »

andruc wrote: post #148
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.)

Faster to interpret than what?

I assume they meant faster to interpret than a tree of objects, since that's the other concept discussed in the article.

Re: Why SQLite Uses Bytecode

#163

Post by 0x457 »

usrusr wrote: post #95
gpderetta wrote: post #73

Earlier quoted context omitted.

There is also the option of native code generation from bytecode at install time as opposed of runtime.

Aka missing out on all the delicious profiling information approaches with later translation enjoy. There's no simple best answer.

I'm probably wrong, but I always thought for platforms like .Net and JVM, AoT delivers the same performance as JIT in most cases. Since a lot of information is available before runtime, unlike JS where VM always needs to be read, ditch optimized byte code and go back to the whiteboard.

Re: Why SQLite Uses Bytecode

#164

Post by astrobe_ »

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.

I think we already kind of have that already; one can prepare a query/statement and then use it multiple times. Regex engines also do that, except that in the case of SQlite one can bind different parameter values.

Programmers worried about SQL lexing/parsing times can compile their most used queries once for all at programmer startup. Plus, one can sometimes break a query with annoyingly variable parts into smaller queries glued with SQLite API calls.

Re: Why SQLite Uses Bytecode

#165

Post by astrobe_ »

pdubroy wrote: post #139

I think most people associate bytecode VMs / interpreters with general-purpose programming languages, but it's a surprisingly useful concept in other contexts. Sometimes bytecode VMs appear in unexpected places! A few that I'm aware of: - eBPF, an extension mechanism in the Linux kernel - DWARF expression language, with interpreters in debuggers like GDB and LLDB - The RAR file format includes a bytecode encoding for…

Also regular expression engines.

Re: Why SQLite Uses Bytecode

#166

Post by alex_smart »

naasking wrote: post #126
alex_smart wrote: post #83

Earlier quoted context omitted.

Consider evaluating an expression like "col1 + col2 == col3" A tree based evaluator has to do something like - for (int i = 0; i whereas a bytecode based evaluator is able to run something equivalent to - for (int i = 0; i

You still have to branch on opcode selection which you're omitting in your translation. Branching on "expression type" and column type in your first example is also unnecessary. Bytecodes have different opcodes to operate on different types and different arities, so in both cases you have only one unpredictable branch for each operation/opcode. The main benefit of bytecodes is then cache friendliness, by removing all…

> Branching on "expression type" and column type in your first example is also unnecessary

It’s not?

Re: Why SQLite Uses Bytecode

#167

Post by mfoc »

galaxyLogic wrote: post #161
mfoc wrote: post #151

Earlier quoted context omitted.

Quote from the article: "A tree-of-objects representation is more difficult to publish in a human-readable form. The objects that comprise the tree tend to all be very different, and thus it is tricky to come up with a consistent and simple table representation with which to display the objects. Any any such table representation that you do come up with would almost certainly have more than six columns, probably many…

Congratulations for your first comment! What I want to do is represent my tree-structure as a table in a relational database and then be able to efficiently get the tree structure back by transforming the table-representation back into a tree. Further I would like to do that in plain standard SQL. This must be a common problem, any documented solutions out there?

Thank you.

Great question - you have touched on the key difference between a labeling scheme and an encoding scheme for tree data structures.

As mentioned previously, the tree is an abstract data type, that is to say, a conceptual model that defines the nodes in a tree, and their relationships.

To be able to evaluate a expression that processes a tree, one needs a labeling scheme. The purpose of a labeling scheme is to assign unique labels to each node in the tree and these labels must facilitate node ordering, and often (but not always) a labeling scheme will permit the reconstruction of the tree structure.

However, no labeling scheme captures the node type, names or the content stored at the nodes. For that we need an encoding scheme. An encoding scheme is constructed upon a labeling scheme and augments it with the information necessary to fully represent the tree in a table-like data structure. In answer to your question, it also permits the full transformation from the table representation to the original tree structure.

Thus, it sounds like what you are looking for is an encoding scheme.

There are many different labeling schemes out there for tree structure data, and virtually all of them can be augmented with additional information to construct a complete encoding scheme. Concerning documented solutions - I have not been active in this space for a number of years, so off the bat - I don't have a recommended documented solution to point you too.

But to help, I will put a link to my PhD thesis [1] which gives a more in-depth understanding of labeling schemes and encoding schemes for tree structured data with an example of a simple implementation of an encoding scheme enabling the full transformation from the table representation to the original tree structure (pages 5-9) and a survey of the advantages and disadvantages of existing labeling schemes concerning their usefulness to be part of an encoding scheme you could use in your solution (see chapter 2)

Caveat 1: My thesis was written in the context of updating dynamic (XML) trees but it addresses the transformation between tree and table data structures.

Caveat 2: The thesis was written 11 years ago, but every now and then I have kept in touch with the latest developments in the area, and to my knowledge, there have been no major developments since.

I hope it helps.

[1]: https://doras.dcu.ie/19316/

Re: Why SQLite Uses Bytecode

#168

Post by naasking »

alex_smart wrote: post #166
naasking wrote: post #126

Earlier quoted context omitted.

You still have to branch on opcode selection which you're omitting in your translation. Branching on "expression type" and column type in your first example is also unnecessary. Bytecodes have different opcodes to operate on different types and different arities, so in both cases you have only one unpredictable branch for each operation/opcode. The main benefit of bytecodes is then cache friendliness, by removing all…

> Branching on "expression type" and column type in your first example is also unnecessary It’s not?

It is unnecessary, only branching on expression operator type is strictly necessary. You're trying to abstract too much in your AST which yields an inefficient interpreter. I can invent an inefficient bytecode too, but that wouldn't be a correct evaluation of how fast bytecode interpretation could be when done right.

Re: Why SQLite Uses Bytecode

#170

Post by omoikane »

pdubroy wrote: post #139

I think most people associate bytecode VMs / interpreters with general-purpose programming languages, but it's a surprisingly useful concept in other contexts. Sometimes bytecode VMs appear in unexpected places! A few that I'm aware of: - eBPF, an extension mechanism in the Linux kernel - DWARF expression language, with interpreters in debuggers like GDB and LLDB - The RAR file format includes a bytecode encoding for…

I believe these fall under "interpreter pattern":

https://en.wikipedia.org/wiki/Interpreter_pattern

https://gameprogrammingpatterns.com/bytecode.html

https://wiki.c2.com/?InterpreterPattern

I first read about it from the "Design Patterns" book, which I would recommend to everyone.

Post reply on HN