Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Using GoLang v1.19 cid ordering is changed due to unstable sort #1071

Closed
shahzadlone opened this issue Feb 2, 2023 · 1 comment · Fixed by #1094
Closed

Using GoLang v1.19 cid ordering is changed due to unstable sort #1071

shahzadlone opened this issue Feb 2, 2023 · 1 comment · Fixed by #1094
Assignees
Labels
area/query Related to the query component bug Something isn't working code quality Related to improving code quality
Milestone

Comments

@shahzadlone
Copy link
Member

This is what commit ordering looks like with GoLang v1.18.5:

func TestPassesWithGo1_18_5(t *testing.T) {
	test := testUtils.RequestTestCase{
		Description: "Simple test",
		Request: `query {
					commits(dockey: "bae-52b9170d-b77a-5887-b877-cbdbb99b009f", order: {height: ASC}) {
						cid
						height
					}
				}`,
		Docs: map[int][]string{
			0: {
				`{
					"Name": "John",
					"Age": 21
				}`,
			},
		},
		Updates: map[int]map[int][]string{
			0: {
				0: {
					`{
						"Age": 22
					}`,
					`{
						"Age": 23
					}`,
					`{
						"Age": 24
					}`,
				},
			},
		},
		Results: []map[string]any{
			{
				"cid":    "bafybeiaqarrcayyoly2gdiam6mhh72ls4azwa7brozxxc3q2srnggkkqkq",
				"height": int64(1),
			},
			{
				"cid":    "bafybeigju7dgicfq3fxvtlxtjao7won4xc7kusykkvumngjfx5i2c7ibny",
				"height": int64(1),
			},
			{
				"cid":    "bafybeid5l577igkgcn6wjqjeqxlta4dcc3a3iykwkborf4fklaenjuctoq",
				"height": int64(1),
			},
			{
				"cid":    "bafybeiacqac6scm7pmtlvqptvtljmoroevnoedku42qi5bmfdpaelcu5fm",
				"height": int64(2),
			},
			{
				"cid":    "bafybeibz3vbkt75siz3zogke6tlzvpcxttpiy4xivjvgyeaorjz6wsbguq",
				"height": int64(2),
			},
			{
				"cid":    "bafybeiho5z6seahwxgbdyobylzyarrdschgzmood7rkdtp4qpd2uxebaxy",
				"height": int64(3),
			},
			{
				"cid":    "bafybeib6yxcmbg2gz5ss6d67u5mu6wcatfjtdp2rv44difyznp3rqlyu4m",
				"height": int64(3),
			},
			{
				"cid":    "bafybeihhlr6teynoy534b32kihulsmtdnnzp5woebvhubvofoxqx4g4lha",
				"height": int64(4),
			},
			{
				"cid":    "bafybeicgc6k47su6263dm3mv5j5gkv3bbt43nb66x6wjashjxpfm2ds5nu",
				"height": int64(4),
			},
		},
	}

	executeTestCase(t, test)
}

This is what commit ordering looks like with GoLang v1.19.5:

