search

389ds / 389-ds-base

The enterprise-class Open Source LDAP server for Linux
https://www.port389.org/
Other
211 stars 91 forks source link

optimise filters for common query types #2431

Closed 389-ds-bot closed 2 months ago

389-ds-bot commented 4 years ago

Cloned from Pagure issue: https://pagure.io/389-ds-base/issue/49372

Issue Description

During filter processing we attempt to minimise the amount of work we do. Some filter elements are likely always to be costly relative to the filter test threshold.

By moving some common known expensive elements to the tail of the filter, we can avoid costly index lookups and improve common search times. A prime example is that most common searches are:

(&(objectClass=person)(uid=william))

Why should we load the entire person index, when uid=william has an idl of size 1, and thus triggers the filter test threshold.

A similar example would be:

(&(!(objectClass=nsTombstone))(uid=william))

Because the not candidate is likely to be expensive if we pushed this last, this would again, benefit from the filter test threshold.

389-ds-bot commented 4 years ago

Comment from mreynolds (@mreynolds389) at 2017-09-07 17:52:02

Metadata Update from @mreynolds389:

389-ds-bot commented 4 years ago

Comment from firstyear (@Firstyear) at 2017-09-08 07:32:49

0001-Ticket-49372-filter-optimisation-improvements-for-co.patch

