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.

Sign up for GitHub

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

Jump to bottom

[kvexec] merge join #8561

Open
wants to merge 15 commits into
base: main
Choose a base branch
from
Open

[kvexec] merge join #8561

wants to merge 15 commits into from

Conversation

max-hoffman
Copy link
Contributor

@max-hoffman max-hoffman commented Nov 14, 2024 •
edited
Loading

This isn't the best perf win on linux, but it counteracts the sql.Row interface PR which otherwise would swing merge join +30% in the wrong direction.

goos: darwin
goarch: arm64
pkg: github.com/dolthub/dolt/go/performance/microsysbench
                │  before.txt  │           after.txt           │
                │    sec/op    │    sec/op     vs base         │
OltpJoinScan-12   680.6µ ± 26%   612.1µ ± 17%  ~ (p=0.240 n=6)

                │  before.txt  │              after.txt              │
                │     B/op     │     B/op      vs base               │
OltpJoinScan-12   163.8Ki ± 0%   123.8Ki ± 0%  -24.42% (p=0.002 n=6)

                │ before.txt  │             after.txt              │
                │  allocs/op  │  allocs/op   vs base               │
OltpJoinScan-12   5.906k ± 0%   4.233k ± 0%  -28.33% (p=0.002 n=6)

TODO:

  • left join
  • nulls and other edge cases
  • execute full comparer

@max-hoffman
Copy link
Contributor Author

#benchmark

@github-actions GitHub Actions
Copy link

@max-hoffman workflow run: https://github.com/dolthub/dolt/actions/runs/11847027155

@coffeegoddd
Copy link
Contributor

@max-hoffman DOLT

comparing_percentages
100.000000 to 100.000000
version result total
302ab0b ok 5937457
version total_tests
302ab0b 5937457
correctness_percentage
100.0

@coffeegoddd
Copy link
Contributor

@coffeegoddd DOLT

comparing_percentages
100.000000 to 100.000000
version result total
4fa6227 ok 5937457
version total_tests
4fa6227 5937457
correctness_percentage
100.0

@coffeegoddd
Copy link
Contributor

@max-hoffman DOLT

test_name from_latency_p95 to_latency_p95 percent_change
tpcc-scale-factor-1 61.08 59.99 -1.78
test_name from_server_name from_server_version from_tps to_server_name to_server_version to_tps percent_change
tpcc-scale-factor-1 dolt 0e34d26 40.64 dolt 4fa6227 40.7 0.15

@coffeegoddd
Copy link
Contributor

@max-hoffman DOLT

read_tests from_latency to_latency percent_change
covering_index_scan 0.62 0.62 0.0
groupby_scan 16.41 16.41 0.0
index_join 2.26 2.26 0.0
index_join_scan 1.79 1.64 -8.38
index_scan 53.85 55.82 3.66
oltp_point_select 0.26 0.27 3.85
oltp_read_only 5.28 5.37 1.7
select_random_points 0.64 0.65 1.56
select_random_ranges 0.63 0.64 1.59
table_scan 54.83 55.82 1.81
types_table_scan 139.85 144.97 3.66
write_tests from_latency to_latency percent_change
oltp_delete_insert 5.77 5.88 1.91
oltp_insert 2.91 2.91 0.0
oltp_read_write 11.24 11.45 1.87
oltp_update_index 2.91 2.97 2.06
oltp_update_non_index 2.86 2.91 1.75
oltp_write_only 5.88 5.99 1.87
types_delete_insert 6.21 6.21 0.0

@coffeegoddd
Copy link
Contributor

@max-hoffman DOLT

comparing_percentages
100.000000 to 100.000000
version result total
f7225f7 ok 5937457
version total_tests
f7225f7 5937457
correctness_percentage
100.0

@coffeegoddd
Copy link
Contributor

@coffeegoddd DOLT