func TestPassesWithGo1_19_5(t *testing.T) {
	test := testUtils.RequestTestCase{
		Description: "Simple test",
		Request: `query {
					commits(dockey: "bae-52b9170d-b77a-5887-b877-cbdbb99b009f", order: {height: ASC}) {
						cid
						height
					}
				}`,
		Docs: map[int][]string{
			0: {
				`{
					"Name": "John",
					"Age": 21
				}`,
			},
		},
		Updates: map[int]map[int][]string{
			0: {
				0: {
					`{
						"Age": 22
					}`,
					`{
						"Age": 23
					}`,
					`{
						"Age": 24
					}`,
				},
			},
		},
		Results: []map[string]any{
			{
				"cid":    "bafybeid5l577igkgcn6wjqjeqxlta4dcc3a3iykwkborf4fklaenjuctoq",
				"height": int64(1),
			},
			{
				"cid":    "bafybeiaqarrcayyoly2gdiam6mhh72ls4azwa7brozxxc3q2srnggkkqkq",
				"height": int64(1),
			},
			{
				"cid":    "bafybeigju7dgicfq3fxvtlxtjao7won4xc7kusykkvumngjfx5i2c7ibny",
				"height": int64(1),
			},
			{
				"cid":    "bafybeibz3vbkt75siz3zogke6tlzvpcxttpiy4xivjvgyeaorjz6wsbguq",
				"height": int64(2),
			},
			{
				"cid":    "bafybeiacqac6scm7pmtlvqptvtljmoroevnoedku42qi5bmfdpaelcu5fm",
				"height": int64(2),
			},
			{
				"cid":    "bafybeib6yxcmbg2gz5ss6d67u5mu6wcatfjtdp2rv44difyznp3rqlyu4m",
				"height": int64(3),
			},
			{
				"cid":    "bafybeiho5z6seahwxgbdyobylzyarrdschgzmood7rkdtp4qpd2uxebaxy",
				"height": int64(3),
			},
			{
				"cid":    "bafybeicgc6k47su6263dm3mv5j5gkv3bbt43nb66x6wjashjxpfm2ds5nu",
				"height": int64(4),
			},
			{
				"cid":    "bafybeihhlr6teynoy534b32kihulsmtdnnzp5woebvhubvofoxqx4g4lha",
				"height": int64(4),
			},
		},
	}

	executeTestCase(t, test)
}
@shahzadlone shahzadlone added bug Something isn't working area/query Related to the query component code quality Related to improving code quality labels Feb 2, 2023
@shahzadlone shahzadlone changed the title Using GoLang v1.19 some commit ordering is changed Using GoLang v1.19 cid ordering is changed due to unstable sort Feb 14, 2023
@shahzadlone
Copy link
Member Author

The situation was that TestPassesWithGo1_18_5 was passing with golang v1.18.5 and TestPassesWithGo1_19_5 was passing with golang v1.19.5.

