search

mit-pdos / noria

Fast web applications through dynamic, partially-stateful dataflow
Apache License 2.0
4.99k stars 242 forks source link

Project fix #185

Open JustusAdam opened 3 years ago

JustusAdam commented 3 years ago

This fixes what I think is a bug in the implementation of query_through in the project operator. The implementation assumed that columns in emit were monotonically increasing, but I did not read about this as an explicit invariant. As a result the implementation would not permute columns if that was requested in emit. The following pseudo-rust illustrates the inconsistency. 

let p = Project::new(emit=[0,2,1]); // <- permutation requested

let v = [1,2,3];
p.on_input([v]) // returns [1,3,2] <- correctly permuted
ancestor_state.insert(v);
p.query_through(..., states={key=1, states={..., ancestor_state }); // returns [1,2,3] <- not permuted

The new version should be as efficient as before but correctly permutes in query_through though I have not benchmarked it.

I added safety assertions for debug mode and added a test case.

The new implementation is less pretty and maybe less simple? So I added some comments explaining what it does.

Lmk if there are any questions or issues with the PR.

JustusAdam commented 3 years ago

I am a bit confused by the output from the automatic checks, because they originate from compiler warnings turned errors in parts of the code this PR does not touch.

I'd prefer not to fix them, as those changes would have nothing to do with the actual purpose of this PR.

jonhoo commented 3 years ago

Thanks for this Justus! I'm not actively maintaining this project any more, but always good to have these fixes in a public place for anyone else who might come along and want to run the code. Thanks for sending it back upstream! Tagging @ms705 too so he's aware of this.

somehowchris commented 2 years ago

@jonhoo @ms705 I couldn't find any notice but just PRs and tickets like these. It seems that this project is not only currently not supported but was fully dropped, am I wrong? I would love to be wrong and help out but if so please note that somewhere and put the repository in read only mode to signal it

jonhoo commented 2 years ago

@somehowchris I responded over in https://github.com/mit-pdos/noria/issues/179#issuecomment-962500999 — let's keep this PR for discussion of the PR :)