How should I measure the similarity of 2 SQLs?

[CBQu]

Goal: I would like to measure the similarity of 2 SQLs in a scale of [0, 1]. 0 means totally different. 1 means exactly same. Assume 2 SQLs are from the same dialect.

My current idea:
I am considering using the diff function. diff returns an operation list. The length of the list can be a measurement of difference.

To be more specific, the similarity function could be something like

1 - len(diff) / some_bound,

where if len(diff) == 0, it naturally indicate "exactly same". But the some_bound should be a value that describe the maximum difference of 2 ASTs. e.g. DELETE FROM a and SELECT 1.

My question: What would be the upper bound of diff to normalize it? My guess is the sum of # nodes. But I am not sure if it is a tight bound.

Any idea or alternative solution would be super helpful. Thanks!

[izeigerman]

The diff function returns an edit script which also contains all nodes that have been unchanged. Those nodes will be wrapped into Keep.

So the upper bound (denominator) would the length of the edit script. The numerator will be a number of Keep nodes in the edit script. For example:

edit_script = diff(...)
numerator = len([e for e in edit_script if isinstance(e, Keep)])
denominator = len(edit_script)
score = numerator / denominator