func TestPassesWithGo1_18_5(t *testing.T) {
	test := testUtils.RequestTestCase{
		Description: "Simple test",
		Request: `query {
                     commits(dockey: "bae-52b9170d-b77a-5887-b877-cbdbb99b009f", order: {height: ASC}) {
                         cid
                         height
                     }
                 }`,
		Docs: map[int][]string{
			0: {
				`{
                     "Name": "John",
                     "Age": 21
                 }`,
			},
		},
		Updates: map[int]map[int][]string{
			0: {
				0: {
					`{
                         "Age": 22
                     }`,
					`{
                         "Age": 23
                     }`,
					`{
                         "Age": 24
                     }`,
				},
			},
		},
		Results: []map[string]any{

			// Input to SortAll()
			// [
			// { [4 bafybeihhlr6teynoy534b32kihulsmtdnnzp5woebvhubvofoxqx4g4lha] }
			// { [3 bafybeiho5z6seahwxgbdyobylzyarrdschgzmood7rkdtp4qpd2uxebaxy] }
			// { [2 bafybeiacqac6scm7pmtlvqptvtljmoroevnoedku42qi5bmfdpaelcu5fm] }
			// { [1 bafybeigju7dgicfq3fxvtlxtjao7won4xc7kusykkvumngjfx5i2c7ibny] }
			// { [1 bafybeiaqarrcayyoly2gdiam6mhh72ls4azwa7brozxxc3q2srnggkkqkq] }
			// { [4 bafybeicgc6k47su6263dm3mv5j5gkv3bbt43nb66x6wjashjxpfm2ds5nu] }
			// { [3 bafybeib6yxcmbg2gz5ss6d67u5mu6wcatfjtdp2rv44difyznp3rqlyu4m] }
			// { [2 bafybeibz3vbkt75siz3zogke6tlzvpcxttpiy4xivjvgyeaorjz6wsbguq] }
			// { [1 bafybeid5l577igkgcn6wjqjeqxlta4dcc3a3iykwkborf4fklaenjuctoq] }
			// ]

			// Output from SortAll() - unstable
			// [
			// { [1 bafybeiaqarrcayyoly2gdiam6mhh72ls4azwa7brozxxc3q2srnggkkqkq] }
			// { [1 bafybeigju7dgicfq3fxvtlxtjao7won4xc7kusykkvumngjfx5i2c7ibny] }
			// { [1 bafybeid5l577igkgcn6wjqjeqxlta4dcc3a3iykwkborf4fklaenjuctoq] }
			// { [2 bafybeiacqac6scm7pmtlvqptvtljmoroevnoedku42qi5bmfdpaelcu5fm] }
			// { [2 bafybeibz3vbkt75siz3zogke6tlzvpcxttpiy4xivjvgyeaorjz6wsbguq] }
			// { [3 bafybeiho5z6seahwxgbdyobylzyarrdschgzmood7rkdtp4qpd2uxebaxy] }
			// { [3 bafybeib6yxcmbg2gz5ss6d67u5mu6wcatfjtdp2rv44difyznp3rqlyu4m] }
			// { [4 bafybeihhlr6teynoy534b32kihulsmtdnnzp5woebvhubvofoxqx4g4lha] }
			// { [4 bafybeicgc6k47su6263dm3mv5j5gkv3bbt43nb66x6wjashjxpfm2ds5nu] }
			// ]

			{
				"cid":    "bafybeiaqarrcayyoly2gdiam6mhh72ls4azwa7brozxxc3q2srnggkkqkq",
				"height": int64(1),
			},
			{
				"cid":    "bafybeigju7dgicfq3fxvtlxtjao7won4xc7kusykkvumngjfx5i2c7ibny",
				"height": int64(1),
			},
			{
				"cid":    "bafybeid5l577igkgcn6wjqjeqxlta4dcc3a3iykwkborf4fklaenjuctoq",
				"height": int64(1),
			},
			{
				"cid":    "bafybeiacqac6scm7pmtlvqptvtljmoroevnoedku42qi5bmfdpaelcu5fm",
				"height": int64(2),
			},
			{
				"cid":    "bafybeibz3vbkt75siz3zogke6tlzvpcxttpiy4xivjvgyeaorjz6wsbguq",
				"height": int64(2),
			},
			{
				"cid":    "bafybeiho5z6seahwxgbdyobylzyarrdschgzmood7rkdtp4qpd2uxebaxy",
				"height": int64(3),
			},
			{
				"cid":    "bafybeib6yxcmbg2gz5ss6d67u5mu6wcatfjtdp2rv44difyznp3rqlyu4m",
				"height": int64(3),
			},
			{
				"cid":    "bafybeihhlr6teynoy534b32kihulsmtdnnzp5woebvhubvofoxqx4g4lha",
				"height": int64(4),
			},
			{
				"cid":    "bafybeicgc6k47su6263dm3mv5j5gkv3bbt43nb66x6wjashjxpfm2ds5nu",
				"height": int64(4),
			},
		},
	}

	executeTestCase(t, test)
}

