4 ms·

A practical relational query compiler in 500 lines of code

95 points by ot 10y ago

gravypod 10y ago
I don't like the idea of executing "real" code in a database. An DB's parser shouldn't allow a query make network connections/IO access.
- makmanalp 10y ago
  Well, in an actual system, this would be sandboxed and stuff. If this all sounds dubious, consider: In modern databases these days, most everything already lives in RAM, and CPUs are getting incredibly fast, meaning most of the time the CPU is sitting there doing nothing, and the bottleneck is bringing stuff up and down from memory into the CPU cache(s) and registers. There is orders of magnitude difference in the speed of accessing stuff from registers vs L1/L2 vs main memory. Now, usually, for sequential access to memory, the hardware is smart and will pre-fetch stuff into the cache, causing near-optimal performance. The more random access to memory you have in your code, the more cache misses, and the worse the performance. Now, imagine having a function call! This means swapping the stack, code, variables all in and out. And often this is a virtual pointer (e.g. MySpecialProcessor->next_tuple()) which is even more indirection and more cache misses. On top of that, there's branches: abstracted code has if's and special cases for many situations that we may already know will never happen in our current query, so why have them? And branches are also bad for other reasons to do with pipelining in modern CPUs. Additionally, the code you're using is competing for space in the upper levels of the memory hierarchy with the data you're trying to process. Meaning if your code is large, then parts of it need to be paged in and out while you loop through your data, which again, is sloooooooow. If this sounds like hyper-optimization, consider that this is the inner-most, hottest loop in the entire database software, and gets called millions and billions of times per second. Trust me when I say this does make orders of magnitude differences overall. For a toy example, check out: https://www.naftaliharris.com/blog/2x-speedup-with-one-line-of-code/ https://www.naftaliharris.com/blog/2x-speedup-with-one-line-... Also we'll see this method being used to some degree in Apache Spark: https://databricks.com/blog/2016/05/23/apache-spark-as-a-compiler-joining-a-billion-rows-per-second-on-a-laptop.html https://databricks.com/blog/2016/05/23/apache-spark-as-a-com...
  - gravypod 10y ago
    I'm not saying the performance isn't important in this case, I'm saying it's an inherently unsafe implementation. I can't think of a single way to secure the system if the password falls to the wrong hands. I'd much rather have this done in a query language and have the queries cached. A compiled query should be very small (maybe only a few instructions) and if done right could be very quick without any fancy meta evaluation. You'd also get "some" way to sandbox the system inherently. The code should only be able to access your data and if you design a language around that idea your have something infinitely more safe then something that isn't.
- pulisse 10y ago
  The query engine isn't executing arbitrary code. The queries are written in a DSL and transpiled.
  - jamii 10y ago
    The DSL is compiled to Julia, and may contain arbitrary Julia expressions which are spliced into the result. Relations may also contain arbitrary Julia datatypes. Eg in: @query begin state() => current_state x in 1:num_x y in 1:num_y is_cleared = @exists cleared($x,$y) is_mine = @exists mine($x,$y) mine_count(x, y) => count cell_node = @match (current_state, is_mine, is_cleared, count) begin (:game_in_progress, _, true, 0) => button("_") (:game_in_progress, _, true, _) => button(string(count)) (:game_in_progress, _, false, _) => button(Dict(:onclick => @event clicked(x,y)), "X") (:game_won, true, _, _) => button("") (:game_lost, true, _, _) => button("") (_, false, _, _) => button(string(count)) other => error("The hell is this: $other") end return cell(x,y) => cell_node end @match is a Julia macro, button, string, Dict etc are Julia functions and cell_node is a DOM node. The point of Imp is to be able to write entire apps without having to context switch between multiple languages and systems. It needs to have a full-blown language in the database because there isn't going to be an application or frontend tier.
    - gravypod 10y ago
      That sounds like playing with a metal forgery and the only protection you have on is oven mitts.