Improve common filter behaviours. This moves filter foldeing (IE (&(&()) -> (&()) to the filter_optimise step.

Additionally, we re-arrange the location where we apply optimisation to the "last possible" moment, which changes some locations and how we free their filters. But this gives us the best possible behaviour of the idl/idl set components.

389-ds-bot commented 4 years ago

Comment from firstyear (@Firstyear) at 2017-09-08 08:15:04

To highlight this difference, this is a search where idlistscanlimit can accommodate the entire objectClass idl:

BEFORE:

(&(objectClass=person)(uid=test0010083))  etime=0.0007833143
(&(uid=test0010083)(objectClass=person))  etime=0.0000664115

AFTER:

(&(objectClass=person)(uid=test0010083))  etime=0.0000760933
(&(uid=test0010083)(objectClass=person))  etime=0.0000976630

Note the difference in order of the two sets: for uid= first this is approximately 1/8th of the processing time compared to objectClass=person.

The only way to achieve "near" this is to reduce the idlistscan limit, but even then:

BEFORE with lower idlistscanlimit:

(&(objectClass=person)(uid=test0010083))  etime=0.0001458060

This value still is about twice the value of the after.

Additionally, on more complex queries this would have a greater impact. For example:

BEFORE with lower idlistscanlimit:

(&(objectClass=inetOrgPerson)(objectClass=person)(objectClass=posixAccount)(uid=test0010083))  etime=0.0002360271

AFTER:

(&(objectClass=inetOrgPerson)(objectClass=person)(objectClass=posixAccount)(uid=test0010083))  etime=0.0000616770

This still shows a reasonable improvement in processing time.

389-ds-bot commented 4 years ago

Comment from ilias95 (@ilstam) at 2017-09-08 11:44:25

Hello.

    # LDAP_FILTER_PRESENT 135
    if f_choice == 0x87:
        print("%s(%s=*)" % (pad, f_un['f_un_type']))
    # LDAP_FILTER_APPROX
    elif f_choice == 0xa8:
        pass
    # LDAP_FILTER_LE
    elif f_choice == 0xa6:
        pass
    ...

Would it be better to get rid of the comments in this part and define constants or enums instead?

389-ds-bot commented 4 years ago

Comment from firstyear (@Firstyear) at 2017-09-11 03:41:14

Indeed it can be. I have changed this to an IntEnum now. Thanks for the tip!

0001-Ticket-49372-filter-optimisation-improvements-for-co.patch

389-ds-bot commented 4 years ago

Comment from mreynolds (@mreynolds389) at 2017-09-11 18:55:26

The patch causes multiple regressions. Failing tests:

48252 48265 (hangs the server 100% CPU)

I couldn't run any more tests due to the hang in 48265, so there could be more failures/regressions. Please run the full test suite before sending out the next patch. Thanks.

389-ds-bot commented 4 years ago

Comment from firstyear (@Firstyear) at 2017-09-12 02:06:21

48265 triggers a heap-use-after free it looks like. I'll investigate this more.

389-ds-bot commented 4 years ago

Comment from lkrispen (@elkris) at 2017-09-12 10:10:31

one more general comment. I think the optimisation idea is good and should be implemented if the tests pass. What I would like to see is a test for a database with referrals and tests wit/without managed site control since the handling of this is also changed

389-ds-bot commented 4 years ago

Comment from firstyear (@Firstyear) at 2017-09-28 00:00:44

Metadata Update from @Firstyear:

389-ds-bot commented 4 years ago

Comment from firstyear (@Firstyear) at 2017-09-28 02:49:19

0001-Ticket-49372-filter-optimisation-improvements-for-co.patch

@elkris I've already done a referral test, and that's happy. Pretty much every search is the referral case in fact.

Hew managedsait case however I'm not so sure about. How would I test this?

Anyway, the patch fixes the issues with crash on those tests

25 passed in 36.17 seconds

48252 is still failing, but that's not related to this. I did a dump on the filters:


(|
    (&
        (0x6020003a5070 "objectClass"=0x6020003a5050 "nstombstone")
        (0x6020003a50f0 "uid"=0x6020003a50d0 "test_user1")
    )
    (0x6020003a5130 "objectclass"=0x6020003a5150 "referral")
)

(|
    (&
        (0x6020003a50f0 "uid"=0x6020003a50d0 "test_user1")
        (0x6020003a5070 "objectClass"=0x6020003a5050 "nstombstone")
    )
    (0x6020003a5130 "objectclass"=0x6020003a5150 "referral")
)

So we aren't mangaling these, I think we are hitting a different issue, perhaps #2414

389-ds-bot commented 4 years ago

Comment from mreynolds (@mreynolds389) at 2017-09-28 04:20:26

48252 test was fixed, did you rebase with master yet?

There's been recent updates to the ci tests, so I'd like to see the latest tests run again with your patch.

389-ds-bot commented 4 years ago

Comment from firstyear (@Firstyear) at 2017-09-28 04:55:07

I may not have rebased this branch. I'll check again shortly.

389-ds-bot commented 4 years ago

Comment from firstyear (@Firstyear) at 2017-09-28 05:32:51

Okay, I've rebased and master works, but with this it does not. I wonder if I'm losing a flag on the filter for when oc is set perhaps? I'll investigate some more,

389-ds-bot commented 4 years ago

Comment from firstyear (@Firstyear) at 2017-09-29 03:24:39

WORKING:
(| flags:2
    (& flags:2
        (0x6020003a5070 "objectClass"=0x6020003a5050 "nstombstone") flags:0
        (0x6020003a50f0 "uid"=0x6020003a50d0 "test_user1") flags:0
    )
    (0x6020003a5130 "objectclass"=0x6020003a5150 "referral") flags:0
)

FAILING:
(| flags:2
    (& flags:2
        (0x6020003a50f0 "uid"=0x6020003a50d0 "test_user1") flags:0
        (0x6020003a5070 "objectClass"=0x6020003a5050 "nstombstone") flags:0
    )
    (0x6020003a5130 "objectclass"=0x6020003a5150 "referral") flags:0
)

I think that this could be because we require nstombstone to be the first filter, because if we do the uid filter first we get 0 in the idl, so we trigger filter_test_threshold and return too early. So this could be the cause,

Really, what causes the problem with this patch, is we re-order the AND/OR components when we prioritise them - Perhaps if flags contains tombstone, we don't optimise?

389-ds-bot commented 4 years ago

Comment from firstyear (@Firstyear) at 2017-09-29 03:59:09

0001-Ticket-49372-filter-optimisation-improvements-for-co.patch

This checks if f_flags has TOMBSTONE set, and avoids optimising if true. This now passes 48252.

389-ds-bot commented 4 years ago

Comment from firstyear (@Firstyear) at 2017-10-03 04:59:40

https://pagure.io/lib389/issue/102 @elkris This lib389 patch adds support for smart referral objects, and a test case to show they work with the managedsait control. I tested it with this patch enabled and it passes :)

389-ds-bot commented 4 years ago

Comment from mreynolds (@mreynolds389) at 2017-10-04 15:31:40

Metadata Update from @mreynolds389:

389-ds-bot commented 4 years ago

Comment from firstyear (@Firstyear) at 2017-10-05 01:09:09

commit 4cd1a24b3ce88968ff5f9a2b87efdc84dee176da To ssh://git@pagure.io/389-ds-base.git 4060848..4cd1a24 master -> master

Thanks Mark and Ludwig!

389-ds-bot commented 4 years ago

Comment from firstyear (@Firstyear) at 2017-10-05 01:09:09

Metadata Update from @Firstyear:

389-ds-bot commented 4 years ago

Comment from mreynolds (@mreynolds389) at 2018-07-05 21:32:23

Look like this also fixes issues with scope one searches in 1.3.7/1.3.8.

389-ds-bot commented 4 years ago

Comment from mreynolds (@mreynolds389) at 2018-07-05 21:32:24

Metadata Update from @mreynolds389:

389-ds-bot commented 4 years ago

Comment from mreynolds (@mreynolds389) at 2018-07-05 22:02:08

1.3.7:

5ad7f149b Ticket 49372 - filter optimisation improvements for common queries

1.3.8 f7a21acb6 Ticket 49372 - filter optimisation improvements for common queries

389-ds-bot commented 4 years ago

Comment from mreynolds (@mreynolds389) at 2018-08-24 22:19:11

We need to revert this fix in all branches. Its breaking all kinds of things, and its holding up F27. Going to revert for now until we get everything sorted out...

389-ds-bot commented 4 years ago

Comment from mreynolds (@mreynolds389) at 2018-08-24 22:19:12

Metadata Update from @mreynolds389:

389-ds-bot commented 4 years ago

Comment from mreynolds (@mreynolds389) at 2018-08-24 22:43:35

Reverts...

Master: d06b5bb2c..14a10a34b master -> master

commit 14a10a34b3ff10d5146d73e67aa54c8945cfa37d (HEAD -> ticket49372) Revert "Ticket 49372 - filter optimisation improvements for common queries This reverts commit 4cd1a24b3ce88968ff5f9a2b87efdc84dee176da.

commit 104968b67bbfbc89cf5311c7ca7be973dd86baed Revert "Ticket 49432 - filter optimise crash" This reverts commit 5c89dd8f9c8eb77c967574412d049d55565bb364.

1.3.8: 96f334aeb..3386445f6 389-ds-base-1.3.8 -> 389-ds-base-1.3.8

commit 3386445f6b4676e66b6803a4883a49622ec70f62 (HEAD -> 389-ds-base-1.3.8) Revert "Ticket 49372 - filter optimisation improvements for common queries" This reverts commit f7a21acb6f01d6c39c7e21d2fd77af183c3a7a89.

commit 1c5b9b03151ad312e0d6c7cc535062df1b7061da Revert "Ticket 49432 - filter optimise crash" This reverts commit d8d57c9b472591628f630bfdc15a6f4db80035ad.

1.3.7: d3cf9f225..79d0b4dee 389-ds-base-1.3.7 -> 389-ds-base-1.3.7

commit 79d0b4dee5994f54b468ece335a73007a68914bc (HEAD -> 389-ds-base-1.3.7) Revert "Ticket 49372 - filter optimisation improvements for common queries" This reverts commit 5ad7f149b5f7cadd0f54c1772e18aee679584b62.

commit 24b84d13c36087d2288c691225886dccbb3c6944 Revert "Ticket 49432 - filter optimise crash" This reverts commit 855d78b5af6a97efa31f6986d27566c990da0826.

389-ds-bot commented 4 years ago

Comment from lkrispen (@elkris) at 2018-08-29 09:33:22

the backout also fixed the issue reported in bz 1616412 (patch for 48275 longer working).

also the patch for 49617 which was not committed is no longer needed.

But if we decide to put the optimization back we need to address these two issues

389-ds-bot commented 4 years ago

Comment from mreynolds (@mreynolds389) at 2019-04-17 22:25:25

Reference:

https://bugzilla.redhat.com/show_bug.cgi?id=1616412

This is the bug where this enhancement originally broke things

389-ds-bot commented 4 years ago

Comment from firstyear (@Firstyear) at 2019-04-18 02:14:41

@elkris Yep, there is a debbuging patch in PR to check to see what's going on here. I think it's in re-arrangement of onelevel searches because that code was improved in this patch.

@mreynolds389 Thanks, I'll have a look, but witohut the extra debug logging, it may not be easy to use this to piece together what went wrong :(

389-ds-bot commented 4 years ago

Comment from mreynolds (@mreynolds389) at 2019-08-23 20:05:28

Metadata Update from @mreynolds389:

389-ds-bot commented 4 years ago

Comment from vashirov (@vashirov) at 2020-03-11 15:39:02

Metadata Update from @vashirov:

vashirov commented 2 months ago

Closing as completed, this was implemented in https://github.com/389ds/389-ds-base/issues/5170