func TestPassesWithGo1_19_5(t *testing.T) {
	test := testUtils.RequestTestCase{
		Description: "Simple test",
		Request: `query {
                     commits(dockey: "bae-52b9170d-b77a-5887-b877-cbdbb99b009f", order: {height: ASC}) {
                         cid
                         height
                     }
                 }`,
		Docs: map[int][]string{
			0: {
				`{
                     "Name": "John",
                     "Age": 21
                 }`,
			},
		},
		Updates: map[int]map[int][]string{
			0: {
				0: {
					`{
                         "Age": 22
                     }`,
					`{
                         "Age": 23
                     }`,
					`{
                         "Age": 24
                     }`,
				},
			},
		},
		Results: []map[string]any{
			// Input to planner.SortAll()
			// [
			// { [4 bafybeihhlr6teynoy534b32kihulsmtdnnzp5woebvhubvofoxqx4g4lha] }
			// { [3 bafybeiho5z6seahwxgbdyobylzyarrdschgzmood7rkdtp4qpd2uxebaxy] }
			// { [2 bafybeiacqac6scm7pmtlvqptvtljmoroevnoedku42qi5bmfdpaelcu5fm] }
			// { [1 bafybeigju7dgicfq3fxvtlxtjao7won4xc7kusykkvumngjfx5i2c7ibny] }
			// { [1 bafybeiaqarrcayyoly2gdiam6mhh72ls4azwa7brozxxc3q2srnggkkqkq] }
			// { [4 bafybeicgc6k47su6263dm3mv5j5gkv3bbt43nb66x6wjashjxpfm2ds5nu] }
			// { [3 bafybeib6yxcmbg2gz5ss6d67u5mu6wcatfjtdp2rv44difyznp3rqlyu4m] }
			// { [2 bafybeibz3vbkt75siz3zogke6tlzvpcxttpiy4xivjvgyeaorjz6wsbguq] }
			// { [1 bafybeid5l577igkgcn6wjqjeqxlta4dcc3a3iykwkborf4fklaenjuctoq] }
			// ]

			// Output from SortAll() - unstable
			// [
			// { [1 bafybeid5l577igkgcn6wjqjeqxlta4dcc3a3iykwkborf4fklaenjuctoq] }
			// { [1 bafybeiaqarrcayyoly2gdiam6mhh72ls4azwa7brozxxc3q2srnggkkqkq] }
			// { [1 bafybeigju7dgicfq3fxvtlxtjao7won4xc7kusykkvumngjfx5i2c7ibny] }
			// { [2 bafybeibz3vbkt75siz3zogke6tlzvpcxttpiy4xivjvgyeaorjz6wsbguq] }
			// { [2 bafybeiacqac6scm7pmtlvqptvtljmoroevnoedku42qi5bmfdpaelcu5fm] }
			// { [3 bafybeib6yxcmbg2gz5ss6d67u5mu6wcatfjtdp2rv44difyznp3rqlyu4m] }
			// { [3 bafybeiho5z6seahwxgbdyobylzyarrdschgzmood7rkdtp4qpd2uxebaxy] }
			// { [4 bafybeicgc6k47su6263dm3mv5j5gkv3bbt43nb66x6wjashjxpfm2ds5nu] }
			// { [4 bafybeihhlr6teynoy534b32kihulsmtdnnzp5woebvhubvofoxqx4g4lha] }
			// ]

			{
				"cid":    "bafybeid5l577igkgcn6wjqjeqxlta4dcc3a3iykwkborf4fklaenjuctoq",
				"height": int64(1),
			},
			{
				"cid":    "bafybeiaqarrcayyoly2gdiam6mhh72ls4azwa7brozxxc3q2srnggkkqkq",
				"height": int64(1),
			},
			{
				"cid":    "bafybeigju7dgicfq3fxvtlxtjao7won4xc7kusykkvumngjfx5i2c7ibny",
				"height": int64(1),
			},
			{
				"cid":    "bafybeibz3vbkt75siz3zogke6tlzvpcxttpiy4xivjvgyeaorjz6wsbguq",
				"height": int64(2),
			},
			{
				"cid":    "bafybeiacqac6scm7pmtlvqptvtljmoroevnoedku42qi5bmfdpaelcu5fm",
				"height": int64(2),
			},
			{
				"cid":    "bafybeib6yxcmbg2gz5ss6d67u5mu6wcatfjtdp2rv44difyznp3rqlyu4m",
				"height": int64(3),
			},
			{
				"cid":    "bafybeiho5z6seahwxgbdyobylzyarrdschgzmood7rkdtp4qpd2uxebaxy",
				"height": int64(3),
			},
			{
				"cid":    "bafybeicgc6k47su6263dm3mv5j5gkv3bbt43nb66x6wjashjxpfm2ds5nu",
				"height": int64(4),
			},
			{
				"cid":    "bafybeihhlr6teynoy534b32kihulsmtdnnzp5woebvhubvofoxqx4g4lha",
				"height": int64(4),
			},
		},
	}

	executeTestCase(t, test)
}

Both the above sorts return different ordering, this is because we are using unstable sort. The correct ordering that should pass with both GoLang 1.18.5 and 1.19.5 is the following (the order should be preserved):