comparing_percentages
100.000000 to 100.000000
version result total
0a7e70a ok 5937457
version total_tests
0a7e70a 5937457
correctness_percentage
100.0

@max-hoffman
Copy link
Contributor Author

#benchmark

@github-actions GitHub Actions
Copy link

@max-hoffman workflow run: https://github.com/dolthub/dolt/actions/runs/11922319267

@coffeegoddd
Copy link
Contributor

@max-hoffman DOLT

comparing_percentages
100.000000 to 100.000000
version result total
e8f4ead ok 5937457
version total_tests
e8f4ead 5937457
correctness_percentage
100.0

@coffeegoddd
Copy link
Contributor

@max-hoffman DOLT

test_name from_latency_p95 to_latency_p95 percent_change
tpcc-scale-factor-1 57.87 58.92 1.81
test_name from_server_name from_server_version from_tps to_server_name to_server_version to_tps percent_change
tpcc-scale-factor-1 dolt f4e529a 41.65 dolt e8f4ead 41.42 -0.55

@coffeegoddd
Copy link
Contributor

@max-hoffman DOLT

read_tests from_latency to_latency percent_change
covering_index_scan 0.62 0.69 11.29
groupby_scan 16.71 16.41 -1.8
index_join 2.26 2.26 0.0
index_join_scan 1.82 1.44 -20.88
index_scan 54.83 54.83 0.0
oltp_point_select 0.27 0.27 0.0
oltp_read_only 5.37 5.37 0.0
select_random_points 0.65 0.65 0.0
select_random_ranges 0.64 0.64 0.0
table_scan 55.82 55.82 0.0
types_table_scan 144.97 142.39 -1.78
write_tests from_latency to_latency percent_change
oltp_delete_insert 5.88 5.88 0.0
oltp_insert 2.91 2.91 0.0
oltp_read_write 11.45 11.45 0.0
oltp_update_index 2.97 2.97 0.0
oltp_update_non_index 2.91 2.91 0.0
oltp_write_only 5.99 5.99 0.0
types_delete_insert 6.21 6.21 0.0

@coffeegoddd
Copy link
Contributor

@max-hoffman DOLT

comparing_percentages
100.000000 to 100.000000
version result total
c1e9358 ok 5937457
version total_tests
c1e9358 5937457
correctness_percentage
100.0

@coffeegoddd
Copy link
Contributor

@max-hoffman DOLT

comparing_percentages
100.000000 to 100.000000
version result total
fdabb0a ok 5937457
version total_tests
fdabb0a 5937457
correctness_percentage
100.0

@coffeegoddd
Copy link
Contributor

@max-hoffman DOLT

comparing_percentages
100.000000 to 100.000000
version result total
b76555f ok 5937457
version total_tests
b76555f 5937457
correctness_percentage
100.0

jycor
jycor approved these changes Nov 21, 2024
View reviewed changes
Copy link
Contributor

@jycor jycor left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think using opposite logic is more readable:
https://github.com/dolthub/dolt/compare/max/kv-merge-join...james/refactor?expand=1

While gotos aren't the best, I think it's still pretty understandable, so LGTM

@coffeegoddd
Copy link
Contributor

@max-hoffman DOLT

comparing_percentages
100.000000 to 100.000000
version result total
f67d302 ok 5937457
version total_tests
f67d302 5937457
correctness_percentage
100.0

zachmu
zachmu reviewed Nov 22, 2024
View reviewed changes
Copy link
Member

@zachmu zachmu left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Not as bad as you built it up to be, generally not too hard to understand.

I think readability would be improved by making the loops explicit, keeping goto statements for true jumps rather than "go to beginning of this loop"

