ORC-1170:[C++] Optimize the RowReader::seekToRow function in the case of seeking within the same stripe by coderex2522 · Pull Request #1114 · apache/orc

coderex2522 · 2022-05-11T09:25:59Z

What changes were proposed in this pull request?

The patch will optimize the seekToRow function. The RowReader::seekToRow() function always call startNextStripe() to seek to the beginning of target stripe. However, when PPD is enabled many calls are still staying in the same stripe which results in many unnecessary calls.

Why are the changes needed?

This PR improves the seekToRow function call. I pick a 259MB file of the TPCH lineitem table which contains 7200030
records. I use a modified orc-scan tool that calls the RowReader::seekToRow function once before each call the RowReader:: next() function to test this patch. The results are shown below:

	original	optimized	speedup
Elapsed Time(s)	43.69	27.13	1.61

How was this patch tested?

The original UTs(TestPredicatePushdown, DictionaryEncoding::multipleStripesWithIndex, DictionaryEncoding::multipleStripesWithoutIndex) will cover this patch.

dongjoon-hyun

Thank you for making a PR, @coderex2522 .

dongjoon-hyun · 2022-05-12T02:40:48Z

+    const T& operator[](uint64_t i) const {
+      return buf[i];
+    }
+


Does this part have a big impact?

The DataBuffer class already has a non-const operator() function, so adding a const operator() function should have no effect.

suggest to use the trick to remove duplicates between const and non-const overloads: https://stackoverflow.com/questions/123758/how-do-i-remove-code-duplication-between-similar-const-and-non-const-member-func

I write a simple demo for testing the implement overload that use const function to implement non-const function.
The complex implement(return const_cast<T&>(static_cast<const DataBuffer&>(*this)[i])) will cost twice the overhead of the simple implement(return buf[i]).

Thanks. Could you share your environment information and the numbers with the above, @coderex2522 ?

Test Environment: x86_64, gcc version 4.8.5
The test results were 7.03 seconds and 3.82 seconds respectively. @dongjoon-hyun

Which OS are you on? The build chain looks a little old to me. I expected 9.4.0 or 11.2.0.

I retested it with gcc 9.2.1 and the results were similar. And both tests were on Linux OS x86_64.

dongjoon-hyun · 2022-05-12T02:41:58Z

    friend class TestRowReader_advanceToNextRowGroup_Test;
    friend class TestRowReader_computeBatchSize_Test;