func TestPassesWithBoth(t *testing.T) {
	test := testUtils.RequestTestCase{
		Description: "Simple test",
		Request: `query {
                     commits(dockey: "bae-52b9170d-b77a-5887-b877-cbdbb99b009f", order: {height: ASC}) {
                         cid
                         height
                     }
                 }`,
		Docs: map[int][]string{
			0: {
				`{
                     "Name": "John",
                     "Age": 21
                 }`,
			},
		},
		Updates: map[int]map[int][]string{
			0: {
				0: {
					`{
                         "Age": 22
                     }`,
					`{
                         "Age": 23
                     }`,
					`{
                         "Age": 24
                     }`,
				},
			},
		},
		Results: []map[string]any{

			// Input to SortAll()
			// [
			// { [4 bafybeihhlr6teynoy534b32kihulsmtdnnzp5woebvhubvofoxqx4g4lha] }
			// { [3 bafybeiho5z6seahwxgbdyobylzyarrdschgzmood7rkdtp4qpd2uxebaxy] }
			// { [2 bafybeiacqac6scm7pmtlvqptvtljmoroevnoedku42qi5bmfdpaelcu5fm] }
			// { [1 bafybeigju7dgicfq3fxvtlxtjao7won4xc7kusykkvumngjfx5i2c7ibny] }
			// { [1 bafybeiaqarrcayyoly2gdiam6mhh72ls4azwa7brozxxc3q2srnggkkqkq] }
			// { [4 bafybeicgc6k47su6263dm3mv5j5gkv3bbt43nb66x6wjashjxpfm2ds5nu] }
			// { [3 bafybeib6yxcmbg2gz5ss6d67u5mu6wcatfjtdp2rv44difyznp3rqlyu4m] }
			// { [2 bafybeibz3vbkt75siz3zogke6tlzvpcxttpiy4xivjvgyeaorjz6wsbguq] }
			// { [1 bafybeid5l577igkgcn6wjqjeqxlta4dcc3a3iykwkborf4fklaenjuctoq] }
			// ]

			//After Fixing SortAll() - stable
			// [
			// { [1 bafybeigju7dgicfq3fxvtlxtjao7won4xc7kusykkvumngjfx5i2c7ibny] }
			// { [1 bafybeiaqarrcayyoly2gdiam6mhh72ls4azwa7brozxxc3q2srnggkkqkq] }
			// { [1 bafybeid5l577igkgcn6wjqjeqxlta4dcc3a3iykwkborf4fklaenjuctoq] }
			// { [2 bafybeiacqac6scm7pmtlvqptvtljmoroevnoedku42qi5bmfdpaelcu5fm] }
			// { [2 bafybeibz3vbkt75siz3zogke6tlzvpcxttpiy4xivjvgyeaorjz6wsbguq] }
			// { [3 bafybeiho5z6seahwxgbdyobylzyarrdschgzmood7rkdtp4qpd2uxebaxy] }
			// { [3 bafybeib6yxcmbg2gz5ss6d67u5mu6wcatfjtdp2rv44difyznp3rqlyu4m] }
			// { [4 bafybeihhlr6teynoy534b32kihulsmtdnnzp5woebvhubvofoxqx4g4lha] }
			// { [4 bafybeicgc6k47su6263dm3mv5j5gkv3bbt43nb66x6wjashjxpfm2ds5nu] }
			// ]
			{
				"cid":    "bafybeigju7dgicfq3fxvtlxtjao7won4xc7kusykkvumngjfx5i2c7ibny",
				"height": int64(1),
			},
			{
				"cid":    "bafybeiaqarrcayyoly2gdiam6mhh72ls4azwa7brozxxc3q2srnggkkqkq",
				"height": int64(1),
			},
			{
				"cid":    "bafybeid5l577igkgcn6wjqjeqxlta4dcc3a3iykwkborf4fklaenjuctoq",
				"height": int64(1),
			},
			{
				"cid":    "bafybeiacqac6scm7pmtlvqptvtljmoroevnoedku42qi5bmfdpaelcu5fm",
				"height": int64(2),
			},
			{
				"cid":    "bafybeibz3vbkt75siz3zogke6tlzvpcxttpiy4xivjvgyeaorjz6wsbguq",
				"height": int64(2),
			},
			{
				"cid":    "bafybeiho5z6seahwxgbdyobylzyarrdschgzmood7rkdtp4qpd2uxebaxy",
				"height": int64(3),
			},
			{
				"cid":    "bafybeib6yxcmbg2gz5ss6d67u5mu6wcatfjtdp2rv44difyznp3rqlyu4m",
				"height": int64(3),
			},
			{
				"cid":    "bafybeihhlr6teynoy534b32kihulsmtdnnzp5woebvhubvofoxqx4g4lha",
				"height": int64(4),
			},
			{
				"cid":    "bafybeicgc6k47su6263dm3mv5j5gkv3bbt43nb66x6wjashjxpfm2ds5nu",
				"height": int64(4),
			},
		},
	}

	executeTestCase(t, test)
}