threepipeproblm 10y ago
Thank you very much for this.

95 points by ot 10y ago

I don't like the idea of executing "real" code in a database. An DB's parser shouldn't allow a query make network connections/IO access.

makmanalp 10y ago
Well, in an actual system, this would be sandboxed and stuff. If this all sounds dubious, consider: In modern databases these days, most everything already lives in RAM, and CPUs are getting incredibly fast, meaning most of the time the CPU is sitting there doing nothing, and the bottleneck is bringing stuff up and down from memory into the CPU cache(s) and registers. There is orders of magnitude difference in the speed of accessing stuff from registers vs L1/L2 vs main memory. Now, usually, for sequential access to memory, the hardware is smart and will pre-fetch stuff into the cache, causing near-optimal performance. The more random access to memory you have in your code, the more cache misses, and the worse the performance. Now, imagine having a function call! This means swapping the stack, code, variables all in and out. And often this is a virtual pointer (e.g. MySpecialProcessor->next_tuple()) which is even more indirection and more cache misses. On top of that, there's branches: abstracted code has if's and special cases for many situations that we may already know will never happen in our current query, so why have them? And branches are also bad for other reasons to do with pipelining in modern CPUs. Additionally, the code you're using is competing for space in the upper levels of the memory hierarchy with the data you're trying to process. Meaning if your code is large, then parts of it need to be paged in and out while you loop through your data, which again, is sloooooooow. If this sounds like hyper-optimization, consider that this is the inner-most, hottest loop in the entire database software, and gets called millions and billions of times per second. Trust me when I say this does make orders of magnitude differences overall. For a toy example, check out: https://www.naftaliharris.com/blog/2x-speedup-with-one-line-of-code/ https://www.naftaliharris.com/blog/2x-speedup-with-one-line-... Also we'll see this method being used to some degree in Apache Spark: https://databricks.com/blog/2016/05/23/apache-spark-as-a-compiler-joining-a-billion-rows-per-second-on-a-laptop.html https://databricks.com/blog/2016/05/23/apache-spark-as-a-com...
- gravypod 10y ago
  I'm not saying the performance isn't important in this case, I'm saying it's an inherently unsafe implementation. I can't think of a single way to secure the system if the password falls to the wrong hands. I'd much rather have this done in a query language and have the queries cached. A compiled query should be very small (maybe only a few instructions) and if done right could be very quick without any fancy meta evaluation. You'd also get "some" way to sandbox the system inherently. The code should only be able to access your data and if you design a language around that idea your have something infinitely more safe then something that isn't.
pulisse 10y ago
The query engine isn't executing arbitrary code. The queries are written in a DSL and transpiled.
- jamii 10y ago
  The DSL is compiled to Julia, and may contain arbitrary Julia expressions which are spliced into the result. Relations may also contain arbitrary Julia datatypes. Eg in: @query begin state() => current_state x in 1:num_x y in 1:num_y is_cleared = @exists cleared($x,$y) is_mine = @exists mine($x,$y) mine_count(x, y) => count cell_node = @match (current_state, is_mine, is_cleared, count) begin (:game_in_progress, _, true, 0) => button("_") (:game_in_progress, _, true, _) => button(string(count)) (:game_in_progress, _, false, _) => button(Dict(:onclick => @event clicked(x,y)), "X") (:game_won, true, _, _) => button("") (:game_lost, true, _, _) => button("") (_, false, _, _) => button(string(count)) other => error("The hell is this: $other") end return cell(x,y) => cell_node end @match is a Julia macro, button, string, Dict etc are Julia functions and cell_node is a DOM node. The point of Imp is to be able to write entire apps without having to context switch between multiple languages and systems. It needs to have a full-blown language in the database because there isn't going to be an application or frontend tier.
  - gravypod 10y ago
    That sounds like playing with a metal forgery and the only protection you have on is oven mitts.

threepipeproblm 10y ago

Thank you very much for this.