go/libraries/doltcore/sqle/kvexec/builder.go
if ita, ok := getIta(n.Right()); ok && len(r) == 0 && simpleLookupExpressions(ita.Expressions()) {
if _, _, dstIter, _, dstTags, dstFilter, err := getSourceKv(ctx, n.Right(), false); err == nil && dstIter != nil {
if srcMap, srcIter, _, srcSchema, srcTags, srcFilter, err := getSourceKv(ctx, n.Left(), true); err == nil && srcSchema != nil {
if _, _, _, dstIter, _, _, dstTags, dstFilter, err := getSourceKv(ctx, n.Right(), false); err == nil && dstIter != nil {
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

One easy readability win here would be to return a struct or an interface from this method. 3 return values is usually fine, 4 is pushing it, this is front page of reddit level bad

go/libraries/doltcore/sqle/kvexec/builder.go
@@ -263,74 +305,79 @@ func getPhysicalColCount(schemas []schema.Schema, splits []int, projections []ui
// getSourceKv extracts prolly table and index specific structures needed
// to implement a lookup join. We return either |srcIter| or |dstIter|
// depending on whether |isSrc| is true.
func getSourceKv(ctx *sql.Context, n sql.Node, isSrc bool) (prolly.Map, prolly.MapIter, index.SecondaryLookupIterGen, schema.Schema, []uint64, sql.Expression, error) {
func getSourceKv(ctx *sql.Context, n sql.Node, isSrc bool) (prolly.Map, prolly.Map, prolly.MapIter, index.SecondaryLookupIterGen, schema.Schema, schema.Schema, []uint64, sql.Expression, error) {
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Def model this after getMergeKv

Probably want to return a pointer to a struct and an err

go/libraries/doltcore/sqle/kvexec/builder.go

func getMergeKv(ctx *sql.Context, n sql.Node) (mergeState, error) {
ms := mergeState{}
//var secMap prolly.Map
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Don't forget to remove these unused vars

go/libraries/doltcore/sqle/kvexec/builder.go
type coveringNormalizer func(val.Tuple) (val.Tuple, val.Tuple, error)

type mergeState struct {
idxMap prolly.Map
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Worth giving these fields comments, probably the type as well

go/libraries/doltcore/sqle/kvexec/builder.go
return ms, err
}

priMap := durable.ProllyMapFromIndex(priIndex)
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Assuming there's an LD check somewhere above this that will prevent this breaking on old repos?

I'm fine breaking old repos but it shouldn't panic

go/libraries/doltcore/sqle/kvexec/merge_join.go
return candidate, true, nil
}

func (l *mergeJoinKvIter) buildCandidate(ctx *sql.Context, leftKey, leftVal, rightKey, rightVal val.Tuple) (sql.Row, error) {
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Probably just buildRow?

go/libraries/doltcore/sqle/kvexec/merge_join.go
goto match
}

incr:
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Maybe just call this compare

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The only exits from this block are to the next block (matchBuf) or to exhaustLeft, otherwise it loops.

exhaustLeft is terminal and is better expressed as a method (see below), so this whole block would be better expressed as a for { loop with a break statement when it's done

go/libraries/doltcore/sqle/kvexec/merge_join.go
goto matchBuf
}

match:
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Same comment here: most of the goto statements are just loop statements, and of the 2 that aren't one is to the terminal exhaustLeft. Write as a loop, makes the intent clearer

go/libraries/doltcore/sqle/kvexec/merge_join.go
goto exhaustLeft
}

func (l *mergeJoinKvIter) tryReturn(ctx *sql.Context, leftKey, leftVal, rightKey, rightVal val.Tuple) (sql.Row, bool, error) {
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Probably call this buildResultRow, add a comment about the boolean return value

go/libraries/doltcore/sqle/kvexec/merge_join.go

func schemaIsCovering(sch schema.Schema, projections []uint64) bool {
cols := sch.GetAllCols()
if len(projections) > cols.Size() {
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

What's this about? Could use a comment

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@zachmu zachmu zachmu left review comments

@jycor jycor jycor approved these changes

Assignees

@zachmu zachmu

Labels
correctness_approved
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
4 participants
@max-hoffman @coffeegoddd @zachmu @jycor