@shahzadlone shahzadlone self-assigned this Feb 14, 2023
@shahzadlone shahzadlone added this to the DefraDB v0.5 milestone Feb 14, 2023
shahzadlone added a commit that referenced this issue Feb 15, 2023
- Resolves #1071

- Resolves #921

- This change uses stable sort and ensures the `Less` interface implementation only returns true if the comparison is less, otherwise returns false (this is not the full story as for when we do `DESC` the less to us then is the check of if it's greater than instead of less than). Note: Ensures the ordering of the input array is preserved, so the output is always stable.

- This change works on both GoLang v1.18.5 and v1.19.5.

- This also resolves some nil panics we were having before (one subtask of #833, which is issue #921).
	1) Fixes the test: `TestOneToManyToOneDeepOrderBySubTypeOfBothDescAndAsc`
	2) Fixes the test: `TestOneToManyToOneWithSumOfDeepOrderBySubTypeAndDeepOrderBySubtypeAscDirections`

- Ensures our sort handles `nil` sorting properly for `ASC` and `DESC`:
```
DESC = [10, 9, 8, ... nil, nil]
ASC  = [nil, nil, 1, 2, 3, ... ]
```
shahzadlone added a commit that referenced this issue Apr 13, 2023
- Resolves #1071

- Resolves #921

- This change uses stable sort and ensures the `Less` interface implementation only returns true if the comparison is less, otherwise returns false (this is not the full story as for when we do `DESC` the less to us then is the check of if it's greater than instead of less than). Note: Ensures the ordering of the input array is preserved, so the output is always stable.

- This change works on both GoLang v1.18.5 and v1.19.5.

- This also resolves some nil panics we were having before (one subtask of #833, which is issue #921).
	1) Fixes the test: `TestOneToManyToOneDeepOrderBySubTypeOfBothDescAndAsc`
	2) Fixes the test: `TestOneToManyToOneWithSumOfDeepOrderBySubTypeAndDeepOrderBySubtypeAscDirections`

- Ensures our sort handles `nil` sorting properly for `ASC` and `DESC`:
```
DESC = [10, 9, 8, ... nil, nil]
ASC  = [nil, nil, 1, 2, 3, ... ]
```
shahzadlone added a commit to shahzadlone/defradb that referenced this issue Feb 23, 2024
- Resolves sourcenetwork#1071

- Resolves sourcenetwork#921

- This change uses stable sort and ensures the `Less` interface implementation only returns true if the comparison is less, otherwise returns false (this is not the full story as for when we do `DESC` the less to us then is the check of if it's greater than instead of less than). Note: Ensures the ordering of the input array is preserved, so the output is always stable.

- This change works on both GoLang v1.18.5 and v1.19.5.

- This also resolves some nil panics we were having before (one subtask of sourcenetwork#833, which is issue sourcenetwork#921).
	1) Fixes the test: `TestOneToManyToOneDeepOrderBySubTypeOfBothDescAndAsc`
	2) Fixes the test: `TestOneToManyToOneWithSumOfDeepOrderBySubTypeAndDeepOrderBySubtypeAscDirections`

- Ensures our sort handles `nil` sorting properly for `ASC` and `DESC`:
```
DESC = [10, 9, 8, ... nil, nil]
ASC  = [nil, nil, 1, 2, 3, ... ]
```
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
area/query Related to the query component bug Something isn't working code quality Related to improving code quality
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant