Mailing List Archive: Lucene: Java-Dev

[jira] [Updated] (LUCENE-4283) Support more frequent skip with Block Postings Format

Index | Next | Previous | View Threaded

jira at apache

Aug 2, 2012, 3:41 AM

Post #1 of 7 (84 views)
Permalink

[jira] [Updated] (LUCENE-4283) Support more frequent skip with Block Postings Format

[ https://issues.apache.org/jira/browse/LUCENE-4283?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Han Jiang updated LUCENE-4283:
------------------------------

Attachment: LUCENE-4283-buggy.patch

An initial try to support partial decode & skipInterval == 32. Details about the skip format is mentioned in BlockSkipWriter. This patch works against pfor-3892 branch, with revision 1365112.

It passes TestPostingsFormat, but still fail to pass CheckIndex. Mike, these test seed should fail the patch.
{noformat}

ant test-core -Dtestcase=TestLongPostings -Dtests.method=testLongPostingsNoPositions -Dtests.seed=EC8F49E9088B926C -Dtests.postingsformat=Block

ant test-core -Dtestcase=TestCustomSearcherSort -Dtests.method=testFieldSortSingleSearcher -Dtests.seed=EC8F49E9088B926C -Dtests.postingsformat=Block

{noformat}

> Support more frequent skip with Block Postings Format
> -----------------------------------------------------
>
> Key: LUCENE-4283
> URL: https://issues.apache.org/jira/browse/LUCENE-4283
> Project: Lucene - Core
> Issue Type: Improvement
> Reporter: Han Jiang
> Priority: Minor
> Attachments: LUCENE-4283-buggy.patch
>
>
> This change works on the new bulk branch.
> Currently, our BlockPostingsFormat only supports skipInterval==blockSize. Every time the skipper reaches the last level 0 skip point, we'll have to decode a whole block to read doc/freq data. Also, a higher level skip list will be created only for those df>blockSize^k, which means for most terms, skipping will just be a linear scan. If we increase current blockSize for better bulk i/o performance, current skip setting will be a bottleneck.
> For ForPF, the encoded block can be easily splitted if we set skipInterval=32*k.

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe [at] lucene
For additional commands, e-mail: dev-help [at] lucene

jira at apache

Aug 2, 2012, 3:55 AM

Post #2 of 7 (79 views)
Permalink

[jira] [Updated] (LUCENE-4283) Support more frequent skip with Block Postings Format [In reply to]

[ https://issues.apache.org/jira/browse/LUCENE-4283?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Han Jiang updated LUCENE-4283:
------------------------------

Attachment: LUCENE-4283-buggy.patch

oh, forgot to revert TestPF

> Support more frequent skip with Block Postings Format
> -----------------------------------------------------
>
> Key: LUCENE-4283
> URL: https://issues.apache.org/jira/browse/LUCENE-4283
> Project: Lucene - Core
> Issue Type: Improvement
> Reporter: Han Jiang
> Priority: Minor
> Attachments: LUCENE-4283-buggy.patch, LUCENE-4283-buggy.patch
>
>
> This change works on the new bulk branch.
> Currently, our BlockPostingsFormat only supports skipInterval==blockSize. Every time the skipper reaches the last level 0 skip point, we'll have to decode a whole block to read doc/freq data. Also, a higher level skip list will be created only for those df>blockSize^k, which means for most terms, skipping will just be a linear scan. If we increase current blockSize for better bulk i/o performance, current skip setting will be a bottleneck.
> For ForPF, the encoded block can be easily splitted if we set skipInterval=32*k.

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe [at] lucene
For additional commands, e-mail: dev-help [at] lucene

jira at apache

Aug 3, 2012, 12:29 PM

Post #3 of 7 (76 views)
Permalink

[jira] [Updated] (LUCENE-4283) Support more frequent skip with Block Postings Format [In reply to]

[ https://issues.apache.org/jira/browse/LUCENE-4283?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Han Jiang updated LUCENE-4283:
------------------------------

Attachment: LUCENE-4283-slow.patch

Previous buggy patch will fail when df=128*k(k=2,3...), since skip reader silly reads the skip point just after the last doc...

This patch should pass all the tests. I haven't test performance, but tests on previous buggy patch shows a net loss, I'll try to optimize on the interval&blocksize later...

> Support more frequent skip with Block Postings Format
> -----------------------------------------------------
>
> Key: LUCENE-4283
> URL: https://issues.apache.org/jira/browse/LUCENE-4283
> Project: Lucene - Core
> Issue Type: Improvement
> Reporter: Han Jiang
> Priority: Minor
> Attachments: LUCENE-4283-buggy.patch, LUCENE-4283-buggy.patch, LUCENE-4283-slow.patch
>
>
> This change works on the new bulk branch.
> Currently, our BlockPostingsFormat only supports skipInterval==blockSize. Every time the skipper reaches the last level 0 skip point, we'll have to decode a whole block to read doc/freq data. Also, a higher level skip list will be created only for those df>blockSize^k, which means for most terms, skipping will just be a linear scan. If we increase current blockSize for better bulk i/o performance, current skip setting will be a bottleneck.
> For ForPF, the encoded block can be easily splitted if we set skipInterval=32*k.

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe [at] lucene
For additional commands, e-mail: dev-help [at] lucene

jira at apache

Aug 4, 2012, 11:21 AM

Post #4 of 7 (79 views)
Permalink

[jira] [Updated] (LUCENE-4283) Support more frequent skip with Block Postings Format [In reply to]

[ https://issues.apache.org/jira/browse/LUCENE-4283?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Han Jiang updated LUCENE-4283:
------------------------------

Attachment: LUCENE-4283-small-interval-partially.patch
LUCENE-4283-small-interval-fully.patch

Two patches: tidied some codes, and removed the partially decoding out to see how we improved only with smaller interval. *-fully.patch will refill a whole block of docs when docBuffer is used up, *-partially.patch will only decode an interval of block when necessary.

> Support more frequent skip with Block Postings Format
> -----------------------------------------------------
>
> Key: LUCENE-4283
> URL: https://issues.apache.org/jira/browse/LUCENE-4283
> Project: Lucene - Core
> Issue Type: Improvement
> Reporter: Han Jiang
> Priority: Minor
> Attachments: LUCENE-4283-buggy.patch, LUCENE-4283-buggy.patch, LUCENE-4283-slow.patch, LUCENE-4283-small-interval-fully.patch, LUCENE-4283-small-interval-partially.patch
>
>
> This change works on the new bulk branch.
> Currently, our BlockPostingsFormat only supports skipInterval==blockSize. Every time the skipper reaches the last level 0 skip point, we'll have to decode a whole block to read doc/freq data. Also, a higher level skip list will be created only for those df>blockSize^k, which means for most terms, skipping will just be a linear scan. If we increase current blockSize for better bulk i/o performance, current skip setting will be a bottleneck.
> For ForPF, the encoded block can be easily splitted if we set skipInterval=32*k.

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe [at] lucene
For additional commands, e-mail: dev-help [at] lucene

jira at apache

Aug 5, 2012, 9:39 AM

Post #5 of 7 (74 views)
Permalink

[jira] [Updated] (LUCENE-4283) Support more frequent skip with Block Postings Format [In reply to]

[ https://issues.apache.org/jira/browse/LUCENE-4283?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Han Jiang updated LUCENE-4283:
------------------------------

Attachment: LUCENE-4283-codes-cleanup.patch

Remove small interval codes, which will be digged later... Mike, this patch should be ready to commit!

> Support more frequent skip with Block Postings Format
> -----------------------------------------------------
>
> Key: LUCENE-4283
> URL: https://issues.apache.org/jira/browse/LUCENE-4283
> Project: Lucene - Core
> Issue Type: Improvement
> Reporter: Han Jiang
> Priority: Minor
> Attachments: LUCENE-4283-buggy.patch, LUCENE-4283-buggy.patch, LUCENE-4283-codes-cleanup.patch, LUCENE-4283-slow.patch, LUCENE-4283-small-interval-fully.patch, LUCENE-4283-small-interval-partially.patch
>
>
> This change works on the new bulk branch.
> Currently, our BlockPostingsFormat only supports skipInterval==blockSize. Every time the skipper reaches the last level 0 skip point, we'll have to decode a whole block to read doc/freq data. Also, a higher level skip list will be created only for those df>blockSize^k, which means for most terms, skipping will just be a linear scan. If we increase current blockSize for better bulk i/o performance, current skip setting will be a bottleneck.
> For ForPF, the encoded block can be easily splitted if we set skipInterval=32*k.

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe [at] lucene
For additional commands, e-mail: dev-help [at] lucene

jira at apache

Aug 7, 2012, 10:52 AM

Post #6 of 7 (65 views)
Permalink

[jira] [Updated] (LUCENE-4283) Support more frequent skip with Block Postings Format [In reply to]

[ https://issues.apache.org/jira/browse/LUCENE-4283?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Han Jiang updated LUCENE-4283:
------------------------------

Attachment: LUCENE-4283-record-next-skip.patch

now we record next skip point, and try not to use skipper when target is still within current buffer.

> Support more frequent skip with Block Postings Format
> -----------------------------------------------------
>
> Key: LUCENE-4283
> URL: https://issues.apache.org/jira/browse/LUCENE-4283
> Project: Lucene - Core
> Issue Type: Improvement
> Reporter: Han Jiang
> Priority: Minor
> Attachments: LUCENE-4283-buggy.patch, LUCENE-4283-buggy.patch, LUCENE-4283-codes-cleanup.patch, LUCENE-4283-record-next-skip.patch, LUCENE-4283-slow.patch, LUCENE-4283-small-interval-fully.patch, LUCENE-4283-small-interval-partially.patch
>
>
> This change works on the new bulk branch.
> Currently, our BlockPostingsFormat only supports skipInterval==blockSize. Every time the skipper reaches the last level 0 skip point, we'll have to decode a whole block to read doc/freq data. Also, a higher level skip list will be created only for those df>blockSize^k, which means for most terms, skipping will just be a linear scan. If we increase current blockSize for better bulk i/o performance, current skip setting will be a bottleneck.
> For ForPF, the encoded block can be easily splitted if we set skipInterval=32*k.

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe [at] lucene
For additional commands, e-mail: dev-help [at] lucene

jira at apache

Aug 7, 2012, 11:29 PM

Post #7 of 7 (64 views)
Permalink

[jira] [Updated] (LUCENE-4283) Support more frequent skip with Block Postings Format [In reply to]

[ https://issues.apache.org/jira/browse/LUCENE-4283?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Han Jiang updated LUCENE-4283:
------------------------------

Attachment: LUCENE-4283-record-skip&inlining-scanning.patch

This patch should also inline scanning for EverythingEnum, and remove some condition statements(refillDocs etc.) out from the while loop.

> Support more frequent skip with Block Postings Format
> -----------------------------------------------------
>
> Key: LUCENE-4283
> URL: https://issues.apache.org/jira/browse/LUCENE-4283
> Project: Lucene - Core
> Issue Type: Improvement
> Reporter: Han Jiang
> Priority: Minor
> Attachments: LUCENE-4283-buggy.patch, LUCENE-4283-buggy.patch, LUCENE-4283-codes-cleanup.patch, LUCENE-4283-record-next-skip.patch, LUCENE-4283-record-skip&inlining-scanning.patch, LUCENE-4283-slow.patch, LUCENE-4283-small-interval-fully.patch, LUCENE-4283-small-interval-partially.patch
>
>
> This change works on the new bulk branch.
> Currently, our BlockPostingsFormat only supports skipInterval==blockSize. Every time the skipper reaches the last level 0 skip point, we'll have to decode a whole block to read doc/freq data. Also, a higher level skip list will be created only for those df>blockSize^k, which means for most terms, skipping will just be a linear scan. If we increase current blockSize for better bulk i/o performance, current skip setting will be a bottleneck.
> For ForPF, the encoded block can be easily splitted if we set skipInterval=32*k.

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe [at] lucene
For additional commands, e-mail: dev-help [at] lucene

Index | Next | Previous | View Threaded

Interested in having your list archived? Contact Gossamer Threads