Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Semantic Diff for SQL

github.com

Post reply on HN
Print view View original

21–30 of 34 posts

Re: Semantic Diff for SQL

#21

Post by lichtenberger »

Really awesome work :-)

I've implemented the Fast Match / Simple Edit script algorithm almost 10 years ago for my Master's thesis[1] for my database project[1][2] in order to import revisions of files with a hopefully minimal edit number of edit operations between the stored revision and a new one (back then it was for XML databases).

The diffing was only one aspect for the visual analytics approach to compare the revisions (tree structures) visually [4]. Internally the nodes are addressed through dense, ascending 64bit ints stored in a special trie index. Furthermore, during the import optionally changes are tracked as well as a rolling hash is stored for each node optionally. After the import you can query the changes or execute time travel queries easily.

Technically, a tree of tries is mapped to an append-only data file using a persistent data structure (in the functional sense), COW with path copying and a novel sliding snapshot algorithm for the leaf data pages itself.

I always have the vision to implement different visualizations to compare the revisions in a web frontend, but I'm currently spending my time on improving the latency of both writes and reads.

Thus, if someone would like to help, that would be awesome :-)

Kind regards

Johannes

[1] https://github.com/JohannesLichtenberger/master-thesis/blob/...

[2] https://github.com/sirixdb/sirix

[3] https://github.com/sirixdb/sirix/tree/master/bundles/sirix-c...

[4] https://youtube.com/watch?v=l9CXXBkl5vI

Re: Semantic Diff for SQL

#22

Post by samokhvalov »

lichtenberger wrote: post #21

Really awesome work :-) I've implemented the Fast Match / Simple Edit script algorithm almost 10 years ago for my Master's thesis[1] for my database project[1][2] in order to import revisions of files with a hopefully minimal edit number of edit operations between the stored revision and a new one (back then it was for XML databases). The diffing was only one aspect for the visual analytics approach to compare the re…

Comparing tree structures can be used to have diff of EXPLAIN plans. During query optimization, it might make a lot of sense.

Re: Semantic Diff for SQL

#23

Post by noisy_boy »

I wonder if this is a topical thread to check if anyone is aware of a Java based solution to parse a CREATE VIEW statement to get a mapping between the view columns and the corresponding source table columns. I checked out jsqlparser[0] and it does produce an AST which can be parsed using the visitor-pattern[1] but was wondering if there is a more "out-of-the-box" solution involving less work. Due to various reasons, querying the database information schema is not an option I can pursue.

[0]: https://github.com/JSQLParser/JSqlParser

[1]: https://en.wikipedia.org/wiki/Visitor_pattern

Re: Semantic Diff for SQL

#24

Post by benjiweber »

noisy_boy wrote: post #23

I wonder if this is a topical thread to check if anyone is aware of a Java based solution to parse a CREATE VIEW statement to get a mapping between the view columns and the corresponding source table columns. I checked out jsqlparser[0] and it does produce an AST which can be parsed using the visitor-pattern[1] but was wondering if there is a more "out-of-the-box" solution involving less work. Due to various reasons,…

What do you mean by a mapping with a source table columns? The data columns in the view could come from 0 to n source tables. Entirely synthetic, transformed, combined data from multiple tables etc.

Re: Semantic Diff for SQL

#25

Post by seaknoll »

tessierashpool wrote: post #16

this is very cool, but I believe this bit of the README is incorrect: Text-based diff tools such as git diff, when applied to a code base, have certain limitations. First, they can only detect insertions and deletions, not movements or updates of individual pieces of code. git diff can detect movements. looking at my .gitconfig, I think it's the "frag = magenta" line.

I think color-moved might also be what you’re thinking of. https://git-scm.com/docs/git-diff#Documentation/git-diff.txt...

Re: Semantic Diff for SQL

#26

Post by zasdffaa »

> (a + b) => (b + a)

> Semantically the query hasn’t changed

Now hang on a minute. Extend that to 3 and it can be (mssql but true in any I guess):

   declare @hi int =  2147483647;
   declare @lo int = -2147483648;

   declare @x int = @hi + @lo + @hi;  -- ok

   declare @y int = @hi + @hi + @lo; -- 'Arithmetic overflow error'
Worse yet with floats. I see what you're saying and good stuff, I'm thinking about this myself and I appreciate this article and will read it properly, but the edge cases have to be acknowledged.

Edit: this kind of thing is apparently something compiler writers keep rediscovering the hard way.

Re: Semantic Diff for SQL

#27

Post by sk1pper »

Nitpick:

> when a nested query is refactored into a common table expression (CTE), this kind of change doesn’t have any functional impact on either a query or its outcome

This isn’t quite true, at least in Postgres. It won’t affect the outcome, but it can affect the query plan.

Re: Semantic Diff for SQL

#28

Post by zasdffaa »

sk1pper wrote: post #27

Nitpick: > when a nested query is refactored into a common table expression (CTE), this kind of change doesn’t have any functional impact on either a query or its outcome This isn’t quite true, at least in Postgres. It won’t affect the outcome, but it can affect the query plan.

I believe that was true but in current PG the CTE no longer acts as an optimisation barrier.

https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit...

Re: Semantic Diff for SQL

#29

Post by noisy_boy »

benjiweber wrote: post #24
noisy_boy wrote: post #23

I wonder if this is a topical thread to check if anyone is aware of a Java based solution to parse a CREATE VIEW statement to get a mapping between the view columns and the corresponding source table columns. I checked out jsqlparser[0] and it does produce an AST which can be parsed using the visitor-pattern[1] but was wondering if there is a more "out-of-the-box" solution involving less work. Due to various reasons,…

What do you mean by a mapping with a source table columns? The data columns in the view could come from 0 to n source tables. Entirely synthetic, transformed, combined data from multiple tables etc.

True - I mean the view columns that _are_ from actual tables. Could be straight up table columns as is or may be part of function like max(a.abcd) where a is an alias to table xyz

Re: Semantic Diff for SQL

#30

Post by captaintobs »

sk1pper wrote: post #27

Nitpick: > when a nested query is refactored into a common table expression (CTE), this kind of change doesn’t have any functional impact on either a query or its outcome This isn’t quite true, at least in Postgres. It won’t affect the outcome, but it can affect the query plan.

For this use case, it’s intentional, since only the outcome is important to us. That’s kind of the draw of a declarative language, you ask what you want and don’t have too much control over how that’s done (the engine should optimize that away).
Post reply on HN