[11.x] Improve performance of InteractsWithPivotTable sync method's attachNew procedure

[haejinjo]

Proposed Refactor

The current attachNew implementation uses PHP's in_array to check if an ID is already present in the $current array.
This leads to O(N) complexity for each check, where N is the size of the $current array.

To optimize, we can convert the $current array to an associative array where keys are the IDs.
This will allow us to use PHP's array_key_exists for O(1) hash lookups which will improve performance, especially for large datasets.

Context

In developing my Laravel application locally, I ran the code below for a model associated with 150k pivot table records.

$someModel->somePivotRelation->syncWithoutDetaching( * Collection of 12k records *);

This caused a server timeout using Laravel's defaults. To fix the timeout, I used tinker to manually detach most of the model's associated pivot table records to match the length of the sync input (12k records), which resolved the issue.

I was curious what caused the slowdown, so I dug into the InteractsWithPivot table.

[Sophist-UK]

This sounds sensible to me (though I suspect that 150k records is unusual).

[haejinjo]

Yeah seems like it'd be a pretty minor tweak to the existing sync logic that will result in big performance gains.

[haejinjo]

I did a quick & dirty microtime profiling experiment with my use case.

Namely, I updated the sync method to format $current as an associative array, then applied array_key_exists instead of in_array in the attachNew method it invokes.

    /**
     * Sync the intermediate tables with a list of IDs or collection of models.
     *
     * @param  \Illuminate\Support\Collection|\Illuminate\Database\Eloquent\Model|array  $ids
     * @param  bool  $detaching
     * @return array
     */
    public function sync($ids, $detaching = true)
    {
        $changes = [
            'attached' => [], 'detached' => [], 'updated' => [],
        ];

        // First we need to attach any of the associated models that are not currently
        // in this joining table. We'll spin through the given IDs, checking to see
        // if they exist in the array of current ones, and if not we will insert.
        $current = $this->getCurrentlyAttachedPivots();
                        

        $records = $this->formatRecordsList($this->parseIds($ids));

        // Next, we will take the differences of the currents and given IDs and detach
        // all of the entities that exist in the "current" array but are not in the
        // array of the new IDs given to the method which will complete the sync.
        if ($detaching) {
            $detach = array_diff($current->pluck($this->relatedPivotKey)->all(), array_keys($records));

            if (count($detach) > 0) {
                $this->detach($detach);

                $changes['detached'] = $this->castKeys($detach);
            }
        }

        // Now we are finally ready to attach the new records. Note that we'll disable
        // touching until after the entire operation is complete so we don't fire a
        // ton of touch operations until we are totally done syncing the records.
        $changes = array_merge(
            $changes, $this->attachNew($records, $current->pluck($this->relatedPivotKey, $this->relatedPivotKey)->all(), false)
        );

        // Once we have finished attaching or detaching the records, we will see if we
        // have done any attaching or detaching, and if we have we will touch these
        // relationships if they are configured to touch on any database updates.
        if (count($changes['attached']) ||
            count($changes['updated']) ||
            count($changes['detached'])) {
            $this->touchIfTouching();
        }

        return $changes;
    }

    /**
     * Attach all of the records that aren't in the given current records.
     *
     * @param  array  $records
     * @param  array  $current
     * @param  bool  $touch
     * @return array
     */
    protected function attachNew(array $records, array $current, $touch = true)
    {
        $changes = ['attached' => [], 'updated' => []];

        foreach ($records as $id => $attributes) {
            // If the ID is not in the list of existing pivot IDs, we will insert a new pivot
            // record, otherwise, we will just update this existing record on this joining
            // table, so that the developers will easily update these records pain free.
            if (! array_key_exists($id, $current)) {
                $this->attach($id, $attributes, $touch);

                $changes['attached'][] = $this->castKey($id);
            }

            // Now we'll try to update an existing pivot record with the attributes that were
            // given to the method. If the model is actually updated we will add it to the
            // list of updated pivot records so we return them back out to the consumer.
            elseif (count($attributes) > 0 &&
                $this->updateExistingPivot($id, $attributes, $touch)) {
                $changes['updated'][] = $this->castKey($id);
            }
        }

        return $changes;
    }

Before the change, syncWIthoutDetaching took 0.23 seconds per call on my pivot table data.
After, it took 0.18. So about a 0.05 second improvement. Over about 12 pages of data, this saves 0.6 second. So, take with that what you will.

[Sophist-UK]

I am unclear just how large the pivot table was to get a 1/20th second reduction in time, but with current CPU speeds and expectations on response time this is not to be sneezed at. That said, this is clearly NOT the same as the original case which timed-out and we really need to know just how much time would be saved in cases with that large amount of data.

Having now had a quick look at the code (and I have not spent the time fully understanding what the original / new code does in detail) I have the following comments:

1. Would the code benefit from using associative arrays everywhere for all internal i.e. local variable arrays?

2. Is it possible to eliminate or reduce the scope of the foreach in attachNew e.g. by using array-functions to reduce the keys iterated over only to those necessary in order to avoid iterating over the elements which do not meet either of the conditions inside the foreach loop?

[haejinjo]

The original case that caused the timeout was 600k pivot rows and 600k input IDs.
The 1/20th second reduction in time used the same 600k pivot rows, but with 12k input IDs, which passed timeout conditions.

Are you saying you want to know how long syncWithoutDetaching takes with timeout removed?

[haejinjo]

Sidenote: @krembo spoke to the performance issues with sync before I did here:

https://olegkreimerpublished.medium.com/laravel-sync-relationship-method-a-word-of-caution-300eece787a6