MISP computation about ascent HOT 8 CLOSED

Hi @brurucy, the index-sharing data structure provider has not been added to the repo yet. I'll try and rectify that whenever I get a chance.
In the meantime, you can check out the docker image https://hub.docker.com/r/arashsahebolamri/byods-artifact, which contains this code under /src/exps/ind-share

from ascent.

Perusing over byods was my main entertainment for a 13 hours flight that just landed. I think I get it now, and the index optimisation code is very portable. I'm snatching it.

Thanks @s-arash and @kmicinski.

Could you also tell me where does ascent the compiler compute the indexes? I can always guess it correctly, but the logic seems to be buried beneath so much parsing that I'm struggling to find the seemingly simple code that does that.

from ascent.

This should be in the ind_rel provider of the byods branch. I am busy with some end-of-semester business now, but I will try to get a concrete pointer into the code by the end of the week. Arash is looking at merging the byods branch into the main one proper--but I think that's still up in the air as to timeline.

from ascent.

Thanks Kristopher! Looking forward to it.

from ascent.

@s-arash could you also describe how do you go from Datalog program -> Indexes?

e.g. if you have the classic ancestor rule:

r1 - tc(?x, ?y) <- e(?x, ?y)
r2 - tc(?x, ?z) <- e(?x, ?y), tc(?y, ?z)

Are your indexes then ((key), (value)):
e [ ((1), (0)), ((0, 1), ) ]
tc [ ((0), (1)) ]

And plan:
r1 - Project identity
r2 - Project (e_((1), (0)) |><| tc_((0), (1)))

from ascent.

Hi Bruno,

Section 5.5 of this paper describes the key points of the implementation: https://kmicinski.com/assets/byods.pdf. There are a few differences compared to what Souffle is doing (e.g., using linked hashmaps rather than btrees/tries), but algorithmically it should follow https://www.vldb.org/pvldb/vol12/p141-subotic.pdf.

from ascent.

@brurucy, to add more context to Kris's answer, the Ascent compiler itself selects a set of logical indexes for each relation. In your example, it is as you described (i.e., for e the indexes are [{}, {1}, {0, 1}]). It is up to the data structure provider (index-sharing for example) to come up with physical indexes for this set. As Kris said, that process is described in the BYODS paper.

from ascent.

Could you also tell me where does ascent the compiler compute the indexes?

Look for it in ascent_hir.rs (no parsing there). Specifically, compile_rule_to_ir_rule() should be a good starting point.

from ascent.