+    inline uint64_t lastRowOfCurrentStripe() const {


Please add a function description comment.

Do we use this somewhere?

The function has remove.

stiga-huang

LGTM. It'd be nice if we can have a more specifit commit tittle. We are optimzing the case seeking within the same stripe. Seeking within the same RowGroup is not optimized in this PR. So having a title like "ORC-1170:[C++] Optimize seeking within the same stripe" seems better to me.

stiga-huang · 2022-05-16T06:55:09Z

    friend class TestRowReader_advanceToNextRowGroup_Test;
    friend class TestRowReader_computeBatchSize_Test;

+    inline uint64_t lastRowOfCurrentStripe() const {


Do we use this somewhere?

coderex2522 · 2022-05-16T11:49:12Z

LGTM. It'd be nice if we can have a more specifit commit tittle. We are optimzing the case seeking within the same stripe. Seeking within the same RowGroup is not optimized in this PR. So having a title like "ORC-1170:[C++] Optimize seeking within the same stripe" seems better to me.

I think seeking within the same stripe is inclusive of seeking withing the same RowGroup. Seeking withing the same RowGroup will also call function startNextStripe under the original implementation.

wgtmac · 2022-05-17T02:03:24Z

+      if (rowIndexes.empty()) {
+        loadStripeIndex();
      }
+      seekToRowGroup(static_cast<uint32_t>(rowsToSkip / rowIndexStride));


If somehow it fails to parse the row index or finds some missing columns in the call of loadStripeIndex(), the seekToRowGroup here cannot proceed. Maybe add a TODO here to mark a future improvement.

nit.
For TODO comment, an IDed TODO style is recommended in order not to forget about it.
It means to file an official ORC JIRA and use TODO(ORC-XXX) style.

Improved the todo comment, thanks!

wgtmac · 2022-05-17T02:05:05Z

    uint64_t firstStripe;
    uint64_t currentStripe;
    uint64_t lastStripe; // the stripe AFTER the last one
+    uint64_t currentInitedStripe;


The naming is a little bit casual, maybe processingStripe?

dongjoon-hyun · 2022-05-19T06:53:11Z

Although I set the milestone for Apache ORC 1.9.0, please feel free to backport this if you want in Apache ORC 1.8.0, @wgtmac and @stiga-huang .

wgtmac

LGTM, +1

dongjoon-hyun

+1, LGTM, too. Thank you, @coderex2522 , @stiga-huang , @wgtmac .
Merged to master.

dongjoon-hyun · 2022-05-21T23:51:56Z

This is merged via 11a2544

…#70079) ### What problem does this PR solve? Related PR: apache/doris-thirdparty#431 (merge the ORC dependency fix first) A condition-cache granule can start in a stripe's SARG-filtered suffix while containing a matching row in the next stripe. On an initialized stripe, ORC's `seekToRow()` uses the stripe-end sentinel as a row-group index. This can access past the index when the stripe ends on an index boundary, or prematurely return EOF when the last row group is partial. The same-stripe fast path originates in [Apache ORC ORC-1170](apache/orc#1114); the same missing stripe-end handling remains in the current upstream C++ reader. Pin the ORC fix that initializes the next selected stripe before positioning its column readers. Preserve SARG pruning, lazy reads and split boundaries. Add a Doris reader regression and a 1.5 KB synthetic ORC fixture with its generator. The fixture has two 20,000-row stripes, a 10,000-row index stride, and one matching row at the start of each stripe. A cache hit seeks to row 18,432 in the first stripe's filtered suffix. The SQL regression compares cache-disabled and cached results with lazy reads and min/max pruning enabled or disabled, and checks the profile for actual cache hits and skipped rows. ### Release note Fix potential crashes and missing rows when ORC condition-cache seeks reach a SARG-filtered stripe suffix. ### Check List (For Author) - Test: - [x] Unit Test: 247 ORC-related BE tests passed under AddressSanitizer, including the new Doris condition-cache case and 32 dependency boundary cases. - [x] Unit Test: 56 focused standalone ORC tests passed under AddressSanitizer. Reverting the fix makes all 16 initialized-stripe boundary cases fail. - [ ] Regression test: SQL suite added; Groovy compilation checked. The external SQL suite has not been executed locally. - [x] clang-format 16 and BE build-hygiene checks passed. - [ ] Local full-file clang-tidy analysis did not complete within ten minutes; no completed result is available. - Behavior changed: - [x] Yes. Safely advance to the next matching stripe or EOF. - Does this need documentation? - [x] No.

ORC-1170:[C++] Optimize the RowReader::seekToRow function

09bda4e

github-actions Bot added the CPP label May 11, 2022

dongjoon-hyun reviewed May 12, 2022

View reviewed changes

Comment thread c++/src/Reader.hh Resolved

ORC-1170:[C++] add some function description comments

76ceb38

stiga-huang reviewed May 16, 2022

View reviewed changes

ORC-1170:[C++] remove the unused function

12ab35c

coderex2522 changed the title ~~ORC-1170:[C++] Optimize the RowReader::seekToRow function~~ ORC-1170:[C++] Optimize the RowReader::seekToRow function in the case of seeking within the same stripe May 16, 2022

wgtmac reviewed May 17, 2022

View reviewed changes

ORC-1170:[C++] add todo comments and modify the variable name

db2c2e7

dongjoon-hyun added this to the 1.9.0 milestone May 19, 2022

ORC-1170:[C++] refine the description of todo comment

4d31c6c

wgtmac approved these changes May 20, 2022

View reviewed changes

dongjoon-hyun approved these changes May 21, 2022

View reviewed changes

dongjoon-hyun closed this May 21, 2022

Gabriel39 mentioned this pull request Nov 3, 2026

[fix](be) Fix ORC condition-cache seeks past filtered stripe suffixes apache/doris#70079

Merged

5 of 7 tasks

Conversation

coderex2522 commented May 11, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

What changes were proposed in this pull request?

Why are the changes needed?

How was this patch tested?

Uh oh!

dongjoon-hyun left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

coderex2522 May 12, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

stiga-huang left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

coderex2522 commented May 16, 2022

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

dongjoon-hyun commented May 19, 2022

Uh oh!

wgtmac left a comment

Choose a reason for hiding this comment

Uh oh!

dongjoon-hyun left a comment

Choose a reason for hiding this comment

Uh oh!

dongjoon-hyun commented May 21, 2022

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

coderex2522 commented May 11, 2022 •

edited

Loading

coderex2522 May 12, 2022 •

edited

Loading